HDOJ 1286 새로운 친구 찾기 (수론) (오로라 함수)

새로운 친 구 를 찾다
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 10305    Accepted Submission(s): 5439
Problem Description
새해 가 다가 오고 있 습 니 다. '돼지 머리 방 협회' 는 모임 을 준비 하고 있 습 니 다. 기 존의 회원 N 명 을 알 고 회원 을 1 부터 N 까지 번호 가 있 습 니 다. 그 중에서 회장 의 번 호 는 N 번 입 니 다. 회장 님 과 오 랜 친구 라면 이 회원 의 번 호 는 N 과 1 이상 의 공약수 가 있 을 것 입 니 다. 그렇지 않 으 면 모두 새로운 친구 입 니 다. 지금 회장 님 은 도대체 몇 명의 새로운 친구 가 있 는 지 알 고 싶 습 니 다.프로그램 을 짜 서 회장 님 계산 을 도와 주세요.
 
Input
첫 번 째 줄 은 데 이 터 를 테스트 하 는 그룹 수 CN (Case number, 1 & lt; CN & gt; 10000) 이 고, 이 어 CN 행 정수 N (1 & gt; n & gt; 32768) 이 회원 수 를 나타 낸다.
 
Output
모든 N 에 대해 새로운 친 구 를 출력 하 는 사람 수 는 모두 CN 줄 로 출력 합 니 다.
 
Sample Input

   
   
   
   

    
    
    
    2
25608
24027
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    7680
16016
   
   
   
   

 
첫 번 째 방법 은 간단 한 인자 제거 입 니 다. n 의 인자 와 n 을 포함 한 인 자 를 모두 제거 하면 새로운 친구 의 수 를 찾 을 수 있 습 니 다.

#include<iostream>
#include<cstdio>
using namespace std;
const int N=32790;
int primer[N];
int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            primer[i]=1;//        0
        for(int i=2;i<=n;i++)
        {
            if(n%i==0)
                for(int j=i;j<=n;j+=i)
                    primer[j]=0;//   n              0，  
        }
        int sum=0;
        for(int i=1;i<=n;i++)// 1  ，      （1  ）
            sum+=primer[i];
            printf("%d
",sum);
    }
    return 0;
}

두 번 째 는 오로라 함 수 를 이용 하여 해 를 구 하 는 것 이다. 오로라 함수 의 정 의 를 방금 알 았 다. 수론 에서 정수 n, 오로라 함 수 는 n 보다 작은 숫자 에서 n 과 서로 질 적 인 수의 수량 이다.
공식:
 
그 중에서 p1, p2... pn 은 x 의 모든 질량 인수 이 고 x 는 0 이 아 닌 정수 입 니 다.φ(1) = 1 (유일 과 1 의 상호 질의 수 (1 보다 작 음) 은 1 자체 다.(주의: 각 질량 인 수 는 하나 입 니 다. 예 를 들 어 12 = 2 * 2 * 3 그러면φ(12) = 12 * (1 - 1 / 2) * (1 - 1 / 3) = 4 (백과사전 에서 유래)
코드 (상용 phi 템 플 릿):

#include<iostream>
#include<cstdio>
using namespace std;
int phi(int n)//      phi    
{
    int ans,i,k;
    if(n==1)
       ans=0;
    else
    {
        ans=n;
        k=1;
        for(i=2;n!=1;i+=k)
        {
            if(n%i==0)
            {
                ans*=(i-1);//         
                ans/=i;
                while(n%i==0)//      p1, p2……pn x      
                  n/=i;
                i=k;
            }
        }
    }
    return ans;
}
int main()
{
    int n,t;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            cin>>n;
            cout<<phi(n)<<endl;
        }
    }
    return 0;
}