Uva 10820 交表

题目链接：https://uva.onlinejudge.org/external/108/10820.pdf

题意：

对于两个整数 x,y，输出一个函数f(x,y)，有个选手想交表，但是，表太大，需要精简；已知：f(x,y) 可以算出 f(x*k,y*k)，所以有一些 f(x,y)可以不在表里。

给定一个 n，1<=x,y<=n，求最少的 f(x,y)个数。

设：

可以看出 x,y互素；

而且，和欧拉函数有一个特别的位置是，对角线，当x>1时，小于等于 x 的与 x 互素的数肯定没有 x，所以可以放心大胆的用欧拉函数。

注意的是，f(1,1)只有一个。

 #include <bits/stdc++.h>

 using namespace std;

 int euler_phi(int n)

 {

     int res = n;

     for(int i=; i*i<=n; i++)

     {

         if(n%i==)

         {

             n/=i;

             res = res - res / i;

             while(n%i==)

             {

                 n/=i;

             }

         }

     }

     if(n>) res = res - res / n;

     return res;

 }

 int sum[];

 void phi_table(int n,int* phi)

 {

     for(int i=; i<=n; i++)

         phi[i] = ;

     phi[]=;

     for(int i=; 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-);

             }

     sum[] = ;

     for(int i=; i<=; i++)

         sum[i] = sum[i-] + phi[i];

 }

 int main()

 {

     int n;

     int phi[];

     phi_table(,phi);

     while(scanf("%d",&n),n)

     {

         printf("%d\n",sum[n]*-);

     }

     return ;

 }