警钟敲烂!如果你WA #2
查看原帖
警钟敲烂!如果你WA #2
1304256
xy_mc楼主2024/12/12 22:57

那么应该是没判断xxyy相等的情况!!!

题解:

因为gcd(x,a0)gcd(x,a_0)一定小于等于xx or a0a_0

xxa0a_0一定是gcd(x,a0)gcd(x,a_0)的倍数

由此得出: x=a1p1x=a_1*p_1 a0=a1p2a_0=a_1*p_2

p1=x/a1p_1=x/a_1 p2=a0/a1p_2=a_0/a_1

p1,p2p_1,p_2一定互质,可以自己举几个例子

所以 gcd(x/a1,a0/a1)=1gcd(x/a_1,a_0/a_1)=1

lcm(x,b0)lcm(x,b_0)同理,只不过变为除法

x=b1/p1x=b_1/p_1 b0=b1/p2b_0=b_1/p_2

p1=b1/xp_1=b_1/x p2=b1/b0p_2=b_1/b_0

得出 gcd(b1/x,b1/b0)=1gcd(b_1/x,b_1/b_0)=1

是人就知道观察两个式子可以发现xx既是a1a_1倍数又是b1b_1的因数

所以:枚举b1b_1 的因子(也就是xx),判断xx是否是a1a_1的倍数加上那两个式子就行了

#include<bits/stdc++.h>
#define IOS; ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int n,a0,a1,b0,b1; 
int gcd(int x,int y){
	if(y==0) return x;
	else return gcd(y,x%y);
}
int main(){
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a0>>a1>>b0>>b1;
		int sum=0;
		for(int j=1;j*j<=b1;j++){
			if(b1%j==0){
				if(j%a1==0&&gcd(j/a1,a0/a1)==1&&gcd(b1/b0,b1/j)==1){
					sum++;
				}
				int k=b1/j;
				if(j&k==j) continue;
				if(k%a1==0&&gcd(k/a1,a0/a1)==1&&gcd(b1/b0,b1/k)==1){
					sum++;
				}
			}
		}
		cout<<sum<<"\n";
	}
	return 0;
}

本蒟蒻的第一道绿题,必须写篇题解庆祝一下

2024/12/12 22:57
加载中...