HRBUST-2227

テーマリンク:http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2227
Phi関数
Time Limit:500 MS
メモリLimit:32768 K
Total Submit:498(306 users)
Total Acceptted:336(295 users)
Rating: 
Special Jundge: No.
Description
整数を入力します n,出力 phi(n)phi(n) 以下を指定 n かつては n 相互の正の整数の数.
Input
入力データには1行が含まれています.整数が含まれています. n(1<=n<=1000).
Output
対応する答えを示す行を出力します.
Sample Input
10 5 99
Sample Output
4 4 60
ベント
以下 10 かつては 10 相互の数はあります.1、3、7、9 .
 
与えられたデータの範囲が小さいので、いくら操作しても大丈夫です.
二つの書き方を与える
一つ目はnbn点で、効率は高いですが、二つ目の必要な空間よりちょっと大きいです.

#include 
#include 

using namespace std;

int phi[1000005];

void phi_table(int 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);
            }
}


int main()
{
    int n;
    phi_table(10000);
    while(~scanf("%d",&n))
        printf("%d
",phi[n]);
    return 0;
}

二つ目はgcdで一つずつ判断して、1からnを遍歴すればいいです.最大公因数が1なら記録してください.運行効率はちょっと低いですが、1<=n==1000は絶対に足ります.

#include 
#include 
using namespace std;

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        int ans = 0;
        for(int i = 1;i <= n; i++)
            if(gcd(i, n) == 1)
            ans++;
        printf("%d
", ans);
    }
    return 0;
}