自从转到c++
n年没用过python
除了会写爬虫都忘了。。。
by ZhuMingYang @ 2019-03-04 21:43:58
不会python,再见(
by Celestial_Scarlet @ 2019-03-04 21:44:43
@[ZhuMingYang](/space/show?uid=128523) 除了列表相关操作和C++没什么区别啊
by Mosklia @ 2019-03-04 21:45:54
@[Sparky_14145](/space/show?uid=67387) 确实,看当然看得懂。。。
by ZhuMingYang @ 2019-03-04 21:47:31
python 中 -1%10=9还是-1
如果是-1 那你x%=b[i]
要改成x=(x%b[i]+b[i])%b[i]
by ZhuMingYang @ 2019-03-04 21:55:07
@[ZhuMingYang](/space/show?uid=128523) 不是,那是C++
Py -1 % 10 = 9
真正的错误是exGCD中应该用 // 而不是 /,以及 CRT 中`ans += x * a[i] * b[i]`改成`ans += x * a[i] * mi`
by Mosklia @ 2019-03-04 22:06:38
才看出来
by Mosklia @ 2019-03-04 22:06:49
@[Sparky_14145](/space/show?uid=67387) 好吧。。。
by ZhuMingYang @ 2019-03-04 22:08:29
@[Sparky_14145](/space/show?uid=67387) 你用c++写的话 最后一个点要写快乘 没Python那么高级
by ZhuMingYang @ 2019-03-04 22:09:41
@[Sparky_14145](/space/show?uid=67387)
```
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
ll n,sum=0,m=1,x,y,a[100010],p[100010];
ll mul(ll a, ll b, ll mod){
ll ans = 0;
for(;b; b >>= 1, a = (a + a) % mod) if(b&1) ans = (ans + a) % mod;
return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0){
x=1,y=0;
return a;
}
ll d=exgcd(b,a%b,x,y);
ll z=x;x=y,y=z-(a/b)*y;
return d;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%lld",a+i);
}
for(int i=1;i<=n;i++)
{
scanf("%lld",p+i);
a[i]=(a[i]%p[i]+p[i])%p[i];
m*=p[i];
}
for(int i=1;i<=n;i++)
{
ll M=m/p[i];
exgcd(M,p[i],x,y);
x=(x%p[i]+p[i])%p[i];
sum=(sum+mul(mul(M,x,m),a[i],m))%m;
}
cout<<(sum%m+m)%m<<endl;
return 0;
}
```
by ZhuMingYang @ 2019-03-04 22:10:20