题目描述

建议poj上提交一下，acwing数据水了
http://poj.org/problem?id=3696

样例

blablabla

算法1

分析：
欧拉定理：若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值。

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

C++ 代码

#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);
    // printf("g = %lld num = %lld\n",g,num);
    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());
    }
}