poj2891 Strange Way to Express Integers 扩展欧几里德的应用
刚开始数论，还不知道中国余数定理这东西，后来看了看，本题 不互素（互质）所以不能直接套中国余数定理，要两两合并公式，看了网上很多题解，基础真心很差结果都没看懂，但是终于看到了一篇让我这么没资质的人懂了
转一下 他的分析
模不互素，不能直接用中国剩余定理，只能每次求2组方程，然后通过他们的lcm求出最后符合左右方程组的解。例如有下面2条同余方程 x ≡ 3 (mod 4)，x ≡ 5 (mod 6)。x = 3 + 4j≡ 5 (mod 6)两边同时减去34j ≡ 2 (mod 6)两边同时除于 gcd(4,2,6)2j ≡ 1 (mod 3)因为2关于3同余1的逆是2j ≡ 2 (mod 3)j = 2 + 3kx = 3 + 4(2 + 3k)这步就是r1 = a1 * x + r1他举了具体数字 看起来就好懂多了
#include<iostream>#include<cstdio>#include<list>#include<algorithm>#include<cstring>#include<string>#include<queue>#include<stack>#include<map>#include<vector>#include<cmath>#include<memory.h>#include<set>#define ll long long#define LL __int64#define eps 1e-8const ll INF=9999999999999;using namespace std;#define M 400000100#define inf 0xfffffff//vector<pair<int,int> > G;//typedef pair<int,int> P;//vector<pair<int,int>> ::iterator iter;////map<ll,int>mp;//map<ll,int>::iterator p;//vector<int>G[30012];LL x,y,t;LL extgcd(LL a,LL b){if(b==0){x=1;y=0;return a;}else{LL temp=extgcd(b,a%b);t=x;x=y;y=t-a/b*y;return temp;}}int main(void){int n;while(cin>>n){bool flag=false;LL a,r;cin>>a>>r;for(int i=0;i<n-1;i++){LL a1,r1; cin>>a1>>r1;if(flag)continue;LL d=r1-r;LL gcd=extgcd(a,a1);if(d%gcd!=0){flag=true;continue;}LL temp=a1/gcd;x=(d/gcd*x%temp+temp)%temp;//直接取余的话，如果求出的gcd值为负数，那就会得到个负数，取余的时候要写成这样子r=a*x+r;a=a*a1/gcd;}if(flag)puts("-1");elsecout<<r<<endl;}}