Super A^B mod C FZU - 1759 （数论）

https://vjudge.net/problem/FZU-1759

昨天打焦作赛G题没做出来，朋友告诉我要用欧拉降幂，发现用欧拉降幂->快速幂取模->同余模定理...一系列数论基础知识我都不太会，今天就来补补课，发现数论真的好神奇~

首先需要知道一个定理：同余模定理。

同余模定理：积和差的取余等于取余的积和差的取余，即：

                (a+b)%c = ((a%c)+(b%c))%c

                (a-b)%c = ((a%c)-(b%c))%c

                (a*b)%c = ((a%c)*(b%c))%c

通过同余模定理可以退出快速幂取模的算法，一些范围不太大的取模这样也就够了，可像此题中10e100000这么大的范围是需要另外一个知识的：欧拉降幂。

说到欧拉降幂就必须要提到欧拉函数，欧拉函数是小于或等于n的正整数中与n互质的数的数目（如φ(1)=1），算法模板在下面

但对于此题中1e100000这么大的范围，降一次幂肯定是不够的，这就又用到了同余模定理中的(a+b)%c = ((a%c)+(b%c))%c

把B作为char数组储存下来，然后根据位数来拆分，10e100000的复杂度就变成100000复杂度了~一秒过没问题

数论真的是太神奇了！

//Super A^B mod C
#include<cstdio>
#include<cstring>
using namespace std;typedef long long LL;
const LL maxn = 1000050;
LL A, C;
char B[maxn];
LL pow_mod(LL a,LL b,LL mod)
{  //快速幂取模模板LL s=1;while(b){if(b&1) s=(s*a)%mod;a=(a*a)%mod;b=b>>1;}return s;
}
LL get_phi(LL x)
{  //欧拉函数模板LL i,ans=x;for(i=2;i*i<=x;i++) if(x%i==0){ans-=ans/i;while(x%i==0) x/=i;}if(x>1) ans-=ans/x;return ans;
}int main()
{while(scanf("%lld %s%lld",&A,B,&C) != EOF){LL len = strlen(B)-1, phi = get_phi(C), tmp = 0;for(int i = 0; i <= len; i++){tmp = ((B[i]-'0')+(tmp*10)); //同余模定理if(tmp > C) break;}if(tmp <= C) printf("%lld\n",pow_mod(A,tmp,C)); //当B小于C直接快速幂else{tmp = 0;for(int i = 0; i <= len; i++) //当B大于等于C时欧拉降幂tmp = ((B[i]-'0')+(tmp*10)) % phi;printf("%lld\n",pow_mod(A, tmp+phi, C));}memset(B,0,sizeof(B));}return 0;
}