我真的一写博客我就难受 但是不写又感觉自己没学进去
都已经这个时候了快速幂我都写不快 码字速度还星一敲代码我就废
还是练习太少了 自己好好反思 但愿还能补救一下
回到正题
题目描述
输入b,p,k的值,求b^p mod k的值。其中b,p,k*k为长整型数。
输入格式
三个整数b,p,k.
输出格式
输出“b^p mod k=s”
s为运算结果
就很简单粗暴的题...一是用快速幂 二是用余数的规律解
说一下第二种方法,手动模拟一下会发现累乘的每一步对k取余得到的余数具有周期性,将周期长度算出,对周期长度取余然后再算一遍就能得到对应的余数。
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ll b,p,k,ans=1; ios::sync_with_stdio(0); cin>>b>>p>>k; cout<<b<<"^"<<p<<" mod "<<k<<"="; while(p>0){ if(p&1)ans=ans*b%k; b=b*b%k; p>>=1; } cout<<ans%k<<endl; return 0; }