洛谷:P1226 【模板】快速幂||取余运算(分治,数学)
程序员文章站
2022-06-22 18:58:31
题目:分析,最基本的算法,看了模板。注意一点,最后函数计算的结果要再次取余。因为 0次方取余1这个测试点。代码:#includeusing namespace std;long long a,b,c;//a的b次方,取余c long long f(long long t){ if(t==0) return 1; long long ans=f(t/2); ans=ans*ans%c; if(t%2==1) ans=ans*a%c; ret...
题目:
分析,最基本的算法,看了模板。
注意一点,最后函数计算的结果要再次取余。因为 0次方取余1这个测试点。
代码:
#include<bits/stdc++.h>
using namespace std;
long long a,b,c;//a的b次方,取余c
long long f(long long t)
{
if(t==0) return 1;
long long ans=f(t/2);
ans=ans*ans%c;
if(t%2==1) ans=ans*a%c;
return ans;
}
int main()
{
cin>>a>>b>>c;
else cout<<a<<'^'<<b<<" mod "<<c<<'='<<f(b)%c;
}
本文地址:https://blog.csdn.net/weixin_42721412/article/details/108547016