题解：P1072 [NOIP2009 提高组] Hankson 的趣味题

题意

求满足

gcd (x,a_0)=a_1, lcm (x,b_0)=b_1

的

x

个数。

思路

2\times10^9

的暴力一看就是过不了的。这个时候我们容易想到求因数那道题，只需枚举

1

至

\sqrt{b_1}

，对于每一个

i

和

\frac{b_1}{i}

，我们判断它们是否互不重复，并且是否符合题意，此时答案数加一。

Code

CPP

#include <bits/stdc++.h>
#define int long long
#define fro for
using namespace std;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen (".in","r",stdin);
	//freopen (".out","w",stdout);
	int n;
	cin>>n;
	while (n--)
	{
		int a,aa,b,bb;
		cin>>a>>aa>>b>>bb;
		int sum=0;
		for (int i=1;i*i<=bb;i++)
		{
			if (bb%i==0)
			{
				int other=bb/i;
				if (b*i/__gcd(b,i)==bb&&__gcd(i,a)==aa)
				sum++;
				if (other!=i/*另一个因数与i不同*/&&b*other/__gcd(b,other)==bb&&__gcd(a,other)==aa)
				sum++;
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}

题解：P1072 [NOIP2009 提高组] Hankson 的趣味题

文章操作

题意

思路

Code

相关推荐

评论

题解：P1072 [NOIP2009 提高组] Hankson 的趣味题