其实这是 7.10 的题，由于 7.26 的模拟赛突然想了起来。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int lcm(int x,int y){
int p=__gcd(x,y);
return (int)((__int128)p*(x/p)*(y/p));
}
int qpow(int a,int b,int mod){
int ans=1;
while(b){
if(b&1){
ans=(ans%mod*a%mod)%mod;
}
a=(__int128)(a%mod)*(a%mod)%mod;
b>>=1;
}
return ans;
}
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37};
bool is_prime(int n){
if(n<2) return false;
for(int i=0;i<12;i++){
if(n%prime[i]==0) return n==prime[i];
}
int d=n-1,s=0;
while(d%2==0){
d/=2;
s++;
}
for(int i=0;i<12;i++){
int a=prime[i];
if(a>=n) continue;
int x=qpow(a,d,n);
if(x==1||x==n-1) continue;
bool flag=true;
for(int r=1;r<s;r++){
x=(__int128)x*x%n;
if(x==n-1){
flag=false;
break;
}
}
if(flag==0) return false;
}
return true;
}
int pollard_rho(int n){
if(n%2==0) return 2;
if(n%3==0) return 3;
while(1){
int c=rand()%(n-1)+1;
int x=rand()%n;
int y=x;
int d=1;
for(int it=0;it<10000&&d==1;it++){
x=((__int128)x*x+c)%n;
y=((__int128)y*y+c)%n;
y=((__int128)y*y+c)%n;
d=__gcd(llabs(x-y),n);
}
if(d>1&&d<n) return d;
}
}
void fc(int n,vector<int>& f){
if(n==1) return ;
//int d=pollard_rho(n);
if(is_prime(n)){
f.push_back(n);
return ;
}else{
int d=pollard_rho(n);
fc(d,f);
fc(n/d,f);
}
}
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
return a;
}
int k=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return k;
}
int inv(int a,int mod){
int x,y;
int g=exgcd(a,mod,x,y);
return (x%mod+mod)%mod;
}
int crt(int a1,int m1,int a2,int m2){
int iv=inv(m1%m2,m2);
int t=((a2-a1)%m2+m2)%m2;
t=(int)((__int128)t*iv%m2);
return a1+(__int128)m1*t;
}
int solve(int lcma,vector<int> f){
map<int,int> mp;
vector<pair<int,int>> fs;
int k=0;
for(int i=0;i<f.size();i++){
mp[f[i]]++;
if(i==f.size()-1||f[i]!=f[i+1]){
int p=f[i];
int cnt=mp[p];
int val=1;
for(int j=0;j<cnt;j++){
val*=p;
}
fs.push_back({p,val});
k++;
}
}
int ans=lcma;
for(int i=0;i<(1<<k);i++){
int a=1,b=1;
for(int j=0;j<k;j++){
if(i&(1<<j)){
a*=fs[j].second;
}else{
b*=fs[j].second;
}
}
if(a==1){
int m=0;
if(b==1) m=b;
else m=b-1;
ans=min(ans,m);
}else if(b==1){
ans=min(ans,a);
}else{
//1
int z=crt(0,a,b-1,b);
if(z>0) ans=min(ans,z);
z=crt(0,b,a-1,a);
if(z>0) ans=min(ans,z);
}
}
return ans;
}
signed main(){
srand(time(0));
int n;
cin>>n;
int x;
cin>>x;
int lcma=x;
for(int i=2;i<=n;i++){
cin>>x;
lcma=lcm(lcma,x);
}
lcma*=2;
vector<int> f;
fc(lcma,f);
sort(f.begin(),f.end());
int ans=solve(lcma,f);
cout<<ans;
}