原题
题意
已知三个数x,y,z的gcd和lcm，求有多少种可能性。
分析
- 若lcm%gcd！=0，则不存在任何可能性。
若lcm%gcd==0：
令d=lcm/gcd，对d进行唯一分解：
d = p1^a1 p2^a2 p3^a3 ……
若要满足这样的条件，x,y,z每个数首先要满足gcd的唯一分解。所以对x/g,y/g,z/g进行容斥：
设l/g中某一素数p的指数为cnt，则只有满足这三个数中至少有一个数的p的指数为cnt（否则最小公倍数不是l），至少有一个数的p的指数为0（否则最大公约数不是1）
共三种情况：①一个数的p的指数为cnt，一个数的p的指数为0，另一个数的p的指数取1~cnt-1，方案数为：C(3,1)C(2,1)(cnt-1)
②两个数的p的指数为cnt，一个数的p的指数为0，方案数为：C(3,1)
③一个数的p的指数为cnt，两个个数的p的指数为0，方案数为：C(3,1)
注意：如果存在素数大于10^5，则必定只有一个，且其指数为1
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
| #include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
int vis[1000007],num;
int pri[1000007];
void prime(int n){
memset(vis,0,sizeof(vis));
for(int i=2;i<=n;i++){
if(vis[i]==0){
vis[i]=1;
pri[num++]=i;
for(int j=2;j<=n/i;j++){
vis[i*j]=1;
}
}
}
}
int main()
{
int t;
ll ans,g,l;
num=0;
prime(1000000);
while(scanf("%d",&t)!=EOF){
while(t--){
scanf("%I64d%I64d",&g,&l);
if(l%g!=0){
printf("0\n");
}
else{
ans=1;
ll d=l/g;
for(int i=0;i<num;i++){
if(d%pri[i]==0){
ll n=0;
while(d%pri[i]==0){
n++;
d/=pri[i];
}
ans*=6*n;
}
}
if(d>1){
ans*=6;
}
printf("%I64d\n",ans);
}
}
}
return 0;
}
|
