POJ 3696 The Luckest number【Euler関数】

タイトルリンク:
http://poj.org/problem?id=3696
テーマ:
あなたに1つの数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)を得ることができ,
さらにEuler式により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;
}