fzu1759

maksyuki 发表于 oj 分类，标签: 数论-欧拉定理

12 9月 2015

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

Source

FZU 2009 Summer Training IV--Number Theory

题目类型：欧拉定理降幂

算法分析：直接使用欧拉定理进行降幂处理，注意指数可能会比较大，需要从高位到低位按位取模计算

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-6;
const double PI = 2 * acos (0.0);
const int maxn = 2;

LL phi (LL val)
{
    LL res = val;
    for (LL i = 2; i * i <= val; i++)
    {
        if (val % i == 0)
        {
            res -= res / i;
            while (val % i == 0) val /= i;
        }
    }

    if (val > 1)
        res -= res / val;

    return res;
}

LL mod_f (LL a, LL b, LL p)
{
    LL res = 1, tt = (a % p + p) % p;
    while (b)
    {
        if (b & 1)
            res = res * tt % p;
        tt = tt * tt % p;
        b >>= 1;
    }
    return res;
}


int main()
{
//    CPPFF;
    LL aa, cc;
    string bb;
    while (cin >> aa >> bb >> cc)
    {
        LL tt = phi (cc);
        LL tb = 0;
        for (LL i = 0; i < bb.size (); i++)
            tb = (tb * 10 + bb[i] - '0') % tt;

        cout << mod_f (aa, tb % tt + tt, cc) << endl;
    }
    return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-6;

const double PI = 2 * acos (0.0);

const int maxn = 2;

LL phi (LL val)

{

LL res = val;

for (LL i = 2; i * i <= val; i++)

{

if (val % i == 0)

{

res -= res / i;

while (val % i == 0) val /= i;

}

if (val > 1)

res -= res / val;

return res;

}

LL mod_f (LL a, LL b, LL p)

{

LL res = 1, tt = (a % p + p) % p;

while (b)

{

if (b & 1)

res = res * tt % p;

tt = tt * tt % p;

b >>= 1;

}

return res;

}

int main()

{

// CPPFF;

LL aa, cc;

string bb;

while (cin >> aa >> bb >> cc)

{

LL tt = phi (cc);

LL tb = 0;

for (LL i = 0; i < bb.size (); i++)

tb = (tb * 10 + bb[i] - '0') % tt;

cout << mod_f (aa, tb % tt + tt, cc) << endl;

}

return 0;

}

fzu1669

uva136

一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

超客的水墨烟雨