【洛谷P1072】Hankson 的趣味题

题目大意：给定四个数字 a,b,c,d，求满足 \(gcd(a,x)=b,lcm(c,x)=d\) 的 x 的个数。

题解：

解法1：根据 lcm 的性质，x 一定为 d 的约数。因此，直接枚举 d 的约数，并判断是否满足上述条件即可，时间复杂度较高。

解法2：解法一中直接枚举约数会导致有大量不满足条件的数字被枚举，导致复杂度的升高。仔细观察最大公约数和最小公倍数的性质可知，在算术基本定理中体现为质因子幂之间的联系。同时，x 的个数也可以转化成有多少种质因子分解使得上述条件成立。因此，在这里直接枚举 d 的每一个质因子，并利用算术基本定理之间的关系即可得知 x 的每一位的可能组成情况，最后利用乘法原理即可。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e5+10;

int n,a,b,c,d;

long long ans;

vector<int> p;

bool vis[maxn];

void prework(){

	vis[1]=1;

	for(int i=2;i<=1e5;i++)if(!vis[i]){

		p.push_back(i);

		for(int j=i;j<=1e5/i;j++)vis[i*j]=1;

	}

}

void solve(int pri){

	int pa=0,pb=0,pc=0,pd=0;

	while(a%pri==0)a/=pri,++pa;

	while(b%pri==0)b/=pri,++pb;

	while(c%pri==0)c/=pri,++pc;

	while(d%pri==0)d/=pri,++pd;

	if(pa==pb&&pd==pc)ans*=(pd-pb+1);

	else if(pa>pb&&pd>pc&&pb==pd)ans*=1;

	else if(pa>pb&&pd==pc)ans*=1;

	else if(pa==pb&&pd>pc)ans*=1;

	else ans=0;

}

void solve(){

	scanf("%d",&n);

	while(n--){

		ans=1;

		scanf("%d%d%d%d",&a,&b,&c,&d);

		for(int i=0;i<p.size();i++)if(d%p[i]==0)solve(p[i]);

		if(d!=1)solve(d);

		printf("%lld\n",ans);

	}

}

int main(){

	prework();

	solve();

	return 0;

}

巴特西

【洛谷P1072】Hankson 的趣味题

最新文章

热门文章