表达整数的奇怪方式（拓展中国剩余定理）

题目链接

https://www.acwing.com/problem/content/description/206/

思路

对于这个问题，我们要求解n个满足条件的方程，我们首先考虑满足两个方程的情况： X ≡ m 1   m o d   a 1 X≡m_1 \ mod \ a_1 X≡m1​ mod a1​ X ≡ m 2   m o d   a 2 X≡m_2 \ mod \ a_2 X≡m2​ mod a2​ 这个方程也能写成如下格式，假设一任意整数 k i k_i ki​ X ≡ k i a i + m i   m o d   a i X≡k_i a_i + m_i \ mod \ a_i X≡ki​ai​+mi​ mod ai​ 于是我们得到： k 1 a 1 + m 1 = k 2 a 2 + m 2 k_1a_1 + m_1 = k_2 a_2 + m_2 k1​a1​+m1​=k2​a2​+m2​ 即 k 1 a 1 − k 2 a 2 = m 2 − m 1 k_1a_1-k_2a_2=m_2-m_1 k1​a1​−k2​a2​=m2​−m1​

设d为 g c d ( a 1 , a 2 ) gcd(a_1,a_2) gcd(a1​,a2​)

如果 d ∣ m 2 − m 1 d |m_2-m_1 d∣m2​−m1​那么说明方程有解，我们可以通过拓展欧几里得算法求出k1,k2的一种解

设p为任意整数，又由于解不是唯一的，所以我们可以将k1的通解写成一下形式： k 1 = k 1 + p a 2 d k1 = k1 + p\frac{a_2}{d} k1=k1+pda2​​ 同理k2的通解可以写成： k 2 = k 2 + p a 1 d k2 = k2 + p\frac{a_1}{d} k2=k2+pda1​​ 然后我们将k1通解公式代入原方程可得： X ≡ ( ( k 1 + p a 2 d ) a 1 + m 1 )   m o d   a 1 X≡((k_1 + p\frac{a_2}{d})a_1 + m1) \ mod \ a_1 X≡((k1​+pda2​​)a1​+m1) mod a1​ X ≡ ( P a 1 ∗ a 2 d + a 1 k 1 + m 1 )   m o d   a 1 X≡ (P\frac{a_1*a_2}{d} + a_1k_1 + m_1) \ mod \ a_1 X≡(Pda1​∗a2​​+a1​k1​+m1​) mod a1​ X ≡ ( P × l g m ( a 1 , a 2 ) + ( a 1 k 1 + m 1 ) )   m o d   a 1 X≡(P\times lgm(a_1,a_2) + (a_1k_1 + m_1)) \ mod \ a_1 X≡(P×lgm(a1​,a2​)+(a1​k1​+m1​)) mod a1​ 然后此时我们惊奇的发现这个不就是我们开始转化的式子的格式吗，于是我们发现我们通过这样的操作可以将两个方程合并，那么我们将这n个方程合并成一个方程，最后就变成了 X ≡ P X 0 + m 1   m o d   X 0 X≡P X_0 + m_1 \ mod \ X_0 X≡PX0​+m1​ mod X0​的形式那么直接输出 m 1 m_1 m1​就好了 注意： 1.因为数据很极限所以我们在计算的过程中要保证k1是一个最小正数解 2.最后的 m 1 m_1 m1​可能为负数，最好将其先取模再加上模数再取模，保证非负

代码

#include
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
//----------------自定义部分----------------
int t,n,m,q,a[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;
}

void slove(){
	cin>>n;
	ll a1,m1;
	cin>>a1>>m1;
	bool fg = true;
	for(int i = 1;i >a2>>m2;
		ll k1,k2;
		ll d = exgcd(a1,a2,k1,k2);
		if((m2 - m1) % d){
			fg = false;
			break;
		}
		k1 *= (m2-m1)/d;//翻倍
		ll t = abs(a2 / d);
		k1 = (k1 % t + t) % t;//变为最小的正整数解否则会溢出
		
		m1 = a1 * k1 + m1;
		a1 = (a1 / d  * a2);
	}
	if(fg){
		cout