欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷: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...

题目:

洛谷:P1226 【模板】快速幂||取余运算(分治,数学)

分析,最基本的算法,看了模板。

注意一点,最后函数计算的结果要再次取余。因为 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

相关标签: 分治 数学