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

 Problem Description

 Input

 Output

 Sample Input

 Sample Output

 Source

FZU 2009 Summer Training IV--Number Theory

#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;

}