2020-2021:teams:legal_string:lgwza:扩展中国剩余定理
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:lgwza:扩展中国剩余定理 [2021/01/21 11:38] lgwza [例题] |
2020-2021:teams:legal_string:lgwza:扩展中国剩余定理 [2021/01/21 11:53] (当前版本) lgwza |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| 不保证 $m_i$ 互质，保证有解 | 不保证 $m_i$ 互质，保证有解 | ||
| + | |||
| + | **题解**： | ||
| + | |||
| + | 对于只有 $2$ 个方程的情况：$x\equiv a_1\pmod{m_1};x\equiv a_2\pmod{m_2}$，等价于 $x=a_1+m_1t_1=a_2+m_2t_2$，即 $m_1t_1-m_2t_2=a_2-a_1$，用扩展欧几里得解出 $t_1$，（若无解则方程组无解），从而得到 $x$ 的解 $x\equiv x_0\pmod{\text{lcm}(m_1,m_2)}$，从而将两个方程合并为一个。$n$ 个方程即执行 $n-1$ 次扩展欧几里得算法，不断合并方程，直至得到最终解。注意过程中乘法要用快速乘避免溢出，注意取模时的模数是什么。 | ||
| + | |||
| + | **代码**： | ||
| + | |||
| + | <hidden> | ||
| + | <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | const int N=1e5+5; | ||
| + | typedef long long ll; | ||
| + | ll m[N],a[N]; | ||
| + | ll gcd(ll x,ll y){ | ||
| + | return !y?x:gcd(y,x%y); | ||
| + | } | ||
| + | ll lcm(ll x,ll y){ | ||
| + | return y/gcd(x,y)*x; | ||
| + | } | ||
| + | void exgcd(ll a,ll b,ll &x,ll &y){ | ||
| + | if(!b){ | ||
| + | x=1,y=0;return; | ||
| + | } | ||
| + | exgcd(b,a%b,y,x); | ||
| + | y-=x*(a/b); | ||
| + | } | ||
| + | ll mul(ll x,ll y,ll mod){ | ||
| + | ll ans=0; | ||
| + | x%=mod;y%=mod; | ||
| + | while(y){ | ||
| + | if(y&1) ans=(ans+x)%mod; | ||
| + | x=(x+x)%mod; | ||
| + | y>>=1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | ll calc(ll M,ll mi,ll c,ll x0){ | ||
| + | ll g=gcd(M,mi); | ||
| + | ll x,y; | ||
| + | exgcd(M,mi,x,y); | ||
| + | ll temp=lcm(M,mi); | ||
| + | c=(c%mi+mi)%mi; | ||
| + | ll ret=mul(x,c/g,mi); | ||
| + | ret=(ret%mi+mi)%mi; | ||
| + | return (mul(ret,M,temp)+x0%temp)%temp; | ||
| + | } | ||
| + | int main(){ | ||
| + | int n; | ||
| + | scanf("%d",&n); | ||
| + | for(int i=1;i<=n;i++) scanf("%lld %lld",&m[i],&a[i]); | ||
| + | ll M=m[1]; | ||
| + | ll ans=a[1]%M; | ||
| + | for(int i=2;i<=n;i++){ | ||
| + | ans=calc(M,m[i],a[i]-ans,ans); | ||
| + | M=lcm(M,m[i]); | ||
| + | ans=(ans+M)%M; | ||
| + | } | ||
| + | printf("%lld",ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/lgwza/扩展中国剩余定理.1611200333.txt.gz · 最后更改: 2021/01/21 11:38 由 lgwza
