首页 > 代码库 > Nod51 1079 中国剩余定理 Label:数论

Nod51 1079 中国剩余定理 Label:数论

2024-08-15 15:57:36   218人阅读

一个正整数K，给出K Mod 一些质数的结果，求符合条件的最小的K。例如，K % 2 = 1, K % 3 = 2, K % 5 = 3。符合条件的最小的K = 23。
 
Input
第1行：1个数N表示后面输入的质数及模的数量。（2 <= N <= 10)第2 - N + 1行，每行2个数P和M，中间用空格分隔，P是质数，M是K % P的结果。（2 <= P <= 100, 0 <= K < P)
Output
输出符合条件的最小的K。数据中所有K均小于10^9。
Input示例
32 13 25 3
Output示例
23

代码

技术分享
 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #define ll long long 6 using namespace std; 7  8 ll x,y,n,a[15],m[15]; 9 ll exgcd(ll a,ll b){10     if(b==0){11         x=1;y=0;return a;12     }13     ll g=exgcd(b,a%b);14     ll t=x;15     x=y;16     y=t-(a/b)*y;17     return g;18 }19 20 21 ll CRT()  22 {  23     ll M = 1;  24     ll ans = 0;  25     for(ll i=1; i<=n; i++)  26         M *= m[i];  27     for(ll i=1; i<=n; i++)  28     {  29         x=0, y=0;  30         ll Mi = M / m[i];  31         exgcd(Mi, m[i]);  32         ans = (ans + Mi * x * a[i]) % M;  33     }  34     if(ans < 0) ans += M;  35     return ans;  36 }  37 38 int main(){39 //    freopen("01.in","r",stdin);40     41     scanf("%d",&n);42     for(ll i=1;i<=n;i++){43         scanf("%d%d",&m[i],&a[i]);44     }45     cout<<CRT()<<endl;46     return 0;47 }
转载代码 不予展示

请在弄懂或者背下 扩展欧几里得算法，同余 的概念或代码后来看这道题

建议先去百度百科逛一圈（我已经放弃了wiki。。）

听大神讲CRT http://blog.csdn.net/acdreamers/article/details/8050018

看大神证明CRT http://blog.csdn.net/hard_man/article/details/7732795

提示，好好看~

Nod51 1079 中国剩余定理 Label:数论


联系
我们