LightOJ 1236 Pairs Forming LCM

  • 2018-08-08
  • 22
  • 0

题目:

Find the result of the following code:

A straight forward implementation of the code may time out. If you analyze the code, you will find that the code actually counts the number of pairs (i, j) for which lcm(i, j) = n and (i ≤ j).

Input:

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 10^{14}).

Output:

For each case, print the case number and the value returned by the function ‘pairsFormLCM(n)’.

Sample Input:

15
2
3
4
6
8
10
12
15
18
20
21
24
25
27
29

Sample Output:

Case 1: 2
Case 2: 2
Case 3: 3
Case 4: 5
Case 5: 4
Case 6: 5
Case 7: 8
Case 8: 5
Case 9: 8
Case 10: 8
Case 11: 5
Case 12: 11
Case 13: 3
Case 14: 4
Case 15: 2

题目链接

先对N,i,j进行素因子分解

N=p_{1}^{e_{1}}\times p_{2}^{e_{2}}\times …\times p_{k}^{e_{k}}

i=p_{1}^{i_{1}}\times p_{2}^{i_{2}}\times …\times p_{k}^{i_{k}}

j=p_{1}^{j_{1}}\times p_{2}^{j_{2}}\times …\times p_{k}^{j_{k}}

\because LCM(i,j)=N

\therefore i_{x}<=e_{x},j_{x}=e_{x}i_{x}=e_{x},j_{x}<=e_{x}

所以对于每一个i_{x}和j_{x}2\times e_{x}+1种组合方式

这样可以算出所有ij的组合方式有(2\times e_{1}+1)\times(2\times e_{2}+1)\times…\times(2\times e_{k}+1)

题目代码规定了ij的大小关系,所以将算得结果+1)\times2即为最终结果

题目N的最大范围到10^{14},对于素数筛来说范围过大,所以素数只筛到\sqrt{10^{14}}=10^{7},素因子分解后特判一下数据大小即可。

AC代码:

评论

还没有任何评论,你来说两句吧