首页 > 代码库 > Raising Modulo Numbers(ZOJ 2150)
Raising Modulo Numbers(ZOJ 2150)
这是题目的答案
#include<iostream>#include<cmath>using namespace std;int a[45002];int b[45002];int mod(int a, int b, int c){ int z = 1; while(b) { if(b%2) z = (z*a)%c; b/=2; a = (a*a)%c; } return z;}int main(){ int T; cin>>T; while(T--) { int M; int H; cin>>M>>H; for(int i=0; i<H; i++) { cin>>a[i]>>b[i]; } int t =0; int mode = 0; while(t<H) { int tem0 = a[t]%M; mode = (mod(tem0,b[t],M) + mode)%M; t++; } cout<<mode<<endl; }}
只分析求幂—模的那个函数，先举例吧（a a a a a a a a a a）这是b个a （b =10），通过z来记录二分时多出来的一个a，每次二分后用a来代替a*a，这样就得到了缩小规模的结果。最后肯定是b=1，所以这时只需用现在的a与z结合就是最后的结果了。
int mod(int a, int b, int c){ int z = 1; while(b) { if(b%2) z = (z*a)%c; b/=2; a = (a*a)%c; } return z;}
这个函数的写法就是二分法而已，但是刚开始时我写的是这样的
long long F(long long a, long long b, long long m){ if(b==1) return a%m; else if(b%2==0) return (F(a,b/2,m)*F(a,b/2,m))%m; else return (F(a,b/2,m)*F(a,b/2,m)*a%m);}
这样写的结果是RE，估计是递归太深导致堆栈溢出了，这个写的很差，根本没有起到二分的效果，反而比O(n)还要费时间。
Raising Modulo Numbers(ZOJ 2150)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。