原题链接
\(首先我们来简单地复习一下中国剩余定理\)
\(对于x \equiv a_i \mod m_i\)
\(令M= \prod_{i=1}^{n} m_i（其中m_i代表的是除数，a_i代表的是余数）\)
\(M_i=M/m_i\)
\(t_i \equiv (M_i)^-1 \mod m_i（使用扩展欧几里得算出即可 exgcd）\)
\(因为(t_i*M_i) \equiv 1 \mod m_i 并且 a_i*t_i*M_i \mod m_i==1 (意思为自己对它取模的结果为一) a_i*t_i*M_i \mod M_i==0 (代表其它数对他进行取模结果都为零)\)
\(那么很明显符合上式\)
\(所以x=k\prod_{i=1}^{n} m_i+\sum_{i=1}^{n} (t_i*a_i*M_i)\)
\(x \equiv \sum_{i=1}^{n} (t_i*a_i*M-) \mod k\prod_{i=1}^{n} m_i\)
\(经过一系列小学生计算 我们发现这题就是中国剩余定理的板子题 那么直接套板子即可通过 因为数据点可能过大 >2e18 所以建议使用__int128__\)
\(code：\)
点击查看代码
plaintext
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define i128 __int128
i128 read() {
__int128 x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
std::ostream &operator<<(std::ostream &os,i128 n){
std::string s;
while(n){
s+='0'+n%10;
n/=10;
}
std::reverse(s.begin(),s.end());
return os<<s;
}
i128 qpw(i128 a,i128 b,i128 mod){i128 ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
void exgcd(i128 a,i128 b,i128 &x,i128 &y){
if(b==0){x=1;y=0;return;}
exgcd(b,a%b,x,y);
i128 tp=x;
x=y;y=tp-a/b*y;
}
void print(__int128 x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
void solve() {
i128 n;n=read();
i128 lcm=1,x,y;
vector<i128>a(n+1),b(n+1);
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)b[i]=read(),lcm=lcm*b[i];
for(int i=1;i<=n;i++)a[i]=(a[i]%b[i]+b[i])%b[i];
i128 ans=0;
for(int i=1;i<=n;i++){
i128 tp=lcm/b[i];
exgcd(tp,b[i],x,y);
x=(x%b[i]+b[i])%b[i];
ans=(ans+x*tp%lcm*a[i]%lcm)%lcm;
}
print(ans);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int _=1;
// cin>>_;
while(_--)solve();
}