学步园

最大公约数之和

描述

题目很简单，求出：

输入

每行一个数n（n<2^31)，以文件结束。

输出

每个结果占一行。

样例输入

12

样例输出

40

解题思路：

考虑n=12时，最大公约数有1、2、3、4、12。
gcd（1，12）=1，gcd（5，12）=1，gcd（7，12）=1，gcd（11，12）=1，
gcd（2，12）=2，gcd（10，12）=2，
gcd（3，12）=3，gcd（9，12）=3，
gcd（4，12）=4，gcd（8，12）=4，
gcd（6，12）=6，
gcd（12，12）=12，
所以：
gcd（1，12）+gcd（2，12）+gcd（3，12）+gcd（4，12）+gcd（5，12）+gcd（6，12）+
gcd（7，12）+gcd（8，12）+gcd（9，12）+gcd（10，12）+gcd（11，12）+gcd（12，12）
=4*1+2*2+2*3+2*4+1*6+1*12=40
我们可以发现：上式等价与
                          φ（12）*1+φ（6）*2+φ（4）*3+φ（3）*4+φ（2）*6+φ（1）*12
                       =4*1+2*2+2*3+2*4+1*6+1*12
                        =40 
其中φ（x)表示不超过x且与x互 素的正整数的个数，称为x的欧拉函数值 。φ函数的值 通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。具体实现见代码。

java代码：

 
 
import java.util.Scanner;
public class Main {
    public static int euler(int n)
    {
    	int sum=n;
    	for(int i=2;i*i<=n;i++)
    	{
    		if(n%i==0)
    		{
    			sum=sum/i*(i-1);
    			while(n%i==0)
    			{
    				n/=i;
    			}
    		}
    	}
    	if(n!=1)
    		sum=sum/n*(n-1);
    	return sum;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext())
        {
        	int number=scanner.nextInt();
        	long sum=0;
        	for(int i=1;i*i<=number;i++)
        	{
        		if(i*i==number&&number%i==0)
        		{
        			sum+=euler(i)*i;//两个因子都是i
        			break;
        		}
        		if(number%i==0)//两个因子不相等，一个是i，一个是k
        		{
        			int k=number/i;
        			sum+=euler(k)*i;
        			sum+=euler(i)*k;
        			
        		}
        	}
        	System.out.println(sum);
        }
        
    }
}