FZU1759 Super A^B mod C

• 板子题，(1<=A,C<=1000000000,1<=B<=10^1000000)，求 (A^B)modC 的值
• 欧拉降幂，sqrt(c)求欧拉函数，还用到了快速幂
• 欧拉降幂就是左边这个公式了
• 如果AC互质的话直接用欧拉定理这个公式降幂
• 代码
  

   1 #include <cstdio>
   2 #include <iostream>
   3 #include <algorithm>
   4 #include <cstring>
   5 #include <cmath>
   6 #define nmax 1000010
   7 
   8 using namespace std;
   9 typedef long long ll;
  10 char b[nmax];
  11 ll a,c,cc;
  12 
  13 ll gcd(ll x,ll y){
  14     if(y==0) return x;
  15     else return gcd(y,x%y);
  16 }
  17 
  18 ll phi(ll x){
  19     ll t=sqrt(x),ans=1,t2=x;
  20     for (ll i=2; i<=t; i++) {
  21         if(x%i) continue;
  22         t2/=i;
  23         ans*=(i-1);
  24         while(x%i==0) x/=i;
  25         if(x==1) break;
  26     }
  27     if(x>1) { ans*=(x-1); t2/=x; } //有个因数大于sqrt
  28     ans*=t2;
  29     return ans;
  30 }
  31 
  32 ll quickpow(ll x,ll y){  //x^y%c
  33     if(y==0) return 1;
  34     if(y==1) return x%c;
  35     ll t=quickpow(x,y/2);
  36     if(y%2) return (t*t%c)*x%c;
  37     else return t*t%c;
  38 }
  39 
  40 int main(){
  41     while( scanf("%I64d%s%I64d",&a,b,&c)!=EOF){
  42         ll d=gcd( max(a,c),min(a,c) );
  43         cc=phi(c);
  44         int l=strlen(b);
  45         ll t=0;//t==b%phi(c)
  46         for (int i=0; i<l; i++) {
  47             t*=10;
  48             t+=(b[i]-‘0‘)%cc;
  49             t%=cc;
  50         }
  51         if(d==1) printf("%I64d\n",quickpow(a,t));//a^(b%phi(c))modc
  52         else{
  53             if(l<=10) {
  54                 ll nb=0;
  55                 for (int i=0; i<l; i++) { nb*=10; nb+=(b[i]-‘0‘); }
  56                 printf("%I64d\n",quickpow(a,nb));
  57             }else{  //a^(b%phi(c)+phi(c))modc
  58                 printf("%I64d\n",quickpow(a,t+cc));
  59             }
  60         }
  61     }
  62     return 0;
  63 }

  (╥╯^╰╥)

   

• 这题提交之后编译错误不给提示。。。看看评论吧https://vjudge.net/problem/FZU-1759

那些需要疯狂降幂的题目（欧拉降幂，快速幂）

原文：https://www.cnblogs.com/jiecaoer/p/11442358.html