本文共 2177 字,大约阅读时间需要 7 分钟。
【题目】
Time Limit: 2 Sec Memory Limit: 128 MB
Submit: 69 Solved: 24 [][][]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
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"
For each test case, print one line with the number of solutions satisfying the conditions above.
2 6 72 7 33
72 0
【题意】
给定三个数的最大公约数x与最小公倍数y,问存在多少对符合要求的(a,b,c)。
【思路】
简单的思考一下,abc一定属于[x,y]并且是x的倍数,由此得若y%x!=0,则不存在,输出0。
根据唯一分解定理每个a,b,c都可以分成素数幂形式;
a=p1^a1*p2^a2*…pn^an;
b=p1^b1*p2^b2*…pn^bn;
c=p1^c1*p2^c2*…pn^cn;
gcd(a,b,c)=p1^min(a1,b1,c1)*…pn^min(an,bn,cn);
lcm(a,b,c)=p1^max(a1,b1,c1)*…pn^max(an,bn,cn);
显然对于每个质因数,只要三个数中有一个数的质因数的个数满足等于max(a,b,c)就可以了。这样来考虑的话,三个数都要有最大公约数的部分,其余的部分就是由lcm/gcd里面的质因子构成。这里面的因子可能会有 2 2 3 这样的情况, 不同的因子之间是不会相互干扰的,但是相同的会出现干扰,因为不能同时将相同的因子都放在三个位置上,这样最大公约数就的要乘上这个因子。对于单种因子来说,每种因子选择两个位置放置有 3 种情况,而两个位置里边选择一个位置放全部即n个因子有 2 种情况, 就有 3 * 2 =6 种情况,而另一个位置可以放0-n个因子有n种情况,这样化简后就是6 * n。由于不同因子互不干扰,所以最后的答案是各质因数的放置情况的乘积。
对不起我没有脑子...
【代码】
#include#include #include #include #include #include #include