前一阵子听说有一个神题，题意大概是这样：求a^b%c。a,c<=10^9,b<=10^1000000。
以前一听就知道我该跪了。 但是，由于上次安叔讲过这个类型的题目，所以我还是略知一二的，看过安叔的课件，参考过安叔的代码后我就把这个题目给a掉了。
题目的编号：FZU1759
解决这个问题用到了一个最最关键的定理：扩展欧拉定理
定理描述为：a^(x+x%phi(m))=a^x(mod m); x>=phi(m);phi(m)为m的欧拉函数值
也就是说如果x>=phi(m)，那么a^(x%phi(m))=a^x(mod m) 即a^(x%phi(m))与a^x同余、
这样的话这个有题目就可以完美地解决掉了呢。
啥都不说了，直接上代码咯！
＃i nclude <iostream>
＃i nclude <cstdio>
#define maxn 1000010
#define ll long long
using namespace std;
char s[maxn];
ll a,b,c,t;
ll phi(ll x)
{
ll ans=x;
for (ll i=2; i*i<=x; i++)
{
if (x%i==0) ans=ans/i*(i-1);
while (x%i==0) x/=i;
}
if (x!=1) ans=ans/x*(x-1);
return ans;
}
ll getmod()
{
ll ans=0;
for (ll i=0; s[i]; i++)
{
ans=ans*10+s[i]-'0';
if (ans>t) ans%=t;
}
return ans;
}
ll q_p_m(ll a,ll b,ll c)
{
ll ans=1;
while (b)
{
if (b&1) ans*=a;
b>>=1;
a=a*a;
if (ans>c) ans%=c;
if (a>c) a%=c;
}
return ans;
}
int main()
{
while (scanf("%I64d%s%I64d",&a,s,&c)!=EOF)
{
t=phi(c);
b=getmod()+t;
printf("%I64d\n",q_p_m(a,b,c));
}
return 0;
}
1
个人表示程序中，我没有对x和phi(m)的值做比较，但是依然AC了。我也觉得很奇怪呢！
不过安叔说了，该定理是被证明过的，所以以后用的话还是要验证一下x和phi(m) 值的大小呢。
以后多多注意，加油。
