题目链接
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≡kiai+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
k1a1+m1=k2a2+m2
即
k
1
a
1
−
k
2
a
2
=
m
2
−
m
1
k_1a_1-k_2a_2=m_2-m_1
k1a1−k2a2=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+a1k1+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)+(a1k1+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
关注
打赏
![]()
查看更多评论
