FZU Super A^B mod C（欧拉函数降幂）

Problem 1759 Super A^B mod C

Accept: 878    Submit: 2870
Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

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

 Source

FZU 2009 Summer Training IV--Number Theory

题目链接：FZU 1759

参考博客：http://blog.****.net/acdreamers/article/details/8236942，本来在搞蛇精病的十进制快速幂的时候做的这个，结果超时了，后来测试发现十进制快速幂还没二进制快……是我太天真了……于是膜一下正确解法，主要利用了这个欧拉定理的扩展公式，当然最重要的是求出一个数的欧拉函数值$phi(x)$，这个可以用埃式筛的思想求得。

代码：

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <sstream>
#include <numeric>
#include <cstring>
#include <bitset>
#include <string>
#include <deque>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1000010;

LL bpow(LL a, LL b, LL mod)
{
    LL r = 1LL;
    while (b)
    {
        if (b & 1)
            r = ((r % mod) * (a % mod)) % mod;
        a = ((a % mod) * (a % mod)) % mod;
        b >>= 1;
    }
    return r;
}
LL phi(LL n)
{
    LL r = n, sz = sqrt(n);
    for (LL i = 2; i <= sz; ++i)
    {
        if (n % i == 0)
        {
            r = r * (i - 1) / i;
            while (n % i == 0)
                n /= i;
        }
    }
    if (n > 1)
        r = r * (n - 1) / n;
    return r;
}
int main(void)
{
    LL a, c;
    char B[N];
    while (~scanf("%I64d%s%I64d", &a, B, &c))
    {
        LL phi_c = phi(c);
        int len = strlen(B);
        LL b;
        if (len <= 20)
        {
            sscanf(B, "%I64d", &b);
            if (b >= phi_c)
                b = b % phi_c + phi_c;
        }
        else
        {
            b = 0LL;
            for (int i = 0; i < len; ++i)
            {
                b = b * 10LL + B[i] - '0';
                if (b > phi_c)
                    b %= phi_c;
            }
            b += phi_c;
        }
        printf("%I64d\n", bpow(a, b, c));
    }
    return 0;
}