题目
link
题解
看到这个东西，想到分解质因数
输入值≤2×109，所以根号下＜50000,50000内的指数不是很多，可以考虑枚举每一个质数，根据唯一分解定理来做
代码
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| #include<bits/stdc++.h>
using namespace std;
const int N = 50000;
int prime[N + 2];
int vis[N + 2];
int cnt = 0;
long long a0, a1, b0, b1;
int main()
{
for(int i = 2;i <= N;i++)
{
if(vis[i]) continue;
prime[++cnt] = i;
for(int j = i;j <= N;j += i)
{
vis[j] = 1;
}
}
int n;
scanf("%d", &n);
while(n --)
{
scanf("%lld%lld%lld%lld", &a0, &a1, &b0, &b1);
long long ans = 1;
bool ok = 1;
for(int i = 1;i <= cnt;i++)
{
long long d = 0, g = 0, c = 0, f = 0;
while(a0 % prime[i] == 0)
{
a0 /= prime[i];
c++;
}
while(a1 % prime[i] == 0)
{
a1 /= prime[i];
f++;
}
while(b0 % prime[i] == 0)
{
b0 /= prime[i];
d++;
}
while(b1 % prime[i] == 0)
{
b1 /= prime[i];
g++;
}
if(d == g && c == f)
{
ans *= (g - f + 1);
}
else if(d > g || c < f || ((d != g) && (c != f) && (g != f)))
{
ok = 0;
break;
}
}
vector<int> qwq;
if(a0 != 1) qwq.push_back(a0);
if(a1 != 1) qwq.push_back(a1);
if(b0 != 1) qwq.push_back(b0);
if(b1 != 1) qwq.push_back(b1);
sort(qwq.begin(), qwq.end());
for(int i = 0;i < qwq.size();i++)
{
long long d = 0, g = 0, c = 0, f = 0;
while(a0 % qwq[i] == 0)
{
a0 /= qwq[i];
c++;
}
while(a1 % qwq[i] == 0)
{
a1 /= qwq[i];
f++;
}
while(b0 % qwq[i] == 0)
{
b0 /= qwq[i];
d++;
}
while(b1 % qwq[i] == 0)
{
b1 /= qwq[i];
g++;
}
if(d == g && c == f)
{
ans *= (g - f + 1);
}
else if(d > g || c < f || ((d != g) && (c != f) && (g != f)))
{
ok = 0;
break;
}
}
if(!ok) cout << 0 << endl;
else cout << ans << endl;
}
return 0;
}
|