【解题报告】洛谷P1072 Hankson 的趣味题

题目链接

https://www.luogu.com.cn/problem/P1072

思路

这道题目我们首先直接模拟，可以得到50pts的高分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
int T; 
int gcd(int a,int b)
{
	return b? gcd(b,a%b):a; 
}
int lcm(int a,int b)
{
	return 1ll*a*b/gcd(a,b);
}
int main()
{
	cin>>T;
	while(T--)
	{
		int a0,a1,b0,b1;
		int cnt=0;
		cin>>a0>>a1>>b0>>b1;
		for(int i=1;i<=max(a1,b1);i++)
		{
			if(gcd(i,a0)==a1&&lcm(i,b0)==b1)
			cnt++;
		}
		cout<<cnt<<'\n';
	}
	return 0;
}

然后发现可以提前判断一下能不能有，于是我们得到了80pts的高分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
int T; 
int gcd(int a,int b)
{
	return b? gcd(b,a%b):a; 
}
int lcm(int a,int b)
{
	return 1ll*a*b/gcd(a,b);
}
int main()
{
	cin>>T;
	while(T--)
	{
		int a0,a1,b0,b1;
		int cnt=0;
		cin>>a0>>a1>>b0>>b1;
		if(b1%a1!=0)
		{
			cout<<0<<'\n';
			continue;
		}
		bool flag=false;
		int add=1;
		//cout<<"They are :";
		for(int i=1;i<=max(a1,b1);i+=add)
		{
			if(b1%i==0)
			{
				if(gcd(i,a0)==a1&&lcm(i,b0)==b1)
				{
				//	cout<<i<<" ";
					if(!flag)
					add=i,flag=true;
					cnt++;
				}
			}
		}
		//cout<<'\n';
		cout<<cnt<<'\n';
	}
	return 0;
}

最后我们正经分析

我们可以把 lcmlcm 变成 gcdgcd ，然后最大公约数可以直接同除

把他们的最大公约数变成一

然后再枚举，就快多了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
int T; 
int gcd(int a,int b)
{
	return b? gcd(b,a%b):a; 
}
int lcm(int a,int b)
{
	return 1ll*a*b/gcd(a,b);
}
int main()
{
	cin>>T;
	while(T--)
	{
		int a0,a1,b0,b1;
		int cnt=0;
		cin>>a0>>a1>>b0>>b1;
		if(b1%a1!=0)
		{
			cout<<0<<'\n';
			continue;
		}
		bool flag=false;
		int add=1;
		//cout<<"They are :";
		for(int i=1;i*i<=b1;i++)
		{
			if(b1%i==0)
			{
				if(i%a1==0&&gcd(i/a1,a0/a1)==1&&gcd(b1/b0,b1/i)==1)
				cnt++;
				int j=b1/i;
				if(i==j) continue;
				if(j%a1==0&&gcd(j/a1,a0/a1)==1&&gcd(b1/b0,b1/j)==1)
				cnt++;
			}
		}
		//cout<<'\n';
		cout<<cnt<<'\n';
	}
	return 0;
}