不知道错在哪里，永远T
/* 引理：a,n互质，则满足a^x=1(mod n)的最小正整数x0是φ（n）的约数 思路：求出d=gcd(L,8) 求出φ(9L/d)的约数集合，再枚举约数x，是否满足10^x = 1 (mod 9L/d) */ #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; #define ll long long ll l,d,phi,m,factor[1000000]; ll v[1000000],prime[1000000],mm; void init(ll n){ memset(v,0,sizeof v); memset(prime, 0,sizeof prime); mm=0; for(int i=2;i<=n;i++){ if(v[i]==0){ v[i]=i; prime[++mm]=i; } for(int j=1;j<=m;j++){ if(prime[j]>v[i] || prime[j]*i>n) break; v[i*prime[j]]=prime[j]; } } } ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll f(ll n){ ll res=n;//和1互质 for(int i=1;i<=mm;i++){ if(prime[i]>n) break; if(n%prime[i]==0) res=res/prime[i]*(prime[i]-1); while(n%prime[i]==0) n/=prime[i]; } if(n>1) res=res/n*(n-1); return res; } ll mul(ll a,ll b,ll m) { ll res=0; while(b) { if(b&1) res+=a; if(res>m) res-=m; a+=a; if(a>m) a-=m; b>>=1; } return res; } ll pow(ll a,ll b,ll m) { ll res=1; while(b) { if(b&1) res=mul(res,a,m); a=mul(a,a,m); b>>=1; } return res; } int main(){ int tt=0; init(sqrt(2000000005)); while(scanf("%lld",&l),l){ d=gcd(l,8); phi=f(9*l/d); if(gcd(10,9*l/d)!=1) { printf("Case %d: 0 ",++tt); continue; } m=0; for(int i=1;i*i<=phi;i++) if(phi%i==0){ factor[++m]=i; if(i!=phi/i) factor[++m]=phi/i; } //从小到大枚举每个约数 ll mod=9*l/d,flag=0; sort(factor+1,factor+1+m); for(int i=1;i<=m;i++){ if(pow(10,factor[i],mod)%mod==1){ flag=1; printf("Case %d: %lld ",++tt,factor[i]); break; } } if(flag==0) printf("Case %d: 0 ",++tt); } return 0; }