【HDOJ 1286】新しい友達を探す

1662 ワード

新しい友達を探す
Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 0   Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia 
Font Size: ← →
Problem Description
新年はもうすぐ着いて、“ブタの頭は協会を手伝います”は1つのパーティーをするつもりで、すでに既存の会員のN人を知っていて、会員を1からNまで番号をつけて、その中の会長の番号はN番で、会長と古い友达で、それではこの会員の番号はきっとNと1より大きい公約数があって、さもなくばすべて新しい友达で、今会長はいったい何人の新しい友达がいることを知りたいですか?プログラムを作って会長の計算を手伝ってください.
Input
1行目は、テストデータのグループ数CN(Case number,1Output
Nごとに、新しい友达の人数を出力し、CN行の出力を共有します.
Sample Input
2
25608
24027

Sample Output
7680
16016

Author
SmallBeer(CML)
Source
杭電ACM合宿チーム訓練試合(VII)
 
単純な数学の問題、同じ因子を持つ数を探します
 
#include <iostream>

using namespace std;

int main()
{
    int N;
    cin>>N;
    while(N--)
    {
        int Maxn,sum=0;
        cin>>Maxn;
        int A[33000];
        for(int i=1;i<Maxn;i++)
        {
            A[i]=i;
        }
        for(int i=2;i<Maxn;i++)
        {
            if(Maxn%i==0)
            {
                for(int j=1;i*j<Maxn;j++)
                    A[i*j]=0;
            }
        }
        for(int i=1;i<Maxn;i++)
            if(A[i])
            sum++;
        cout<<sum<<endl;
    }
    return 0;
}