51nod 1079中国剩余定理

心已赠人 2022-05-22 02:11 259阅读 0赞

[1079 中国剩余定理][1079] ![ok.png][]

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 [难度：基础题][Link 1]

![star.png][] 收藏

![plus.png][] 关注

一个正整数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示例

3
    2 1
    3 2
    5 3

Output示例

中国剩余定理是用来解决模线性方程组问题的

![(S) : \\quad \\left\\\{ \\begin\{matrix\} x \\equiv a\_1 \\pmod \{m\_1\} \\\\ x \\equiv a\_2 \\pmod \{m\_2\} \\\\ \\vdots \\qquad\\qquad\\qquad \\\\ x \\equiv a\_n \\pmod \{m\_n\} \\end\{matrix\} \\right.][S_ _ _quad _left_ _begin_matrix_ x _equiv a_1 _pmod _m_1_ _ x _equiv a_2 _pmod _m_2_ _ _vdots _qquad_qquad_qquad _ x _equiv a_n _pmod _m_n_ _end_matrix_ _right.]

求出 x 满足这个等式

![70][]

![70 1][]

[wiki传送][wiki]

第一种方法：

直接写

#include<cstdio>
    #include<cstring> 
    #include<algorithm>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    const int maxn=11;
    
    int main()
    {
    	int n;
    	while(~scanf("%d",&n))	
    	{
    		ll a[maxn],m[maxn];
    		ll lcm=1;
    		ll ans=0;
    		for(int i=0;i<n;i++)
    		{
    			scanf("%lld %lld",&a[i],&m[i]);
    			lcm*=a[i];
    		}
    		for(int i=0;i<n;i++)
    		{
    			int j=1;
    			ll M=lcm/a[i];
    			if(M%a[i]!=0)
    				for(j=1;j*M%a[i]!=1;j++);
    			ans+=M*m[i]*j;
    		}
    		printf("%lld\n",ans%lcm);
    	}
    	return 0;
    }

第二种，利用exgcd

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    const int maxn=105;
    int n;
    ll m[maxn],p[maxn];
    ll exgcd(ll a,ll b,ll &x,ll &y)
    {
    	if(!b)
    	{
    		x=1;
    		y=0;
    		return a;
    	}
    	int r=exgcd(b,a%b,y,x);
    	y-=x*(a/b);
    	return r;
    }
    ll CRT(ll *m,ll *a)
    {
    	ll M=1,ans=0;
    	for(int i=0;i<n;i++)
    		M*=m[i];
    	for(int i=0;i<n;i++)
    	{
    		ll mi=M/m[i],x,y;
    			exgcd(mi,m[i],x,y);	//要注意为止不能放反。。。 
    		ans=(ans+x*mi*a[i])%M;	
    	}
    	return (ans+M)%M;
    }
    int main()
    {
    
    	while(~scanf("%d",&n))
    	{
    		for(int i=0;i<n;i++)
    			scanf("%lld %lld",m+i,p+i);
    		printf("%lld\n",CRT(m,p));
    	}
    	return 0;
    }

[1079]: https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1079
[ok.png]: https://file.51nod.com/images/icon/ok.png
[Link 1]: https://www.51nod.com/onlineJudge/problemList.html#!groupId=1
[star.png]: https://file.51nod.com/images/icon/star.png
[plus.png]: https://file.51nod.com/images/icon/plus.png
[S_ _ _quad _left_ _begin_matrix_ x _equiv a_1 _pmod _m_1_ _ x _equiv a_2 _pmod _m_2_ _ _vdots _qquad_qquad_qquad _ x _equiv a_n _pmod _m_n_ _end_matrix_ _right.]: https://wikimedia.org/api/rest_v1/media/math/render/svg/b3e3b83a47f7942fa7337d9157658625d6685ef0
[70]: /images/20220522/ba8f3fd8b01d45108031b5d33ee9438d.png
[70 1]: /images/20220522/bc609ba447634251bfe3f6e81e07743a.png
[wiki]: https://zh.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E5%89%A9%E4%BD%99%E5%AE%9A%E7%90%86