uva10820（欧拉函数，排列组合）

/*
translation:
给定一个数n，任意两个元素组成的二元组（x,y）.其中xy均小于n。任意两个二元组之间定不存在
(k*xi, k*yi) = (xj, yj);问这样的二元组有多少个。

solution:
排列组合，欧拉函数
满足条件的二元组的两个元素之间肯定互素，如果两个元素不互素，肯定存在一个整数k使得有二元组
(x/k, y/k)。与题意相反。所以利用欧拉函数很容易求出phi[2...n]。又考虑到二元组是不对称
的，所以设f = phi[2]+...+phi[n]。再加上(1,1)这种情况。答案为2*f+1!

note:
date:
2016.9.26
*/
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int maxn = 50001 + 5;

int n, phi[maxn];

int main()
{
    while(cin >> n && n) {
for(int i = 2; i <= n; i++)phi[i] = 0;
phi[1] = 1;
for(int i = 2; i <= n; i++) if(!phi[i]) {
for(int j = i; j <= n; j += i) {
if(!phi[j])phi[j] = j;
phi[j] = phi[j] / i * (i-1);
}
}

long long res = 0;
for(int i = 2; i <= n; i++)res += phi[i];
cout << res*2 + 1 << endl;
    }
    return 0;
}