题目链接:
http://acm./showproblem.php?pid=4497
题目大意:
给出三个数的gcd和lcm,求出这三个数有多少种可能性
解题思路:
设lcm / gcd =(p1^r1)*(p2^r2)*(p3^r3)…(pm^rm)
设三个数为x, y, z;
有:
x=(p1^i1)*(p2^i2)*(p3^i3)…(pm^im)
y=(p1^j1)*(p2^j2)*(p3^j3)…(pm^jm)
z=(p1^k1)*(p2^k2)*(p3^k3)…(pm^km)
对于某个r,i、j、k里面一定有一个是r,并且一定有一个是0,所以i,j,k有一下3种情况:
r 0 0 ,有C(3,1)种
r 0 r ,有C(3,1)种
r 0 1~r-1 ,有(r-1)*A(3,3)种
所以一共是6*r种。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll n, m; 5 6 int main() 7 { 8int T; 9cin >> T;10while(T--)11{12 cin >> m >> n;13 if(n % m)14 {15 cout<<"0"<<endl;16 continue;17 }18 n /= m;19 ll ans = 1;20 for(ll i = 2; i * i <= n; i++)21 {22 if(n % i == 0)23 {24 int cnt = 0;25 while(n % i == 0)26 {27 cnt++;28 n /= i;29 }30 ans *= 6;31 ans *= cnt;32 }33 }34 if(n != 1)35 ans *= 6;36 cout<<ans<<endl;37}38return 0;39 }