HDU2837 Calculation 指数循环节欧拉函数+快速幂

快期末了要复习，但是做数论需要时间来累积，所以保持每天做做题目

依旧是这个公式的应用，关于 A^x = A^(x % Phi(C) + Phi(C)) (mod C) 的若干证明】【指数循环节】

对于求指数循环节基本都会用到这个公式，或者求一个 A^B （B非常非常大的时候也要用到这个公式），但是要注意的是这里的X要较大才可以用这个公式，所以在快速幂取模的时候要注意区分 x是否较大

#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; // const int N=30010; ll prime[N]; bool isprime[N]; ll cnt; void init()//这段求出了N内的所有素数 { ll i,j; for(i=2;i<=N;i++) { if(!isprime[i]) prime[cnt++]=i; for(j=0;j
                    
                     1) ans=ans/tempn*(tempn-1); return ans; } ll quick(ll a,ll b,ll m) { ll ans=1; ll now=1; for(int i=0;i
                     
                      = m) break; } if(now >= m) now=m; else now=0; while(b) { if(b&1) { ans=(ans*a)%m; b--; } b>>=1; a=a*a%m; } return ans+now; } ll dfs(ll n,ll m)//递归求解 { if(n==0) return 1; ll tmp=euler(m); ll p=dfs(n/10,tmp); ll ans=quick(n%10,p,m); return ans; } int main(void) { init(); int t; ll n,m; scanf(%d,&t); while(t--) { scanf(%I64d %I64d,&n,&m); ll ans=dfs(n,m); printf(%I64d ,ans%m); } } /* 2 24 20 25 20 */

HDU2837 Calculation 指数循环节 欧拉函数+快速幂