博客园阅读地址

Problem

ACwing 题目地址 （听说这里的数据已经加强到POJ这个水平了，毒瘤数据恶心死了）

Solution

这里学会两个 引理/性质：

$1.$ 由 $x$ 个 $y$ 组成的数的公式是 $y*\frac{10^x-1}{9}$。比如 $88888888$ 这种数。

$2.$ 若正整数 $a,n$ 互质，则满足 $a^x \equiv 1 \pmod n$ 的最小正整数 $x_0$ 是 $φ(n)$ 的约数。

证明一下第二条性质：

证明方法：反证法，调整法。
证明：
假设性质二不成立，也就是 $x_0$ 可能不是 $φ(n)$ 的约数。
首先 $x_0 < φ(n)$。如果 $x_0 > φ(n)$，那么 $φ(n)$ 才是最小符号条件的 $x_0$。
假设 $φ(n)=k*x_0+r$，根据欧拉定理，$a^{φ(n)} \equiv 1 \pmod n$。
又有 $a^{x_0} \equiv 1 \pmod n$，所以 $a^{k*x_0} \equiv 1 \pmod n$。
又因为 $a^{φ(n)}=a^{k*x}*a^r$，所以 $a^r \equiv 1 \pmod n$
根据余数的定义 $1<=r<x_0$，故 $x_0$ 不是最小的符合条件的正整数。
如此往复迭代调整，直到 $r=0$，才无法继续调整，此时 $x_0$ 是 $φ(n)$ 的约数。
证毕。

有了这两个性质，我们就可以开始推导题目了。

题目实际上要我们求一个最小的正整数 $x$，满足 $L \ | \ 8*\frac{10^x-1}{9}$

我们来转化一下这个限制条件：

$$\Leftrightarrow 9*L \ | \ 8*(10^x-1)$$

令 $d=gcd(L,8)$，那么（$①$ 下面有注释）：

$$\Leftrightarrow \frac{9*L}{d} \ | \ 10^x-1$$

$$\Leftrightarrow 10^x-1 \equiv 0 \pmod{\frac{9*L}{d}}$$

$$\Leftrightarrow 10^x \equiv 1 \pmod{\frac{9*L}{d}}$$

注释 $①$ ：（一开始我看不懂这一步，解释一下qwq）首先 $\frac{9*L}{d}$ 与 $\frac{8}{d}$ 是互质的，所以 $\frac{9*L}{d}$ 一定是 $10^x-1$ 的因数，所以 $\Leftrightarrow \frac{9*L}{d} \ | \ 10^x-1$

根据上面的 性质$2$，我们可以试除法找约数判断答案是否可行解决这个题目。时间复杂度（假设 $N$ 组数据 $O(N*\sqrt{L} \log^2 L)$）。（为什么时间复杂度带两个 $\log$？我才不会告诉你这个题目毒瘤数据要写快速乘法，所以快速幂里面套一个快速乘）

我的求欧拉函数和大家的有点区别。。

Code

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
int L,mod,ans,pm;
int gcd(int a,int b) {
    return (b==0?a:gcd(b,a%b));
}
int Phi(int n) {
    if(n == 1) return 1;
    int res = 1;
    for(int i=2;i<=sqrt(n);++i) {
        if(n % i == 0) {
            res *= (i-1); n /= i;
            while(n % i == 0) {
                res *= i; n /= i;
            }
        }
    }
    if(n > 1) res *= (n-1);
    return res;
}
int Mul(int x,int y) {
    int res = 0, base = x;
    while(y) {
        if(y&1) res = (res+base)%mod; base = (base<<1)%mod; y >>= 1;
    }
    return res;
}
int Pow(int x,int y) {
    int res = 1, base = x;
    while(y) {
        if(y&1) res = Mul(res,base); base = Mul(base,base); y >>= 1;
    }
    return res;
}
void work(int T) {
    mod = 9*(L/gcd(L,8)), pm = Phi(mod);
    //printf("%d %d\n",mod,pm);
    bool flag = 0;
    for(int i=1;i<=sqrt(pm);++i)
        if(pm % i == 0 && Pow(10,i) == 1) {
            flag = 1; ans = i; break;
        }
    if(flag) {
        printf("Case %lld: %lld\n",T,ans); return ;
    }
    for(int i=sqrt(pm);i>=1;--i)
        if(pm % i == 0 && Pow(10,pm/i) == 1) {
            flag = 1; ans = pm/i; break;
        }
    if(flag) {
        printf("Case %lld: %lld\n",T,ans); return ;
    } else {
        printf("Case %lld: 0\n",T);
    }
}
signed main()
{
    //test();
    for(int i=1;i;++i) {
        L = read();
        if(!L) break;
        work(i);
    }
    return 0;
}

Summary

学到了两个性质，最重要的是性质二：

• 若正整数 $a,n$ 互质，则满足 $a^x \equiv 1 \pmod n$ 的最小正整数 $x_0$ 是 $φ(n)$ 的约数。