POJ3696 The Luckiest number【欧拉函数】

题目链接：

http://poj.org/problem?id=3696

题目大意：

给你一个数N，问是否存在L的倍数M，且数M各个位上都由8组成，如果存在多个M，输出最小

的那个，并输出M由几个8组成。

思路：

设长度为x，由题意可知，长度为x的由8组成的数可以被L整除。形式为88…88，由于10^x-1是

长度为x、全部由9组成的数，则(10^x-1)/9*8 = L*k(k倍)，即(10^x-1)*8= 9*L*k。

则(10^x-1)*8/gcd(8，L) = 9*L*k/gcd(8，L)

令p = 8/gcd(8，L)  q = 9*L/gcd(8，L)，则(10^x-1)*p = q*k。

因为p和q是互质的，则(10^x-1) % q == 0。

根据同余定理可得10^x ≡ 1(mod q)，

再通过欧拉公式可知当gcd(10，q) = 1时，10^φ(q) ≡ 1(mod q)。而如果gcd(10，q) ≠ 1，则无解。

题目要求的是最小的解，答案就是φ(q)的因子，只要枚举φ(q)的因子，检查mod q 是否为1.

具体步骤如下：

1.求解φ(q)

2.找出φ(q)所有的素因子pi

3.找出满足10^x  ≡ 1(mod q)最小的x。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define LL __int64
#define MAXN (1 << 16)
using namespace std;

LL GCD(LL a,LL b)       //求最大公约数
{
    if(b == 0)
        return a;
    return GCD(b,a%b);
}

LL MultiMod(LL a,LL b,LL m) // a * b % m
{
    LL ans = 0;
    while(b)
    {
        if(b&1)
            ans = (ans + a) % m;
        a = a*2%m;
        b >>= 1;
    }
    return ans;
}

LL MultiPower(LL a,LL b,LL m) // a^b % m 用于求10^pi % m
{
    LL ans = 1;
    a %= m;
    while(b)
    {
        if(b&1)
            ans = MultiMod(ans,a,m);
        a = MultiMod(a,a,m);
        b >>= 1;
    }
    return ans;
}

LL Euler(LL n)      //求φ(n)
{
    LL ret = n;
    for(LL i = 2; i*i <= n; ++i)
    {
        if(n%i == 0)
        {
            n /= i;
            ret = ret - ret/i;
        }
        while(n % i == 0)
            n /= i;
    }
    if(n > 1)
        ret = ret - ret/n;
    return ret;
}

LL factor[MAXN],cnt;
void Divid(LL n)        //分解素因子
{
    cnt = 0;
    memset(factor,0,sizeof(factor));
    for(LL i = 1; i*i <= n; ++i)
    {
        if(n % i == 0)
        {
            factor[cnt++] = i;
            factor[cnt++] = n/i;
        }
    }
    sort(factor,factor + cnt);
}

int main()
{
    int kase = 0;
    LL m;
    while(cin >> m && m)
    {
        cout << "Case " << ++kase << ": ";
        m = m*9/GCD(m,8);
        if(GCD(m,10) != 1)
        {
            cout << "0" << endl;
            continue;
        }
        LL p = Euler(m);
        Divid(p);
        LL ans = 0;
        for(int i = 0; i < cnt; ++i)    //找出最小的x
        {
            if(MultiPower(10,factor[i],m) == 1)
            {
                ans = factor[i];
                break;
            }
        }
        cout << ans << endl;

    }

    return 0;
}

POJ3696 The Luckiest number【欧拉函数】

原文：http://blog.csdn.net/lianai911/article/details/44591181