POJ3696 The Luckiest number 非常好的数论题目 - c++编程基础

题目难度怎么说呢？就是要转很多的弯，外加一点点的运气，看到一些化简过后的式子能立马想到跟哪个定理的相似，或者符合哪个定理，弯都转过来后就好做了，操作并不是很复杂，主要就是不停地转弯转弯
10^x-1是长度为x的由9组成的，所以 8/9*（10^x-1）= L*P，就能改为由8组成的，化简 (10^x-1)=9*L*P/8; 令 m=9*L/gcd(8,L),使得9*L*P/8=m*P1，继续化简 (10^x-1)=m*P1, 接下来转化为同余方程 10^x ≡1 （mod m）,
这个式子刚好符合欧拉函数一个性质的式子， a^φ(n) ≡ 1 mod n ，所以答案肯定是 φ(n)的因子，
然后枚举φ(n) 的因子再检查模是否为1，找到最小的那个满足条件的就是最终答案了

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; // ll MOD; ll gcd(ll a,ll b) { return b==0 a:gcd(b,a%b); } ll quick(ll a,ll b) { ll ans=0; while(b) { if(b&1) ans=(ans+a)%MOD;//由于a*b可能会超所以改加法 a=a*2%MOD; b>>=1; } return ans; } ll multi(ll x) { ll ans=1; ll m=10; while(x>0) { if(x&1) ans=quick(ans,m); m=quick(m,m); x>>=1; } return ans; } int main(void) { int Case=0; while(scanf("%I64d",&MOD),MOD) { MOD=MOD*9/gcd(8,MOD); if(gcd(MOD,10) != 1) { printf("Case %d: %d\n",++Case,0); continue; } ll tmp=MOD,n=MOD; ll mp[100][2]; int k=0; for(ll i=2;i*i<=n;i++) { if(n%i==0) { tmp-=tmp/i; n/=i; while(n%i == 0) n/=i; } } if(n > 1) tmp-=tmp/n; n=tmp; for(ll i=2;i*i<=n;i++) { if(n%i==0) { mp[k][0]=i; mp[k][1]=0; n/=i; mp[k][1]++; while(n%i == 0) { n/=i; mp[k][1]++; } k++; } } if(n > 1) { mp[k][0]=n; mp[k][1]=1; k++; } for(int i=0;i