[cf571e] geometric progressions -- number theory and prime factor decomposition

CF571E Geometric Progressions

Answer key

I looked almost completely at This article explains Taxi .

The product is too large to handle , So we put all $a_i,b_i$ Do prime factorization .

Then consider merging two series , The result is obvious ： Or there is no solution , Or get a number , Or we can get a new sequence of proportional numbers . Our task is to $n$ Two series of numbers are merged , Final output （ The first term of the proportional series is output ）. For the convenience of , We can regard a number as a common ratio 1 A series of equal proportions .

remember $c_p(x)$ Express $x$ Prime number in prime factor decomposition of the $p$ The number of times , So let's merge two series $a\ast b^{?}$ and $c\ast d^{?}$ （ The purpose is to find the natural number coefficient $x,y$ bring $a\ast b^x=c\ast d^y$） when , Each prime factor can be enumerated $p$, And then discuss the situation ：

• $c_p(b)$ and $c_p(d)$ All equal to 0, If at this time $c_p(a)\ne c_p(c)$ There must be no solution , Otherwise it doesn't matter ;
• $c_p(b)$ and $c_p(d)$ One of the two is equal to 0, At this time, the coefficient on the non-zero side has been determined （ There may also be no natural number solution , So there's no solution ）, The coefficient of zero is to be determined ;
• $c_p(b)$ and $c_p(d)$ None of them 0, At this point, we get the bivariate equation $c_p(b)x-c_p(d)y=c_p(c)-c_p(a)$, Write it down and put it aside .

After processing , There are several situations ：

• unsolvable , Then don't worry ;
• Neither of the two coefficients is determined , In this case, if not both series have only one value , Then there must be several bivariate equations left . After the linear correlation in these equations is de duplicated , If there are two or more equations , Then the coefficient has a unique solution , Substitute judgment ; If there is only one equation , Then we need to use the extended Euclidean algorithm to solve $x,y$ Are non negative integers , And $x$ or $y$ The smallest solution , Then you can merge a new series of proportional numbers . Let this new sequence of equal proportions be $a^{\prime }\ast b^{\prime ?}$, So there are $$\begin{gathered} c_p(a^{\prime })=c_p(a)+x\times c_p(b) \\ {c}_p(b^{\prime })=\text{lcm}(c_p(b),c_p(d)) \end{gathered}$$
• One of the coefficients is fixed , Then a certain sequence of numbers can be treated as a number , Then repeat the above process . At this time, enumerating prime factor values may appear 1、2 Two cases , So the last two coefficients can be determined , Then we will continue to discuss ：
• Both coefficients are fixed , Then take it in for inspection .

In order to facilitate weight removal , I used a large constant map. Finally, according to the prime factor, the output module is decomposed $a$ The value of the can .

The code looks long , In fact, most of them are repeaters .

Code

#include<bits/stdc++.h>//JZM yyds!!
#define ll long long
#define lll __int128
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define END putchar('\n')
#define lowbit(x) ((x)&-(x))
#define inline jzmyyds
using namespace std;
const int MAXN=114514;
const ll INF=1e18;
ll read(){
    
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){
    if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int readuns(){
    
	int x=0;char s=getchar();
	while(s<'0'||s>'9')s=getchar();
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return x;
}
int ptf[50],lpt;
void print(ll x,char c='\n'){
    
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt>0)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
const ll MOD=1e9+7;
ll ksm(ll a,ll b,ll mo){
    
	ll res=1;
	for(;b;b>>=1,a=a*a%mo)if(b&1)res=res*a%mo;
	return res;
}
ll exgcd(ll a,ll b,ll&x,ll&y){
    
	if(!b)return x=1,y=0,a;
	ll d=exgcd(b,a%b,y,x);
	return y-=a/b*x,d;
}
ll gcd(ll a,ll b){
    return !b?a:gcd(b,a%b);}
map<ll,ll> getp(ll x){
    
	map<ll,ll>res;
	for(ll i=2;i*i<=x;i++)if(x%i==0){
    
		ll&d=res[i]=0;
		while(x%i==0)x/=i,d++;
	}if(x>1)res[x]=1;
	return res;
}
#define pll pair<ll,ll>
struct itn{
    
	ll a,b,c;itn(){
    }
	itn(ll A,ll B,ll C){
    
		ll d=gcd(gcd(A,B),C);
		if(A<0)d=-d;
		if(d)a=A/d,b=B/d,c=C/d;
		else a=b=c=0;
	}
	bool operator<(const itn&y)const{
    
		return a<y.a||(a==y.a&&(b<y.b||(b==y.b&&c<y.c)));
	}
	pll rsl()const{
    
		ll x,y,d=exgcd(a,abs(b),x,y),p=b/d,q=a/d;
		if(b<0)y=-y;
		if(c%d)return pll(-1,-1);
		x*=c/d,y*=c/d;
		if(q<0)q=-q,p=-p;
		if(y<0)x-=p*((-y+q-1)/q),y+=q*((-y+q-1)/q);
		if(p<0)p=-p,q=-q;
		if(x<0)y-=q*((-x+p-1)/p),x+=p*((-x+p-1)/p);
		if(x>0){
    
			if(q>0)y+=q*(x/p),x-=p*(x/p);
			else{
    
				q=-q;ll md=min(x/p,y/q);
				x-=p*md,y-=q*md;
			}
		}
		if(x<0||y<0)return pll(-1,-1);
		return pll(x,y);
	}
};
pll getcro(const itn&p,const itn&q){
    
	ll D=p.a*q.b-p.b*q.a;
	if(!D)return pll(-1,-1);
	ll D1=p.c*q.b-p.b*q.c,D2=p.a*q.c-p.c*q.a;
	if(D<0)D=-D,D1=-D1,D2=-D2;
	if(D1<0||D2<0||D1%D||D2%D)return pll(-1,-1);
	return pll(D1/D,D2/D);
}
map<ll,ll>a,b;
bool ok=1,hv=0;
int main()
{
    
	for(int N=read();N--;){
    
		ll A=read(),B=read();
		if(!ok)continue;
		map<ll,ll>c=getp(A),d=getp(B);
		for(auto it:d)c[it.fi];
		if(!hv){
    swap(a,c),swap(b,d),hv=1;continue;}
		for(auto it:c)a[it.fi];
		set<itn>st;
		ll u=-1,v=-1;
		for(auto mmp:a){
    
			const ll p=mmp.fi,ci=b[p],cj=d[p];
			// printf("\n %lld %lld %lld %lld %lld\n",p,a[p],c[p],ci,cj);
			if(!ci&&!cj){
    
				if(a[p]==c[p])continue;
				ok=0;break;
			}if(!ci){
    
				ll dt=a[p]-c[p];
				if(dt<0||dt%cj){
    ok=0;break;}
				v=dt/cj;continue;
			}if(!cj){
    
				ll dt=c[p]-a[p];
				if(dt<0||dt%ci){
    ok=0;break;}
				u=dt/ci;continue;
			}st.insert(itn(ci,-cj,c[p]-a[p]));
		}
		if(!ok)continue;
		if(u<0&&v<0){
    
			if(st.empty())continue;
			if(st.size()==1){
    
				pll rs=(*st.begin()).rsl();
				if(rs.fi<0){
    ok=0;continue;}
				for(auto mmp:a){
    
					const ll p=mmp.fi,ci=b[p],cj=d[p];
					a[p]+=rs.fi*ci;
					if(!ci||!cj)b[p]=0;
					else b[p]=ci/gcd(ci,cj)*cj;
				}continue;
			}
			itn f=*st.begin(),g=*st.rbegin();
			pll rs=getcro(f,g);
			if(rs.fi<0){
    ok=0;continue;}
			for(auto x:st)if(rs.fi*x.a+rs.se*x.b!=x.c)ok=0;
			if(!ok)continue;
			u=rs.fi,v=rs.se;
		}
		if(u<0||v<0){
    
			for(auto mmp:a){
    
				const ll p=mmp.fi;
				if(u>=0)a[p]+=u*b[p],b[p]=0;
				if(v>=0)c[p]+=v*d[p],d[p]=0;
			}u=v=0;
			for(auto mmp:a){
    
				const ll p=mmp.fi,ci=b[p],cj=d[p];
				if(!ci&&!cj){
    
					if(a[p]==c[p])continue;
					ok=0;break;
				}if(!ci){
    
					ll dt=a[p]-c[p];
					if(dt<0||dt%cj){
    ok=0;break;}
					v=dt/cj;continue;
				}if(!cj){
    
					ll dt=c[p]-a[p];
					if(dt<0||dt%ci){
    ok=0;break;}
					u=dt/ci;continue;
				}
			}if(!ok)continue;
		}
		if(u>=0&&v>=0){
    
			for(auto mmp:a){
    
				const ll p=mmp.fi;
				a[p]+=u*b[p],c[p]+=v*d[p],b[p]=0;
				if(a[p]^c[p]){
    ok=0;break;}
			}
			if(!ok)continue;
		}
	}ll ans=1;
	if(!ok)return printf("-1\n"),0;
	for(auto it:a)(ans*=ksm(it.fi,it.se,MOD))%=MOD;
	print(ans);
	return 0;
}