zcmu--1796: wjw的数学题（素数筛+思维）

1796: wjw的数学题

Time Limit: 2 Sec  Memory Limit: 128 MB Submit: 83  Solved: 28 [Submit][Status][Web Board]

Description

Wjw recently encountered a mathematical problem .. given two positive integers x and y, how many kinds of schemes (a, b, c) make their gcd = x, lcm = y

Input

First line comes an integer T (T <= 12), telling the number of test cases. The next T lines, each contains two positive  integers, x and y. The all input is guaranteed to be within the "int"

Output

For each test case, print one line with the number of solutions satisfying the conditions above.

Sample Input

2

6 72

7 33

Sample Output

72

0

HINT

Source

jnxxhzz

【题意】给你三个数的最小公倍数和最大公约数，让你求可能的这三个数有多少种组合。

【分析】参考（here）

三个数的最大公约数是x,最小公倍数是y，所以，y必然能整除x，如果不能的话，即不符合，输出0；那么问题就简化为3个数的最小公倍数是y/x，最大公约数是1. 所以这三个数必然互质。三个数的gcd是1，把a,b,c分别质因数分解可以得到： a=q1^p1*q2^p2*q3^p3.... b=q1^pp1*q2^pp2*q3^pp3.... c=q1^ppp1*q2^ppp2*q3^ppp3.... 那么，x,y,z的gcd：q1^min(p1,pp1,ppp1)*q2^min(p2,pp2,ppp2)                      lcm：q1^max(p1,pp1,ppp1)*q2^max(p2,pp2,ppp2)所以，要求每个质因子的个数，然后组合数。 这里，假设第一个因子2，最小是0，最大是t，那么把这0和t分给两个数，第三个数就有t+1种可能性，那么这三个数就有6(t+1)种可能性。但是，如果有两个数相等的话，会出现重复的情况，共6种情况（草稿纸算算就有了），减掉，就正好每次ans*6t。

【代码】

#include<bits/stdc++.h> using namespace std; int prime[1000000]; int f[10000000]; void init() { int len=0; memset(f,0,sizeof(f)); for(int i=2;i<1000000;i++) { if(!f[i]) { prime[len++]=i; for(int j=i+i;j<10000000;j+=i) f[j]=1; } } } int main() { init(); int t;scanf("%d",&t); while(t--) { int x,y,ans=1; scanf("%d%d",&x,&y); if(y%x)ans=0; else { y/=x; int t; for(int i=0;prime[i]<=y;i++) { if(y%prime[i]==0) { t=0; while(y%prime[i]==0) y/=prime[i],t++; ans*=6*t; } } } printf("%d\n",ans); } }