华华教月月做数学

思路

乍一看是一个快速幂的题

但是发现好像但就乘法, 都会超范围

然后,看了眼题解, 让乘法变成取模乘法就行了

做法就是 ,emm, 加法模拟乘法

int mul(int x , int k , int p)
{
    // 用加法模拟乘法, 防止溢出
    int res = 0 ;
    while(k)
    {
        if (k&1 ) res = (res + x ) % p ;
        x  =(x + x )%p;
        k>>=1;
    }
    return res ;
}

快速幂板子

int qmi (int m  ,int k ,int p)
{
    int res= 1 % p , t = m ;
    while(k)
    {
        if(k&1) res = mul(res , t , p);
        t = mul (t , t , p);
        k >>= 1;
    }
    return res;
}

ac 代码

#include<bits/stdc++.h>
using namespace std;
const int N =1e5+10;
const int inf = INT_MAX ;
typedef pair <int, int > pii;
typedef priority_queue<int ,vector<int> ,greater<int>> small_heap;
#define int long long  
int mul(int x , int k , int p)
{
    // 用加法模拟乘法, 防止溢出
    int res = 0 ;
    while(k)
    {
        if (k&1 ) res = (res + x ) % p ;
        x  =(x + x )%p;
        k>>=1;
    }
    return res ;
}
int qmi (int m  ,int k ,int p)
{
    int res= 1 % p , t = m ;
    while(k)
    {
        if(k&1) res = mul(res , t , p);
        t = mul (t , t , p);
        k >>= 1;
    }
    return res;
}
int32_t main()
{
    int T ;
    cin >>T;
    while(T--)
    {
        int a , b, p;
        cin >> a >> b>> p;
        cout <<qmi(a,b,p)<<endl;
    }
    return 0;
}