题意： 求出由全8组成的数的最短长度，使得给定的L能整除它
思路： 整除的时候要往同余的方向想，同余的时候可以往欧拉定理相关想，容易得到9L | 8*(10^x-1)，我们是希望 得到10 ^x同余1的形式，这样好解，但8和L可能有公共因子，所以两边除以个gcd(8,L),这样一来 (10 ^x-1)肯定整除9L/gcd(8,L)，就好解了，由阶的性质知，答案肯定是phi(9L/gcd(8,L))的因子，枚举即可，模数的范围超过1e9，所以要写快速乘，O(1)快速乘少了个log确实快的飞起，没解的时候其实是gcd(10,9L/gcd(8,L))==1的时候
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;} ll fac[100]; ll mul(ll a,ll b,ll p) { if(p<=1000000000)return a*b%p; else if(p<=1000000000000ll)return (((a*(b>>20)%p)<<20)+(a*(b&((1<<20)-1))))%p; } ll mypow(ll a,ll b,ll p) { ll ans=1; while(b){ if(b&1)ans=mul(ans,a,p); a=mul(a,a,p); b>>=1; } return ans; } ll divide(ll x) { ll ans=x; for(int i=2;i*i<=x;++i) { if(x%i==0){ ans=ans/i*(i-1); while(x%i==0)x/=i; } } if(x>1)ans=ans/x*(x-1); return ans; } int main() { ll l; int f=0; while(~scanf("%lld",&l)&&l) { ll t=9*l/gcd(8,l); ll sum=divide(t); int cnt=0; for(ll i=1;i*i<=sum;++i) { if(sum%i==0) { fac[++cnt]=i; if(i!=sum/i)fac[++cnt]=sum/i; } } sort(fac+1,fac+1+cnt); bool flag=0; for(int i=1;i<=cnt;++i) if(mypow(10,fac[i],t)==1) { printf("Case %d: %lld\n",++f,fac[i]); flag=1; break; } if(!flag) printf("Case %d: 0\n",++f); } return 0; }