題干：

Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,C<=1000000000,1<=B<=10^1000000).

Input

There are multiply testcases. Each testcase, there is one line contains three integers A, B and C, separated by a single space.

?

Output

For each testcase, output an integer, denotes the result of A^B mod C.

?

Sample Input

3 2 4 2 10 1000

Sample Output

1 24

解題報(bào)告：

? ?裸題，僅供模板準(zhǔn)備。

AC代碼：

#include <iostream> #include <string.h> #include <stdio.h> using namespace std; const int N=1000005; typedef long long LL; char str[N]; int phi(int n) {int rea = n;for(int i=2; i*i<=n; i++) {if(n % i == 0) {rea = rea - rea / i;while(n % i == 0) n /= i;}}if(n > 1)rea = rea - rea / n;return rea; } LL multi(LL a,LL b,LL m) {LL ans = 0;a %= m;while(b) {if(b & 1) {ans = (ans + a) % m;b--;}b >>= 1;a = (a + a) % m;}return ans; } LL quick_mod(LL a,LL b,LL m) {LL ans = 1;a %= m;while(b) {if(b & 1) {ans = multi(ans,a,m);b--;}b >>= 1;a = multi(a,a,m);}return ans; } void Solve(LL a,char str[],LL c) {LL len = strlen(str);LL ans = 0;LL p = phi(c);if(len <= 15) {for(int i=0; i<len; i++)ans = ans * 10 + str[i] - '0';} else {for(int i=0; i<len; i++) {ans = ans * 10 + str[i] - '0';ans %= p;}ans += p;}printf("%I64d\n",quick_mod(a,ans,c)); } int main() {LL a,c;while(~scanf("%I64d%s%I64d",&a,str,&c))Solve(a,str,c);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【FZU - 1759】Super A^B mod C （数论，快速幂，快速乘，欧拉降幂，指数循环节，模板）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。