Java教程

ADV-1117 超级快速幂(数论)

本文主要是介绍ADV-1117 超级快速幂(数论),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

问题描述

  给出a,b,c。令p=1000000007, z=b^c, y=a^z, x=y mod p。请求出x。

输入格式

  三个整数分别是a,b,c

输出格式

  请输出x

数据规模和约定

  abc都不超过10^9

思路

不能使用a^(b^c%mod)%mod
考虑费马小定理
当a和p互质时, a ^ (p - 1) % p = 1
最后的结论是a^(b^c) % mod = a^(b^c%(mod - 1)) % mod
先是一个结论:a = b * (a / b) + a % b
div = (b ^ c) / (mod - 1) rem = (b ^ c) % (mod - 1)
a^(b^c) % mod = a ^ ((mod - 1) * div + rem) % mod
由于a小于1e9,mod=1e9+7, mod是质数,a和mod互质,满足费马小定理
所以,a^(b^c) % mod = a ^ rem % mod

#include <iostream>

using namespace std;

const int p = 1000000007;
typedef long long LL;

int qmi(int a, int k, int mod)
{
    int res = 1;
    while(k)
    {
        if(k & 1)
        {
            res = (LL)res * a % mod;
        }
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    int z = qmi(b, c, p - 1);
    int y = qmi(a, z, p);
    cout << y;
    return 0;
}
这篇关于ADV-1117 超级快速幂(数论)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!