TOJ 3151: H1N1's Problem(歐拉降幂)

傳送門：http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=3151

時間限制(普通/Java):1000MS/3000MS     記憶體限制:65536KByte

描述

H1N1 like to solve acm problems.But they are very busy, one day they meet a problem. Given three intergers a,b,c, the task is to compute a^(b^c))%317000011. 1412, ziyuan and qu317058542 don't have time to solve it, so the turn to you for help.

輸入

The first line contains an integer T which stands for the number of test cases. Each case consists of three integer a, b, c seperated by a space in a single line. 1 <= a,b,c <= 100000

輸出

For each case, print a^(b^c)%317000011 in a single line.

樣例輸入

 2

1 1 1

2 2 2

樣例輸出

1

16

思路：

直接暴力用歐拉降幂2次來做的

歐拉降幂公式：

A^B%C=A^( B%Phi[C] + Phi[C] )%C   (B>=Phi[C])

數學方面的證明可以去：http://blog.csdn.net/Pedro_Lee/article/details/51458773  學習

注意第一次降幂的時候Mod值取的是317000011的歐拉函數值

恩，這樣用時是600MS，耗時還是很高的。

其實因為317000011是質數，它的歐拉函數值是本身減1.于是就可以轉換到下式

a^(b^c) % p = a^( (b^c)%(p-1) )%p

直接搞個快速幂就好了

給出歐拉降幂的代碼：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#define ll long long
using namespace std;
ll ol(ll x)  
{  
    ll i,res=x;  
    for(i=2;i*i<=x;i++)  
    {
        if(x%i==0)  
        {  
            res=res-res/i;  
            while(x%i==0)  
                x/=i;  
        }  
    }
    if(x>1)res=res-res/x;  
    return res;  
} //求某個值的歐拉函數值 
ll q(ll x,ll y,ll MOD)
{  
    ll res=1;  
    while(y){  
        if(y&1)res=res*x%MOD;  
        x=(x*x)%MOD;  
        y>>=1;  
    }  
    return res;
}//快速幂 
char * change(ll a){
    char s[10000];
    int ans = 0;
    while(a){
        s[ans++]=(a%10)+'0';
        a/=10;
    }
    s[ans]='\0';
    strrev(s);
    return s;
}//數字轉字元串 
char *solve(ll a,char s[],ll c){
    ll i,ans,tmp,b;
    ans=0;b=0;tmp=ol(c);
    ll len=strlen(s);  
    for(i=0;i<len;i++)b=(b*10+s[i]-'0')%tmp;  
    b += tmp;
    ans=q(a,b,c);
    return change(ans);
}//歐拉降幂 
int main()
{
    ll a,c = 317000011,b,d;
    char s[100000];
    int t;
    for(scanf("%d",&t);t--;){
        scanf("%I64d %I64d %s",&a,&b,s);
        printf("%s\n",solve(a,solve(b,s,ol(c)),c));//注意第一次降幂用的是 ol(c) 
    }
    return 0;
}      

轉載于:https://www.cnblogs.com/Esquecer/p/8527654.html