题目大意

给出数列p[i]，求最小的x使得\(\forall i,(x+1)x/2\%p_i=0\)
保证lcm(p[i])<=1e18

n<=1e5，pi<=1e7

题解

对所有的i模p[i]=0，等价于模lcm(p[i])=0

所以求最小的x使得\((x+1)x/2\%lcm=0\)，\((x+1)x=2lcm\)

因为lcm<=1e18，所以不同的质因子只有2~47共15个，要使s=x(x+1)在这些质因子上的次数超过lcm的次数
（s贡献的\(p_1^{k_1'}\)模lcm中\(p_1^{k_1}=0\)）

因为x和x+1互质，所以二者贡献的质因子各不相同
换句话说，就是lcm中需要有的质因子分别在x和x+1中出现

所以 2^质因子种数 枚举质因子划分情况，变成\(x\%p_{11}^{k_{11}}=0,x\%p_{12}^{k_{12}}=0,...,(x+1)\%p_{21}^{k_{21}}=0,(x+1)\%p_{22}^{k_{22}}=0,...,\)

然后crt合并取最小x

code

不是我写的

~~显然是wjt写的~~

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=10001000;

int n;
int prime[N],num;
bool b[N];
LL ans=4e18;
LL gd[121],cnt;

LL gcd(LL x,LL y)
{
	if( !y)
	return x;
	return gcd(y, x%y);
}

LL exgcd(LL a,LL b,LL &x,LL &y){
	LL d=a; if(b==0) x=1,y=0; else{
		d=exgcd(b,a%b,y,x),y-=a/b*x;
	}
	return d;
}
void pre()
{
	for(int i=2;i<N;i++)
	{
		if( !b[i])
		prime[++num]=i;
		for(int j=1;j<=num && i * prime[j]<N;j++)
		b[i*prime[j]]=1;
	}
}

int main()
{
	
	pre();
	
	cin>>n;
	LL lcm=1;
	for(int i=1;i<=n;i++)
	{
		LL x;
		scanf("%lld",&x);
		lcm=lcm/gcd(x,lcm) * x;
	}
	
	if( lcm==1)
	{
		cout<<1<<endl;
		return 0;
	}
	
	lcm*=2;
	
	for(int i=1;i<=num;i++)
	if( lcm % prime[i]==0)
	{
		LL zhi=1;
		LL taffy=lcm;
		while( taffy%prime[i]==0)
		{
			taffy/=prime[i];
			zhi*=prime[i];
		}
		gd[cnt++]=zhi;
	}
	
	int nn=(1<<cnt);
	for(int i=0;i<nn;i++)
	{
		LL tk=1,res=1;
		for(int j=0;j<cnt;j++)
		if( (1<<j) &i)
		tk*=gd[j];
		else
		res*=gd[j];
		
		LL x,y;
		LL d=exgcd(tk,res, x,y);
		
		
		y%=tk;
		if( y<=0)
		y+=tk;
		
		if( y * res-1 < ans )
		{
			LL taffy=lcm,tmp= y * res-1;
			if(tmp!=0)
			{
				taffy/=gcd(tmp, taffy);
				taffy/=gcd(tmp+1,taffy);
				
				if( taffy==1)
				ans=tmp;
			}
		
		}
		
	}
	
	cout<<ans<<endl;
	
	
	return 0;
}