HDU - 1286 새 친구 찾기 (오로라 함수 + 질량 타 표)

새로운 친 구 를 찾다
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 10097    Accepted Submission(s): 5328
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
   
   
   
   

또 하나의 모 르 는 지식 인 오로라 함수, 계산 [1, n] 에서 n 과 서로 질 적 인 수 는 몇 가지 가 있 습 니까?
구체 적 인 정리:
오로라 함수, 수론 에서 구 해 에 사용 [1, n] 중과 n  호질수 개수 의 함 수 는 연구자 가 오로라 이기 때문에 오로라 함수 라 고 명명 되 었 다.
      통식:φ(x) = x (1 - 1 / p1) (1 - 1 / p2) (1 - 1 / p3)... (1 - 1 / pn), 그 중 p1, p2... pn 은 x 의 모든 질량 인수 이 고 x 는 0 이 아 닌 정수 이다.
      φ(1) = 1 (유일 과 1 의 상호 질의 수 (이하 1) 는 1 자체) 이다.(주의: 각 질량 인 수 는 하나 입 니 다. 예 를 들 어 12 = 2 * 2 * 3 그러면      φ(12) = 12 * (1-1/2) * (1-1/3)=4  )
      만약... 면 n = p^k  (  p 는 질 수)φ(n) = p ^ k - p ^ (k - 1) = (p - 1) p ^ (k - 1), (p 의 배 수 를 제외 하고 기타 수 는 모두 p 의 상호 질량 수).
      n = p (p 는 질 수) 이면  φ(n) = p-p^(1-1) = p-1。
오로라 함수 성질:
     1、  φ(mn) = φ(m) φ(n)
     2. n 이 홀수 라면,φ(2n) = φ(n). / / 이 건 범 위 를 줄 일 수 있 을 것 같 아 요.
코드:

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<set>
#include<sstream>
#include<map>
#include<vector>
using namespace std;
inline bool isprime(const int &n)
{
	if(n<=1)
		return false;
	else
	{
		for (int i=2; i*i<=n; i++)
			if(n%i==0)
				return false;
	}
	return true;
}
int prime[32768],k;
int main(void)
{
	int t,n,i;
	k=0;
	for (i=2; i<=32767; i++)//    
	{
		if(isprime(i))
			prime[k++]=i;
	}
	scanf("%d",&t);
	while (t--)
	{
		scanf("%d",&n);
		while (n%2==0&&(n/2)%2!=0)
		{
			n/=2;
		}//  n   （     ）
		int ans=n;
		for (i=0; prime[i]<=n; i++)
		{
			if(n%prime[i]==0)
				ans=ans/prime[i]*(prime[i]-1);//    
		}
		printf("%d
",ans);		
	}
	return 0;
}