首页 > 代码库 > 1079 中国剩余定理
1079 中国剩余定理
1079 中国剩余定理
例如,K % 2 = 1, K % 3 = 2, K % 5 = 3,可以先令一个值等于5+3,然后依次加五直到8求余等于2时,在依次加15直到23求余2等于1,就求出答案了。
1 #include <iostream> 2 #include <algorithm> 3 #include <stdio.h> 4 using namespace std; 5 struct Nod{ 6 int p,m; 7 }nod[11]; 8 bool cmp(Nod a, Nod b){ 9 return a.p > b.p; 10 } 11 int main(){ 12 int n; 13 cin>>n; 14 for(int i = 0; i < n; i ++) cin>>nod[i].p>>nod[i].m; 15 sort(nod,nod+n,cmp); 16 int ans = nod[0].m, cnt = 1; 17 for(int i = 1; i < n; i ++){ 18 cnt = cnt/__gcd(cnt,nod[i-1].p)*nod[i-1].p; 19 while((ans%nod[i].p) != nod[i].m){ 20 ans+=cnt; 21 } 22 } 23 cout << ans << endl; 24 return 0; 25 }
不过由于每一个p都之间的最大因子都是1,所以就不需要求最大公倍数这么麻烦了。
1 #include <iostream> 2 #include <algorithm> 3 #include <stdio.h> 4 using namespace std; 5 struct Nod{ 6 int p,m; 7 }nod[11]; 8 int main(){ 9 int n; 10 cin>>n; 11 for(int i = 0; i < n; i ++) cin>>nod[i].p>>nod[i].m; 12 int ans = nod[0].m, cnt = 1; 13 for(int i = 1; i < n; i ++){ 14 cnt = cnt*nod[i-1].p; 15 while((ans%nod[i].p) != nod[i].m){ 16 ans+=cnt; 17 } 18 } 19 cout << ans << endl; 20 return 0; 21 }
1079 中国剩余定理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。