rt,以下是代码:
#include <bits/stdc++.h>
//#define mod 998244353
using ll = long long;
using namespace std;
const int maxn = 5005,mod = 998244353;
int n;
ll a[maxn],b[maxn];
int ans = (mod + 1) / 2;
ll gcd(ll x,ll y)
{
if (y == 0)return x;
return gcd(y,x % y);
}
ll qpow(int a,int b)
{
ll res = 1ll;
while (b)
{
if (b & 1)
res = res * a % mod;
a = (a * a) % mod,b >>= 1;
}
return res;
}
int main()
{
scanf("%d",&n);
for (int i = 1;i <= n;i++)
scanf("%lld",a + i);
//b[1] = a[1] % mod;
for (int i = 1;i <= n;i++)
{
ll cnt = 1ll;
for (int j = 1;j < i;j++)
{cnt = (__int128)cnt * b[j] % a[i];}
b[i] = a[i] / gcd(a[i],cnt);
//cout << b[i] << ' ' << i << endl;
}
for (int i = 1;i <= n;i++)
{ans = b[i] % mod * ans % mod;}
printf("%d",ans);
return 0;
}
其中最后算ans的一行如果换成
ans = ans % mod * b[i] % mod;
就会错,比如说
2
700442971370034452 959019558094624110
原程序输出918734010,换顺序后输出-368504960