poj-3696(欧拉定理+推导)

￡神魔★判官ぃ 2022-06-08 22:46 156阅读 0赞

Description

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

8
    11
    16
    0

Sample Output

Case 1: 1
    Case 2: 2
    Case 3: 0

题目题意：题目给我们1个数L,让我们求最小的一个数满足俩个要求1：数字的每一位都是8，2：这个能被L整除。

题目分析：这个题目重在公式的推导，我们假设这个数是8\*(10^x-1)/9

即 8\*(10^x-1)/9=k\*L,我们左右俩边除以gcd(8,L) 这个非常关键。

(10^x-1)\*8/gcd(8,L)=k\*9\*L/gcd(8,L)

我们注意到  8/gcd(8,L) 与L/gcd(8,L) 肯定互质，因为8与L的最大公约数都约去了。

我们注意到8与9也是互质的，没有公共的质因子，那么8/gcd(8,L)与9\*L/gcd(8,L)互质

我们令 mod= 9\*L/gcd (8,L)

在上面的等式左右模mod ,刚刚我们证明了 8/gcd(8,L)与mod 互质，那么%mod 肯定不为0

所以我们得到了:

(10^x-1)%mod=0;

即 (10^x-1)=k\*mod

10^x=k\*mod+1

10^x=1 %mod

变形到这里，我们已经完成了推导，现在就是欧拉定理了

在 [数论][Link 1]中，欧拉定理,（也称 [费马][Link 2]\-欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为 [正整数][Link 3]，且n,a [互质][Link 4]，则: ![0823dd54564e92584b7cba389d82d158cdbf4e9f.jpg][]

所以当gcd (10,mod)==1 时，那么我们的x=phi\[mod\]，但是这个x不是最小的，我们要求得就是满足题意x最小的因子，当gcd(10,mod)!!=1时，就输出0

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #define ll long long
    using namespace std;
    
    const int maxn=1e6+10;
    int prime[maxn],cnt;
    bool vis[maxn];
    void get_prime()//打表
    {
        memset (vis,true,sizeof (vis));
        vis[1]=false;
        for (int i=2;i<maxn;i++) {
            if (vis[i]) prime[cnt++]=i;
            for (int j=0;j<cnt&&i*prime[j]<maxn;j++) {
                vis[i*prime[j]]=false;
                if (i%prime[j]==0) break;
            }
        }
    }
    
    ll gcd(ll a,ll b)
    {
        if (b==0) return a;
        return gcd( b,a%b);
    }
    
    ll get_euler(ll n)//欧拉函数
    {
        ll res=n,a=n;
        for (ll i=2;i*i<=a;i++) {
            if (a%i==0) {
                res=res/i*(i-1);
                while (a%i==0) a=a/i;
            }
        }
        if (a>1)
            res=res/a*(a-1);
        return res;
    }
    
    ll fast_muti(ll a,ll b,ll mod)//快速乘法，因为在快速幂中，乘法会炸long long
    {
        ll ans=0;
        while (b) {
            if (b&1)
                ans=(ans+a)%mod;
            a=(a+a)%mod;
            b>>=1;
        }
        return ans;
    }
    ll fast_pow(ll base,ll k,ll mod)
    {
        ll ans=1;
        while (k) {
            if (k&1)
                ans=fast_muti(ans,base,mod);
            base=fast_muti(base,base,mod);
            k>>=1;
        }
        return ans;
    }
    ll factor[1005][2],fcnt;
    void get_factor(ll n)//质因子分解
    {
        memset (factor,0,sizeof (factor));
        fcnt=0;
        for (int i=0;i<cnt&&(ll)prime[i]*prime[i]<=n;i++) {
            if (n%prime[i]==0) {
                factor[fcnt][0]=(ll)prime[i];
                while (n%prime[i]==0) {
                    factor[fcnt][1]++;
                    n=n/prime[i];
                }
                fcnt++;
            }
        }
        if (n!=1) {
            factor[fcnt][0]=n;
            factor[fcnt++][1]=1;
        }
    }
    int main()
    {
        ll l,icase=1;
        get_prime();
        while (scanf("%lld",&l)!=EOF) {
            if (l==0) break;
            ll mod=9*l/gcd (8,l);
            if (gcd(10,mod)!=1) {
                printf("Case %lld: %d\n",icase++,0);
                continue;
            }
            ll ans=get_euler(mod);
            get_factor(ans);
            for (int i=0;i<fcnt;i++) {
                for (int j=0;j<factor[i][1];j++) {//挨个去检验，如果去掉这个因子，对结果有没有影响，没有就去掉
                    if (fast_pow(10,ans/factor[i][0],mod)%mod==1) ans=ans/factor[i][0];
                }
            }
            printf("Case %lld: %lld\n",icase++,ans);
        }
        return 0;
    }

[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E8%AE%BA
[Link 2]: https://baike.baidu.com/item/%E8%B4%B9%E9%A9%AC
[Link 3]: https://baike.baidu.com/item/%E6%AD%A3%E6%95%B4%E6%95%B0
[Link 4]: https://baike.baidu.com/item/%E4%BA%92%E8%B4%A8
[0823dd54564e92584b7cba389d82d158cdbf4e9f.jpg]: https://gss2.bdstatic.com/9fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D116/sign=b4a8aa2a7dd98d1072d40830173eb807/0823dd54564e92584b7cba389d82d158cdbf4e9f.jpg