另一种思路:本题的递归解法
递归解法
第一次写题解可能写的比较乱,大家凑活着看吧
代码中给出了较为详细的注释,这里解释一下原理和一些细节问题
递归解法的原理:
假定已经求出了前k-1个方程的一个解x[k-1],记l[k-1]=lcm(a1,a2,...,a[k-1])
,即a1,a2,...,a[k-1]
的最小公倍数.
则x[k-1]+k*l[k-1]
是前k-1个方程的通解. 原因:(l[k-1]%a[i]==0,i=1,2,...,k-1)
这时,我们只需要确定一个k1,使得(x+k1*l[k-1])%a[k]=m[k]
,即可得到前k个方程的一个解,如果k1存在,则前k个方程组有解,不存在则无解.
现在求解k1:
将(x+k1*l[k-1])%a[k]=m[k]
变形,可得k1*l[k-1]-k2*a[k]=m[k]-x
此时用exgcd(l[k-1],a[k],k1,k2)
即可求解出k1.
如果有解,即可得到前k个方程组的解为:x[k]=x[k-1]+k1*l[k-1]
此时,x[k]+k*l[k]
即为前k个方程组的通解(这个很重要,需要理解为什么)
k1%t以及x%l[n]的操作的具体含义:
//计算符合条件的最小正整数k1
k1*=(m[n]-x)/d;
LL t=a[n]/d;
k1=(k1%t+t)%t;
//计算符合条件的最小正整数x
x=(x%l[n]+l[n])%l[n];
这是在求解最小正整数的特解(视频里有讲)
k1的通解为:k1+(a[k]/d)*k
//k1要求最小正整数是为了防止x爆long long返回错误结果
x的通解为:x+l[n]*k
求出通解中的最小正整数,就是所需要的特解.
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=30;
typedef long long LL;
//存储a,m l[k]中存储了a_1,a_2,...,a_k的最小公倍数
//为了写的更明白用了一个数组来存储最小公倍数,可以简化为只用一个变量
LL a[N],m[N],l[N];
LL exgcd(LL a,LL b,LL &x,LL &y){
if(!b){
x=1,y=0;
return a;
}
LL d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
//计算方程组的解x
LL get_x(int n){
//递归基,只有一个方程时,x=m1,l=a1
if(n==1){
l[1]=a[1];
return (m[1]%a[1]+a[1])%a[1];
}
//得到n-1个方程组的解
LL x=get_x(n-1);
//n-1个方程无解,n个方程自然无解
if(x==-1) return -1;
//解线性同余方程k1*l[n-1]-k2*a[n]=m[n]-x;
LL k1,k2;
LL d=exgcd(l[n-1],a[n],k1,k2);
//线性同余方程无解的条件是(m[n]-x)%d!=0
if((m[n]-x)%d) return -1;
//计算符合条件的最小正整数k1
k1*=(m[n]-x)/d;
LL t=a[n]/d;
k1=(k1%t+t)%t;
//更新n个方程组的解x
x=x+k1*l[n-1];
//更新前n个a的最小公倍数
l[n]=l[n-1]*a[n]/d;
//返回最小正整数x
x=(x%l[n]+l[n])%l[n];
return x;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>m[i];
}
cout<<get_x(n)<<endl;
}
循环解法(同y总)
循环解法的代码和y总的一样,有写的比较详细的题解了,不在赘述
C++ 代码
blablabla
敲公式太累了大家凑活着看吧hh