首页 > 代码库 > hdu 1370 中国剩余定理
hdu 1370 中国剩余定理
题意 :求一个最小的数对 23 38 33 于i p e
zsd: 因为23 38 33 两两互素所以可以用中国剩余定理
是中共剩余定理的经典模板
#include <iostream> using namespace std; int exgcd(int a,int b,int &x,int &y) { if(a==0) { x=0; y=1; return b; } int g = exgcd(b%a,a,x,y); int tem = y; y=x; x=tem-(b/a)*y; return g; } int inv(int a,int n)//求逆元 { int x,y; exgcd(a,n,x,y); return (x%n+n)%n; } int main() { int N,P,E,I,D,ans; const int m1=23,m2=28,m3=33,M1=28*33,M2=23*33,M3=23*28,m=23*28*33; const int M11 = inv(M1,m1),M22 = inv(M2,m2),M33 = inv(M3,m3);//求mi的逆元 scanf("%d",&N); while(scanf("%d%d%d%d",&P,&E,&I,&D)!=EOF) { if(P==-1&&E==-1&&I==-1&&D==-1)break; //a[i]*(mi*mi(逆)mod ni)因为在求逆元的时候已经mod ni了 //(mi*mi(逆)mod ni)是ci ans = (P*M1*M11 + E*M2*M22 + I*M3*M33)%m; ans -= D; if(ans<=0) ans+=m; printf("Case %d: the next triple peak occurs in %d days.\n",N++,ans); //cout<<"Case "<<N++<<": the next triple peak occurs in "<<i<<" days.\n"; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。