GCD and LCM
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 40 Accepted Submission(s): 22
Problem Description
Given two positive integers G and L, could you tell me how many solutions of (x, y, z) there are, satisfying that gcd(x, y, z) = G and lcm(x, y, z) = L?
Note, gcd(x, y, z) means the greatest common divisor of x, y and z, while lcm(x, y, z) means the least common multiple of x, y and z.
Note 2, (1, 2, 3) and (1, 3, 2) are two different solutions.
Note, gcd(x, y, z) means the greatest common divisor of x, y and z, while lcm(x, y, z) means the least common multiple of x, y and z.
Note 2, (1, 2, 3) and (1, 3, 2) are two different solutions.
Input
First line comes an integer T (T <= 12), telling the number of test cases.
The next T lines, each contains two positive 32-bit signed integers, G and L.
It’s guaranteed that each answer will fit in a 32-bit signed integer.
The next T lines, each contains two positive 32-bit signed integers, G and L.
It’s guaranteed that each answer will fit in a 32-bit signed integer.
Output
For each test case, print one line with the number of solutions satisfying the conditions above.
Sample Input
2
6 72
7 33
6 72
7 33
Sample Output
72
0
0
Source
Recommend
liuyiding
对G和L 分别进行合数分解。
很显然，如果G中出现了L中没有的素数，或者指数比L大的话，肯定答案就是0了、
对于素数p,如果L中的指数为num1,G中的指数为num2.
显然必须是num1 >= num2;
3个数p的指数必须在num1~num2之间，而且必须有一个为num1,一个为num2
容斥原理可以求得种数是：
(num1-num2+1)*(num1-num2+1)*(num1-num2+1) -
2*(num1-num2)*(num1-num2)*(num1-num2) +
(num1-num2-1)*(num1-num2-1)*(num1-num2-1);
然后乘起来就是答案：
/* ***********************************************
Author :kuangbin
Created Time :2013/8/24 12:48:31
File Name :F:\2013ACM练习\比赛练习\2013通化邀请赛\1005.cpp
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std; const int MAXN = ;
int prime[MAXN+];
void getPrime()
{
memset(prime,,sizeof(prime));
for(int i = ;i <= MAXN;i++)
{
if(!prime[i])prime[++prime[]] = i;
for(int j = ;j <= prime[] && prime[j] <= MAXN/i;j++)
{
prime[prime[j]*i] = ;
if(i % prime[j] == )break;
}
}
}
long long factor[][];
int fatCnt;
int getFactors(long long x)
{
fatCnt = ;
long long tmp = x;
for(int i = ; prime[i] <= tmp/prime[i];i++)
{
factor[fatCnt][] = ;
if(tmp % prime[i] == )
{
factor[fatCnt][] = prime[i];
while(tmp % prime[i] == )
{
factor[fatCnt][] ++;
tmp /= prime[i];
}
fatCnt++;
}
}
if(tmp != )
{
factor[fatCnt][] = tmp;
factor[fatCnt++][] = ;
}
return fatCnt;
}
int a[],b[];
map<int,int>mp1,mp2;
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
getPrime();
//for(int i = 1;i <= 20;i++)
//cout<<prime[i]<<endl;
int n,m;
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
mp1.clear();
mp2.clear();
getFactors(m);
int cnt1 = fatCnt;
for(int i = ;i < cnt1;i++)
{
mp1[factor[i][]] = factor[i][];
a[i] = factor[i][];
//printf("%I64d %I64d\n",factor[i][0],factor[i][1]);
}
getFactors(n);
int cnt2 = fatCnt;
bool flag = true;
for(int i = ;i < cnt2;i++)
{
mp2[factor[i][]] = factor[i][];
if(mp1[factor[i][]] < factor[i][])
flag = false;
b[i] = factor[i][];
//printf("%I64d %I64d\n",factor[i][0],factor[i][1]);
}
if(!flag)
{
printf("0\n");
continue;
}
int ans = ;
for(int i = ;i < cnt1;i++)
{
int num1 = mp1[a[i]];
int num2 = mp2[a[i]];
if(num1 == num2)
ans *= ;
else
{
long long tmp = (num1-num2+)*(num1-num2+)*(num1-num2+);
tmp -= *(num1-num2)*(num1-num2)*(num1-num2);
tmp += (num1-num2-)*(num1-num2-)*(num1-num2-);
ans *= tmp;
}
}
printf("%d\n",ans);
}
return ;
}