（POJ3696）The Luckiest number（好题欧拉函数+快乘）

一时失言乱红尘 2021-10-29 22:44 346阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。  
题目链接：http://poj.org/problem?id=3696  
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

Source  
2008 Asia Hefei Regional Contest Online by USTC

分析：  
欧拉定理：若a，b互质，则a^&(b) % b == 1.其中&（b）为欧拉函数（找不到那个符号的菜鸡）。

引理1：  
对于任何一个111，222……22，333……33,形如这样的数，我们都是可以用一个公式表示的。即： k \* (10^x - 1) / 9;

所以目前的可以将问题转化为：  
满足L | (8 \* (10^x - 1) / 9 )，找到最小的x。  
将公式化简：  
9L | (8 \* (10^x - 1))。  
我们令d = gcd(9L,8),然后同时两边除上d，可得：  
9L/d | (8/d \* (10^x - 1))。

9L/d 与 8/d 这两个数一定是互质的。  
故，我们可以得到9L/d 因是 (10^x - 1)的因子。可得：  
9L/d | (10^x - 1). 可得：  
10^x % （9L/d） == 1.  
至此 这个函数跟欧拉定理，就是一样的形式了。

那么我们根据欧拉定理推断  
10与（9L/d）是互质的则x一定存在&（9L/d）一定为x的取值，否则x不存在。

证明：  
若10 与 （9L/d） 不是互质的，则二者有相同的因子b为2或者5。  
若b为2 则：  
9L/d 为偶数，那么10 % （9L/d）一定不能等于1.同理可证b为5的情况。

继续根据欧拉函数推测：  
&（9L/d）可以为x的取值。但是现在要找的是最小的x。我们知道a^b % n是有循环节r的。  
r应是&（9L/d）的约数。

至此，我们目的明确了。  
求出（9L/d）的欧拉函数值，枚举他的所有约数，找到满足10^x % （9L/d） == 1.的x值。

但是要注意几个细节，快速幂要套乘法快乘。

参考博客:https://www.cnblogs.com/oneshot/p/3979847.html  
https://www.cnblogs.com/rainydays/archive/2012/11/05/2754760.html

#include"stdio.h"
    #include"string.h"
    #include"math.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    ll L;
    
    ll gcd(ll a,ll b)
    {
        if(a < b)
           {
               ll t = a; a = b; b = t;
           }
        if(b == 0)
            return a;
        return gcd(b,a%b);
    }
    ll multi(ll a,ll b,ll mod)
    {
        ll ans = 0;
        while(b)
        {
            if(b & 1)
                ans = (ans + a) % mod;
            a = (a << 1) % mod;
            b = b >> 1;
        }
        return ans;
    }
    ll Ola(ll n)
    {
        ll sum = n;
        for(int i = 2; i * i<= n; i ++)
        {
            if(n % i)
                continue;
            sum = sum / i * (i - 1);
            while(n % i == 0)
                n = n / i;
        }
        if(n != 1)
            sum = sum / n * (n - 1);
        return sum;
    }
    int Quick(ll a,ll b,ll mod)
    {
        ll ans = 1; a %= mod;
        while(b)
        {
            if(b & 1)
                ans = multi(ans,a,mod);
            b >>= 1;
            a = multi(a,a,mod);
        }
        if(ans == 1)
            return 1;
        return 0;
    }
    ll solve()
    {
        ll g = L / gcd(L,8LL) * 9;
        if(gcd(10LL,g) != 1) return 0;
        ll sum = 1;
        ll num = Ola(g);
        //这里必须将i强制转化一下，不然i*i爆int。因为这里tle了好久
        for(int i = 1; i * (ll)i <= num; i ++)
        {
            if(num % i)  continue;
            if(Quick(10LL,(ll)i,g) == 1)
                return i;
        }
        ll m = sqrt(num);
        for(int i = m; i >= 1; i --)
        {
            if(num % i == 0 && Quick(10LL,num / i,g) == 1)
                return num / i;
        }
        return 0;
    }
    
    int main()
    {
        int cnt = 1;
        while(~scanf("%lld",&L))
        {
            if(L == 0)  break;
            printf("Case %d: %lld\n",cnt ++,solve());
        }
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/