POJ3696:The Luckiest number(欧拉函数||求某数最小的满足题意的因子)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Chinese people think of '8' as the lucky digit. Bob also likes digit '8'. Moreover, Bob has his own lucky number L . Now he wants to construct his luckiest number which is the minimum among all positive integers that are a multiple of L and consist of only digit '8'.

Input

The input consists of multiple test cases. Each test case contains exactly one line containing L (1 ≤ L ≤ 2,000,000,000).

The last test case is followed by a line containing a zero.

Output

For each test case, print a line containing the test case number( beginning with 1) followed by a integer which is the length of Bob's luckiest number. If Bob can't construct his luckiest number, print a zero.

Sample Input

Sample Output

Case 1: 1

Case 2: 2

Case 3: 0

题意： 求最小的由8组成的数，是L的倍数。

思路： 由一系列证明得到，ans=phi(N)的满足题意的最小因子。

关键： 对于X，求其满足题意的最小因子p|X，可以这样求，枚举素因子prime，如果X/prime满足题意，则X=X/prime。

存疑： 我感觉复杂度是根号级别的，但是我看到ppt上说是log级别。

#include<cstdio>

#include<cstdlib>

#include<iostream>

using namespace std;

#define ll long long

ll gcd(ll a,ll b){ if(b==) return a;return gcd(b,a%b);}

ll qmul(ll a,ll x,ll Mod){ll res=; a%=Mod; while(x){if(x&) res=(res+a)%Mod;a=(a+a)%Mod;x>>=;} return res;}

ll qpow(ll a,ll x,ll Mod){ll res=; a%=Mod; while(x){if(x&1LL) res=qmul(res,a,Mod); a=qmul(a,a,Mod); x>>=;} return res;}

ll phi(ll x)

{

    ll tx=x,res=x;

    for(int i=;i*i<=tx;i++){

        if(tx%i==){

            res-=res/i;

            while(tx%i==) tx/=i;

        }

    }

    if(tx>) res-=res/tx;

    return res;

}

ll find(ll Mod,ll py) //得到最小因子满足条件

{

     ll n=py; ll tp[][]; int k=;

     for(ll i=;i*i<=n;i++)      //唯一分解

       if(n%i==){

         k++; tp[k][]=i; tp[k][]=;

         while(n%i==){

            n/=i; tp[k][]++;

         }

     }

     if(n>) k++, tp[k][]=n, tp[k][]=; 

     for(int i=;i<=k;i++)

       for(int j=;j<=tp[i][];j++)

         if(qpow(,py/tp[i][],Mod)==)

           py/=tp[i][];

    return py;

}

int main()

{

    ll N,M,Case=;

    while(~scanf("%lld",&N)&&N){

        printf("Case %lld: ",++Case);

        N=N*/gcd(N,);

        if(gcd(N,)!=) printf("0\n");

        else printf("%d\n",find(N,phi(N)));

    }

    return ;

}