codevs 1455 路径计算m^n%p

题目链接

题目描述 Description

小明从A1到An+1，他知道从A1到A2,从A2到A3,......,从An到An+1都有m条路,且从A1到An+1都只有这些路。小明想知道,从A1地到An+1地共有多少种方法,由于答案可能会很大,小明只要你输出总方案数mod k。

输入描述 Input Description

输入共1行,三个正整数m,n,k

输出描述 Output Description

输出共1行,表示答案

样例输入 Sample Input

3 2 100

样例输出 Sample Output

数据范围及提示 Data Size & Hint

假设从A1到A2的所有路为W1,W2,W3,从A2到A3的所有路为W4,W5,W6

方案如下：

W1>>W4
W2>>W4
W3>>W4
W1>>W5
W2>>W5
W3>>W5
W1>>W6
W2>>W6
W3>>W6
共9种方案

对于100%的数据，m,k≤1,000,000,000，n≤101,000,000

题意很明显，就是m^n%k，但是n超级大，所以我们用公式。 m^n%k = m^(n%phi(k)+phi(k))%k。一下就算出来了好神奇...

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

ll p;

ll get_phi(ll n)

{

    ll res = n,i,j;

    for(i=;i*i<=n;i++)

    {

        if(n%i==)

        {

            n=n/i;

            while(n%i==)

                n=n/i;

            res=res/i*(i-);

        }

        if(n<(i+))

            break;

    }

    if(n>)

        res = res/n*(n-);

    return res;

}

ll pow(ll a, ll b) {

    ll ret = ;

    while(b) {

        if(b&)

            ret = ret*a%p;

        a = a*a%p;

        b>>=;

    }

    return ret;

}

int main()

{

    int m;

    string n;

    cin>>m>>n>>p;

    ll phi = get_phi(p);

    ll tmp = ;

    for(int i = ; i<n.size(); i++) {

        tmp = tmp*+n[i]-'';

        tmp %= phi;

    }

    tmp += phi;

    ll ans = pow(1LL*m, tmp)%p;

    cout<<ans<<endl;

    return ;

}

codevs 1455 路径 计算m^n%p

codevs 1455 路径计算m^n%p