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})
我们来转化一下这个限制条件：
令 (d=gcd(L,8))，那么（(①) 下面有注释）：
注释 (①) ：（一开始我看不懂这一步，解释一下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
",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
",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
",T,ans); return ;
} else {
printf("Case %lld: 0
",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)) 的约数。