TOJ 3151: H1N1's Problem(欧拉降幂)-白红宇

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

阅读量：5352 次

发布时间：2019-06-15

本文共 1560 字，大约阅读时间需要 5 分钟。

传送门：

时间限制(普通/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.

样例输入

1 1 1

2 2 2

样例输出

思路：

直接暴力用欧拉降幂2次来做的

欧拉降幂公式：

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

数学方面的证明可以去：学习

注意第一次降幂的时候Mod值取的是317000011的欧拉函数值

恩，这样用时是600MS，耗时还是很高的。

其实因为317000011是质数，它的欧拉函数值是本身减1.于是就可以转换到下式

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

直接搞个快速幂就好了

给出欧拉降幂的代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long longusing 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

转载于:https://www.cnblogs.com/Esquecer/p/8527654.html

你可能感兴趣的文章