• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

acwing 875

开发技术 开发技术 1天前 4次浏览

title: “acwing875”
author: Sun-Wind
date: September 13, 2021

acwing875

题目大意:快速幂模板题

Train of thought

此题如果采用暴力的做法时间复杂度为0(n*b);

n为样例的数目,b是幂
我们想要优化暴力的做法,首先样例的数量是没有办法改变的,用二进制的思路来进行思考幂,将幂转换成二进制数表示,可以优化时间复杂度到0(n*logb)
acwing 875
其中还运用了取模运算规则如(a*b) % p = ((a %p) * (b %p)) % p

综上所述,代码如下所示

#include<iostream>
#include<utility>
using namespace std;
typedef long long ll;
#define fi(a,b) for(int i = a; i <= b; ++i)
#define fr(a,b) for(int i = a; i >= b; --i)
using pii = pair<int,int>;
ll quick(ll a, ll b,ll p)
{
   ll res = 1;
    while(b)
    {
        if(b & 1)//取出对应的位看是否是1
            res = res * a % p;
        a = a * a % p;//相应的数进行累乘,幂增加
        b >>= 1;//通过移位继续向后检验
    }
    return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll n;
cin >> n;
while(n--)
{
    ll a,b,c;
    cin >> a >> b >> c;
    cout << quick(a,b,c) << endl;
}
return 0;
}

程序员灯塔
转载请注明原文链接:acwing 875
喜欢 (0)