Problem A: 高次同余Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 43  Solved: 4[Submit][Status][Web Board]Description在数论专题时我给大家讲过快速模幂，但是今天的题目只用快速模幂算法是解决不了的，A^B mod C 中如果B很大怎么处理呢？ 想想我数论专题讲的其他内容吧！我的题目就是要你编程求出A^B mod C的值是多少。 Input有多组测试数据，每组测试数据为一行包括三个数A，B，C由一个空格分开。 (1<=A,C<=1000000000,1<=B<=10^10000).Output 对于每组测试数据，输出一个整数，代表A^B mod C的结果。Sample Input3 2 4 3 4 5 2 10 1000 3 1000000000 7Sample Output1 1 24 4HINT提示：x≥? (n)时，ax≡a(x mod ?(n)+ ?(n)) (mod n)

定义：在数论，对正整数n，欧拉函数是小于等于n的数中与n互质的数的数目。? (n) =   1..n中与n互质的数的个数如何求? (n)？素因子展开+容斥原理令n = p1r1p2r2...pkrk?(n)=n*(1-1/p1)*(1-1/p2)*...*(1-1/pk)（为什么？）提示：欧拉函数是积性函数——若m,n互质，即：  φ(mn)=φ(m)φ(n)“被认为是数学世界中最美妙的定理之一”若a和n互质，则a?(n)≡1 (mod n)  （a的?(n)次方）欧拉定理的推广形式当x≥? (m)时，ax≡a(x mod ?(n)+ ?(n)) (mod n)不需要互素用途：计算高阶幂次取模（如何计算？）

#include<stdio.h> #include<string> #include<iostream> using namespace std; #define eps 1e-8 int Eler(int n) {     int i;     double tmp=(double)n;     for(i=2;i*i<=n;i++)     {         if(n%i==0)         {             tmp*=(1-1.0/i);             while(n%i==0)                 n/=i;         }     }     if(n>1)         tmp*=(1-1.0/n);     tmp+=eps;     return (int)tmp; } int Mod(string b,int q) {     int ret=0;     for(int i=0;i<b.length();i++)     {         ret=ret*10+b[i]-‘0‘;         ret%=q;     }     ret%=q;     return ret; } long long multy(long long q, long long n,int mod) {     long long cnt = n;     long long base = q;     long long ret = 1;     while(cnt > 0)     {         if(cnt & 1)             ret = (long long)ret*base%mod;         cnt = cnt >> 1;         base = (long long)base*base%mod;     }     return ret; } int main() {     int a,c;     string b;     int i;     while(cin>>a>>b>>c)     {         int el=Eler(c);         int tmp=0;           for(i=0;i<b.length();i++)         {             tmp=tmp*10+b[i]-‘0‘;             if(tmp>el)break;         }         if(tmp>el)tmp=Mod(b,el)+el;         //else tmp;         long long ans=multy((long long)a%c,(long long)tmp,c);           printf("%lld\n",ans);         b.clear();     }     return 0; }