CRT/EXCRT

孙子定理是中国古代求解一次同余式组(见同余)的方法。是数论中一个重要定理。 又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期(公元5世纪)的数学著作《孙子算经》卷下第二十六题,叫做“物不知数”问题, 原文如下: 有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何? 即,一个整数除以三余二,除以五余三,除以七余二,求这个整数。《孙子算经》中首次提到了同余方程组问题, 以及以上具体问题的解法,因此在中文数学文献中也会将中国剩余定理称为孙子定理。 具体的解法可以去参考以下链接 这里 还有 这里 其实就是对于一个多次同余方程的求解 可以举个例子用数学方法算一下 例五:三三数之剩二,五五数之剩三,七七数之剩二。问物几何? CRT/EXCRT
即,一个整数除以三余二,除以五余三,除以七余二,求这个整数。
除以3余2和除以7余2的数可以写成21n+2。
21n+2除以5余3,要求21n除以5余1。
21n除以5余1,21除以5余1,要求n除以5余1
(乘数之余等于余数之乘),则n最小取1。
所以满足“除以3余2,除以5余3,除以7余2”的最小的数是21×1+2=23。

标准解法:先从3和5、3和7、5和7的公倍数中相应地找出分别被7、5、3除均余1的较小数15、21、70 ( 注释:此步又称为求"模逆"运算,利用扩展欧几里得法并借助计算机编程可比较快速地求得.当然,对于很小的数,可以直接死算 )。即

15÷7=2……余1,
21÷5=4……余1,
70÷3=23……余1.
再用找到的三个较小数分别乘以所要求的数被7、5、3除所得的余数的积连加,
15×2+21×3+70×2=233. (将233处用i代替,用程序可以求出)
最后用和233除以3、5、7三个除数的最小公倍数.
233÷105=2……余23,
这个余数23就是合乎条件的最小数.
答案

对于这个我们有两种算法 

1 大数翻倍法

#include<algorithm>
//会用到一个很神奇滴函数,加着
#include<iostream>
using namespace std;
long long n,a[11],b[11],i,ans,c;
//用long long定义
long long zxgbs(long long a,long long b)
{ return a*b// __gcd(a,b); } //求最小公倍数 int main(){ cin>>n; for(i=1;i<=n;i++) cin>>a[i]>>b[i]; //输入部分,不说了 c=a[1];ans=b[1]; //第一次建立不用循环,直接写进去 for(i=2;i<=n;i++) { for(;ans%a[i]!=b[i];) ans+=c; //ans暴力往上加,加到符合这次的标准 c=zxgbs(c,a[i]); //用函数把a[i]加进去,后面每次加的都要是这次的倍数 } cout<<ans; //输出结果 return 0; }

  2.EX—gcd

#include<cstdio>
#define ll long long
ll n,a[16],m[16],Mi[16],mul=1,X;
inline int rd(){
    int io=0;char in=getchar();
    while(in<'0'||in>'9')in=getchar();
    while(in>='0'&&in<='9')io=(io<<3)+(io<<1)+(in^'0'),in=getchar();
    return io;
}
void exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){x=1;y=0;return ;}
    exgcd(b,a%b,x,y);
    int z=x;x=y,y=z-y*(a/b);
}
int main(){
    n=rd();
    for(int t=1;t<=n;++t){
        int M=rd();m[t]=M;
        mul*=M;
        a[t]=rd();
    }
    for(int t=1;t<=n;++t){
        Mi[t]=mul/m[t];
        ll x=0,y=0;
        exgcd(Mi[t],m[t],x,y);
        X+=a[t]*Mi[t]*(x<0?x+m[t]:x);
    }
    printf("%lld",X%mul);
    return 0;
}

  这就是CRT

但是我们知道GCD后有EX—gcd 所以CRT后也有EX—CRT

EX—CRT是这么说的(两数不互质)

CRT/EXCRT

 

PS 这里的Ai是不互质的,所以EXcrt根本不可能用CRT去解

CRT/EXCRT

代码如下

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
bool flag = false;
ll a1,a2,n1,n2;
ll n;
ll as[100001];
ll ns[100001];
void exgcd(ll a,ll b,ll g,ll &x,ll &y) {
	if (b == 0) {
		g = a;
		x = 1;
		y = 0;
		return;
	}
	exgcd(b,a%b,g,y,x);
	y-=(a/b)*x;
}
void china() {
	ll d = a2 - a1;
	ll g,x,y;
	exgcd(n1,n2,g,x,y);
	if (d % g == 0) {
		x = ((x*d/g)%(n2/g)+(n2/g))%(n2/g);
		a1 = x*n1 + a1;
		n1 = (n1*n2)/g;
	} else
		flag = true;
}
ll multi(ll a,ll b,ll m)
{
	ll ret=0;
	
	while(b!=0)
	{
		if(b&1)
		{
			ret=(ret+a)%m;
		}
		a=(a*2)%m;
		b/=1;
	}
	
	return ret;
}
ll excrt() {
	a1 = as[0];
	n1 = ns[0];
	for (ll i = 1; i<n; i++) {
		a2 = as[i];
		n2 = ns[i];
		china();
		if (flag)
			return -1;
	}
	return a1;
}
int main() {
	cin>>n;
	flag = false;
	for (ll i = 0; i<n; i++)
		cin>>ns[i]>>as[i];
	cout<<1ll*excrt()<<endl;
}

  今天终于考完颓荐生考试了,考的怎么样还要等到明天才出成绩,所以,本蒟蒻可能就要暂时离开OI的练习了,今天用了一点课余时间统计了一下我的刷题数

从1月9日开始学OI开始 到2020/06/27 我已经刷了597道题了

CRT/EXCRTCRT/EXCRT

如果成绩不是很理想的话,可能就要暂别机房了...

近六个月的学习,很快乐很苦也很充实,今天来打个卡,庆祝一下我洛谷刷题破300(虽然水了好多红题qwq)

但愿明天成绩不错....

 
上一篇:对于iPhone描述文件的签名认证


下一篇:.NET CORE部署各种问题