acm数论题目 a^b^c mod 1000000007 如何快速幂.数据范围三个数都小于 1000000000.

acm数论题目 a^b^c mod 1000000007 如何快速幂.数据范围三个数都小于 1000000000.

#include
typedef __int64 lld;
lld mod(lld a,lld b,lld m)
{
\x05lld ret=1;
\x05a%=m;
\x05while(b)
\x05{
\x05\x05if(b&1)ret=ret*a%m;
\x05\x05b>>=1;
\x05\x05a=a*a%m;
\x05\x05//printf(b=%I64d\n,b);
\x05}
\x05return ret;
}
int main()
{
\x05lld a,b,c;
\x05lld m = 1000000007;
\x05while(scanf(%I64d%I64d%I64d,&a,&b,&c)!=EOF)
\x05{
\x05\x05b=mod(b,c,m-1);//应该用费马小定理,把b^c先降下来
\x05\x05a=mod(a,b,m);
\x05\x05printf(%I64d\n,a);
\x05}
\x05return 0;
}
再问： 大侠 ，费马小定理 能否稍微解释一下。
再答： 恩，就是欧拉函数知道吗？ 1000000007是一个素数 如果(a,b)=1 那么 a^c%b=a^(c%(phi(b)))%b phi(b) 是指b的欧拉函数，就是比b小的数字中有多少个数和b的公因子是1。 素数的欧拉函数是自身减一。其他的你自己去具体看看一下相关知道吧

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息