Codeforces 571E - Geometric Progressions（数论+阿巴细节题）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Codeforces 571E - Geometric Progressions（数论+阿巴细节题），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6836字，纯文字阅读大概需要10分钟。
内容图文
u1s1 感觉此题思维难度不太大，不过大概是细节多得到了精神污染的地步所以才放到 D1E 的罢（（（
首先我们对所有 \(a_i,b_i\) 分解质因数并将它们全部质因子拎出来编个号 \(1,2,3,\cdots,m\)——这样的质因子个数肯定不会超过 \(2n\omega(a_i)\)。我们记 \(ap_{i,j}\) 表示 \(a_i\) 中标号为 \(j\) 的质因子出现的次数，\(bp_{i,j}\) 表示 \(b_i\) 中标号为 \(j\) 的质因子出现的次数，那么本题等价于找出两个序列 \(k_1,k_2,\cdots,k_n\) 和 \(X_{1},X_2,\cdots,X_m\)使得对于任意质因子 \(j\) 都有 \(ap_{1,j}+k_1bp_{1,j}=ap_{2,j}+k_2bp_{2,j}=\cdots=ap_{n,j}+k_nbp_{n,j}=X_j\)，\(k_i\) 表示最终的答案 \(=a_ib_i^{k_i}\)，\(X_i\) 表示在最终答案的质因数分解式中编号为 \(i\) 的质因子的出现次数。
考虑对质因子分开来考虑，对于某个质因子 \(j\)，如果 \(\exists i\) 使得 \(bp_{i,j}=0\)，那么意味着 \(X_j\) 只能等于 \(ap_{i,j}\)，此时我们检查是否 \(\exists l\ne i\) 满足 \(bp_{l,j}>0\)，如果不存在我们只需检验是否所有 \(ap_{l,j}\) 都等于 \(ap_{i,j}\)，如果是那么答案乘上 \(p_j^{X_j}\) 并忽略这个方程，否则我们可以得到一个一元一次方程 \(ap_{l,j}+k_lbp_{l,j}=ap_{i,j}\)，如果 \(ap_{i,j}<ap_{l,j}\) 或 \(ap_{i,j}-ap_{l,j}\) 不是 \(bp_{l,j}\) 的倍数那就无解，否则解出 \(k_l\) 之后就可以解出所有 \(X_j\)，解出 \(X_j\) 之后再带回去求出其他的 \(k_i\)，解完之后再代回去看看是否合法，如果不合法则 \(-1\)，合法就直接输出 \(\prod p_j^{X_j}\) 然后退出即可。
处理完 \(\exists bp_{i,j}=0\) 的质因子之后我们默认其余的 \(bp_{i,j}\) 都不等于 \(0\)，我们不妨假设 \(1\) 号质因子满足 \(\forall i,bp_{i,1}\ne 0\)，那么显然有 \(\forall i,ap_{1,1}+k_1bp_{1,1}=ap_{i,1}+k_ibp_{i,1}\)，我们将 \(k_1,k_i\) 当作两个变量，其余当作常数，可得方程 \(k_1bp_{1,1}-k_ibp_{i,1}=ap_{i,1}-ap_{1,1}\)，我们考虑另外枚举一个满足 \(\forall i,bp_{i,j}\ne 0\) 的质因子 \(j\)，那么也可得类似的方程 \(k_1bp_{1,j}-k_ibp_{i,j}=ap_{i,j}-ap_{1,j}\)，如果该方程满足 \(\dfrac{bp_{1,1}}{bp_{1,j}}=\dfrac{bp_{i,1}}{bp_{i,j}}=\dfrac{ap_{i,1}-ap_{1,1}}{ap_{i,j}-ap_{1,j}}\) 则该方程与第一个方程是等价的可以忽略，否则我们就暴力解出 \(k_1,k_i\) 并带回去求出所有的 \(X_i\)，再求出别的 \(k_i\) 即可。否则我们根据 \(ap_{1,1}+k_1bp_{1,1}=ap_{2,1}+k_2bp_{2,1}=\cdots=ap_{n,1}+k_nbp_{n,1}=X_1\) 可以得到 \(n\) 个形如 \(X_1\equiv ap_{i,1}\pmod{bp_{i,1}}\) 的同余方程组，exCRT 合并即可，最后可以得到形如 \(X_1\equiv A\pmod{B}\) 的式子，记 \(mx=\max\limits_{i=1}^nap_{i,1}\)，当然有可能这里 \(A<mx\)，那么就会存在 \(k_i\) 是负数的情况，这是不合法的，因此我们需令 \(A\) 不断加上 \(B\) 直到 \(A\ge mx\)，最后我们希望找到的最小的 \(X_1\) 就是 \(A\)，解出 \(X_1\) 后就可以求出 \(k_i\)，也就可以求出别的 \(X_j\) 了。
u1s1 这题真是精神污染，写了我 3h……
const int MAXN=100;
const int MAXP=1200;
const int MOD=1e9+7;
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){x=1;y=0;return;} exgcd(b,a%b,y,x);y-=(a/b)*x;
}
int qpow(int x,ll e){
int ret=1;
for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
return ret;
}
int n,m,a[MAXN+5],b[MAXN+5],p[MAXP+5];
bool vis[MAXN+5];
void getpri(int x){
for(int i=2;i*i<=x;i++) if(x%i==0){
p[++m]=i;while(x%i==0) x/=i;
} if(x>1) p[++m]=x;
}
int ap[MAXN+5][MAXP+5],bp[MAXN+5][MAXP+5],ans=1;
ll ans1[MAXP+5],ans2[MAXN+5];
void calc(int x){
int tmpa=a[x],tmpb=b[x];
for(int i=1;i<=m;i++){
while(tmpa%p[i]==0) tmpa/=p[i],ap[x][i]++;
while(tmpb%p[i]==0) tmpb/=p[i],bp[x][i]++;
}
}
void solve(int a1,int b1,int c1,int a2,int b2,int c2){
// debug(20060729);
// printf("%dx+%dy=%d\n%dx+%dy=%d\n",a1,b1,c1,a2,b2,c2);
int lcm=a1/__gcd(a1,a2)*a2;
int mul1=lcm/a1,mul2=lcm/a2;
b1*=mul1;c1*=mul1;b2*=mul2;c2*=mul2;
if((c1-c2)%(b1-b2)) puts("-1"),exit(0);
int x,y;y=(c1-c2)/(b1-b2);
b1/=mul1;c1/=mul1;b2/=mul2;c2/=mul2;
int rem=c1-b1*y;if(rem%a1) puts("-1"),exit(0);
x=rem/a1;if(x<0||y<0) puts("-1"),exit(0);
// printf("%d %d\n",x,y);
for(int i=1;i<=m;i++) ans1[i]=ap[1][i]+x*bp[1][i];
// for(int i=1;i<=m;i++) printf("%d^%lld\n",p[i],ans1[i]);
memset(ans2,-1,sizeof(ans2));
for(int j=1;j<=n;j++){
for(int k=1;k<=m;k++){
if(vis[k]) continue;
if(!bp[j][k]){
if(ap[j][k]!=ans1[k]) return puts("-1"),void();
} else {
if(ap[j][k]>ans1[k]||(ans1[k]-ap[j][k])%bp[j][k]) return puts("-1"),void();
else if(~ans2[j]&&(ans1[k]-ap[j][k])/bp[j][k]!=ans2[j]) return puts("-1"),void();
else ans2[j]=(ans1[k]-ap[j][k])/bp[j][k];
}
}
}
for(int j=1;j<=m;j++) if(!vis[j])
ans=1ll*ans*qpow(p[j],ans1[j])%MOD;
printf("%d\n",ans);
}
bool combine(ll &a1,ll &m1,ll a2,ll m2){
// printf("%lld %lld %lld %lld\n",a1,m1,a2,m2);
ll k1,k2,g=__gcd(m1,m2);exgcd(m1,m2,k1,k2);
if((a2-a1)%g) return 0;ll t=((a2-a1)/g*k1%m2+m2)%m2;
return a1+=t*m1%(m1/g*m2),m1*=m2/g,a1=(a1%m1+m1)%m1,1;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
for(int i=1;i<=n;i++) getpri(a[i]),getpri(b[i]);
sort(p+1,p+m+1);m=unique(p+1,p+m+1)-p-1;
for(int i=1;i<=n;i++) calc(i);
for(int i=1;i<=m;i++){
int pos0=0,pos1=0;
for(int j=1;j<=n;j++){
if(!bp[j][i]) pos0=j;
else pos1=j;
}
if(pos0){
// printf("%d\n",i);
if(!pos1){
for(int j=1;j<=n;j++) if(ap[j][i]!=ap[1][i])
return puts("-1"),0;
ans=1ll*ans*qpow(p[i],ap[1][i])%MOD;vis[i]=1;
} else {
if(ap[pos0][i]<ap[pos1][i]) return puts("-1"),0;
if((ap[pos0][i]-ap[pos1][i])%bp[pos1][i]) return puts("-1"),0;
int cc=(ap[pos0][i]-ap[pos1][i])/bp[pos1][i];
// printf("%d %d %d\n",pos0,pos1,cc);
for(int j=1;j<=m;j++) ans1[j]=1ll*bp[pos1][j]*cc+ap[pos1][j];
memset(ans2,-1,sizeof(ans2));
for(int j=1;j<=n;j++){
for(int k=1;k<=m;k++){
if(vis[k]) continue;
if(!bp[j][k]){
if(ap[j][k]!=ans1[k]) return puts("-1"),0;
} else {
if(ap[j][k]>ans1[k]||(ans1[k]-ap[j][k])%bp[j][k]) return puts("-1"),0;
else if(~ans2[j]&&(ans1[k]-ap[j][k])/bp[j][k]!=ans2[j]) return puts("-1"),0;
else ans2[j]=(ans1[k]-ap[j][k])/bp[j][k];
}
}
}
for(int j=1;j<=m;j++) if(!vis[j])
ans=1ll*ans*qpow(p[j],ans1[j])%MOD;
printf("%d\n",ans);return 0;
}
}
} int pos=1;while(vis[pos]) pos++;
if(pos==m+1) return printf("%d\n",ans),0;
for(int i=1;i<=n;i++) swap(ap[i][pos],ap[i][1]),swap(bp[i][pos],bp[i][1]);
swap(vis[pos],vis[1]);swap(p[pos],p[1]);debug(1);
// printf("%d\n",pos);
for(int j=2;j<=m;j++) if(!vis[j]){
for(int i=2;i<=n;i++){
if(bp[1][1]*bp[i][j]!=bp[1][j]*bp[i][1]){
solve(bp[1][1],-bp[i][1],ap[i][1]-ap[1][1],
bp[1][j],-bp[i][j],ap[i][j]-ap[1][j]);
return 0;
}
}
} //debug(20060617);
ll A=ap[1][1]%bp[1][1],M=bp[1][1],mx=ap[1][1];
// debug(114514);
for(int i=2;i<=n;i++){
if(!combine(A,M,ap[i][1]%bp[i][1],bp[i][1]))
return puts("-1"),0;
chkmax(mx,ap[i][1]);
} //debug(20210406);
if(A<mx) A+=(mx-A+M-1)/M*M;
ll cc=(A-ap[1][1])/bp[1][1];
for(int i=1;i<=m;i++) ans1[i]=ap[1][i]+cc*bp[1][i];
// for(int i=1;i<=m;i++) printf("%d^%lld\n",p[i],ans1[i]);
memset(ans2,-1,sizeof(ans2));
for(int j=1;j<=n;j++){
for(int k=1;k<=m;k++){
if(vis[k]) continue;
if(!bp[j][k]){
if(ap[j][k]!=ans1[k]) return puts("-1"),0;
} else {
if(ap[j][k]>ans1[k]||(ans1[k]-ap[j][k])%bp[j][k]) return puts("-1"),0;
else if(~ans2[j]&&(ans1[k]-ap[j][k])/bp[j][k]!=ans2[j]) return puts("-1"),0;
else ans2[j]=(ans1[k]-ap[j][k])/bp[j][k];
}
}
}
for(int j=1;j<=m;j++) if(!vis[j])
ans=1ll*ans*qpow(p[j],ans1[j])%MOD;
printf("%d\n",ans);
return 0;
}
内容总结
以上是互联网集市为您收集整理的Codeforces 571E - Geometric Progressions（数论+阿巴细节题）全部内容，希望文章能够帮你解决Codeforces 571E - Geometric Progressions（数论+阿巴细节题）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。