POJ 2480 Longge’s problem

  • 2018-08-07
  • 7
  • 0

题目:

Longge is good at mathematics and he likes to think about hard mathematical problems which will be solved by some graceful algorithms. Now a problem comes: Given an integer N(1 < N < 2^31),you are to calculate ∑gcd(i, N) 1<=i <=N.

“Oh, I know, I know!” Longge shouts! But do you know? Please solve it.

Input:

Input contain several test case.
A number N per line.

Output:

For each N, output ,∑gcd(i, N) 1<=i <=N, a line

Sample Input:

2
6

Sample Output:

3
15

题目链接

\sum_{i=1}^{N}gcd(i,N)gcd(i,N)一定是N的因子,所以使用循环变量i1 \rightarrow \sqrt{N}中遍历N的因子,因子i\sum_{i=1}^{N}gcd(i,N)中出现的次数是Phi(\frac{n}{i})同理可以算出因子\frac{n}{i}\sum_{i=1}^{N}gcd(i,N)中出现的次数是Phi(i),将i\times Phi(\frac{n}{i})+\frac{n}{i}\times Phi(i)加入到结果中继续遍历即可。

AC代码:

评论

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