UVa 10820 - Send a Table（欧拉函数）

链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1761

 

题意：

有一道比赛题目，输入两个整数x、y（1≤x,y≤n），输出某个函数f(x,y)。
有位选手想交表（即事先计算出所有的f(x,y)，写在源代码里），但表太大了，源代码超过了比赛限制，需要精简。
那道题目有一个性质，即很容易根据f(x,y)算出f(x*k, y*k)（k是任意正整数），这样有一些f(x,y)就不需要保存了。
输入n（n≤50000），你的任务是统计最简的表里有多少个元素。例如，n=2时有3个：(1,1), (1,2), (2,1)。

 

分析：

本题的本质是：输入n，有多少个二元组(x,y)满足：1≤x,y≤n，且x和y互素。
不难发现除了(1,1)之外，其他二元组(x,y)中的x和y都不相等。设满足x<y的二元组有f(n)个，那么答案就是2f(n)+1。
对照欧拉函数的定义，可以得到f(n)=phi(2)+phi(3)+…+phi(n)。

 

代码：

import java.io.*;
import java.util.*;

public class Main {
    static final int UP = 50000;
    static int phi[] = new int[UP+5];
    
    static void constant() {
        for(int t = 2; t <= UP; t++) if(phi[t] == 0) {
            for(int i = t; i <= UP; i += t) {
                if(phi[i] == 0) phi[i] = i;
                phi[i] = phi[i] / t * (t-1);
            }
        }
        for(int i = 3; i <= UP; i++) phi[i] += phi[i-1];
    }
    
    public static void main(String args[]) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        constant();
        
        while(true) {
            int n = cin.nextInt();
            if(n == 0) break;
            System.out.println(2 * phi[n] + 1);
        }
        cin.close();
    }
}