@[MLBZSSK](/user/333800) 直接乘会炸longlong，要用龟速乘
by charleshe @ 2022-07-07 20:46:58
@[charleshe](/user/477258) 那开个int128？
by qip101 @ 2022-07-07 20:48:10
@[MLBZSSK](/user/333800) 我建议龟速乘，但你要用int128我也不拦你，就是我也不知道能不能过。
众所周知最大可以达到 $10^{18} \times 10^{18} = 10^{36}$
by charleshe @ 2022-07-07 20:50:49
@[charleshe](/user/477258) 欧克欧克话说bdfs感觉没有什么好的龟速乘教程
by qip101 @ 2022-07-07 20:51:49
@[MLBZSSK](/user/333800) 其实就是快速幂，把里面的乘号改成加号。龟速乘和快速幂的原理是一样的
by charleshe @ 2022-07-07 20:53:09
@[charleshe](/user/477258) 哦哦哦谢谢大佬
by qip101 @ 2022-07-07 20:53:50
大概是这样子吗
```cpp
long long power(long long y,long long x)
{
if(x==0)
return 1%k;
long long sum=1;
while(x>0)
{
if(x & 1)
sum=sum%k+y%k;
y=y%k+y%k;
x>>=1;
}
return sum;
}
```
@[charleshe](/user/477258)
by qip101 @ 2022-07-07 20:55:38
@[MLBZSSK](/user/333800) addd，差不多
by charleshe @ 2022-07-07 20:56:22
@[charleshe](/user/477258) 这为什么写了龟速乘之后还是WA#2啊
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
long long k;
long long x,y;
long long MM=1;
long long a[25],b[25],u[25],M[25];
inline long long mul(long long a,long long b,long long p)
{
long long ans=0;
while(b)
{
if(b&1)
ans=(ans+a)%p;
a=a*2%p;
b>>=1;
}
return ans;
}
inline void init()
{
cin >> k;
for(int i=1;i<=k;i++)
cin >> a[i];
for(int i=1;i<=k;i++)
{
cin >> b[i];
MM*=b[i];
}
for(int i=1;i<=k;i++)
M[i]=MM/b[i];
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
long long d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main()
{
ios::sync_with_stdio(false);
init();
for(int i=1;i<=k;i++)
{
exgcd(M[i],b[i],u[i],y);
u[i]=(b[i]+u[i]%b[i])%b[i];
for(int j=1;j<=a[i];j++)
x=(x+mul(M[i],u[i],MM))%MM;
}
cout << x%MM << endl;
return 0;
}
```
by qip101 @ 2022-07-07 21:01:34
@[MLBZSSK](/user/333800) 我把我的代码给宁对比下？
```
#include <iostream>
#define int long long
using namespace std;
int n;
int a[11],b[11];
int M,ans;
void exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
int mul(int x,int y,int mod){
int ans=0;
while(y){
if(y&1) ans=(ans+x)%mod;
x=(x+x)%mod;
y>>=1;
}
return ans;
}
signed main(){
cin>>n;
M=1;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
cin>>b[i];
M*=b[i];
}
for(int i=1;i<=n;i++){
int m=M/b[i];
int x,y;
exgcd(m,b[i],x,y);
x=(x%b[i]+b[i])%b[i];
ans=(ans+mul((a[i]+b[i])%b[i],mul(x,m,M),M)+M)%M;
}
ans=(ans+M)%M;
cout<<ans<<endl;
return 0;
}
```
by charleshe @ 2022-07-07 21:12:03