HDOJ 1286 새로운 친구 찾기

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

2
25608
24027

 
Sample Output

7680
16016

 
처음에는 자신 이 생각 했 던 것 이 바로 폭력 이 었 다. 그리고 오 랜 친구 로부터 시작 했다. 즉, 먼저 오 랜 친구 의 수 를 폭력 으로 낸 다음 에 CN - 오 랜 친구 로 결 과 를 세 어 보 았 다. 그 생각 은 아무리 알고리즘 을 바 꿔 도 n ^ 2 등급 이 므 로 반드시 시간 을 초과 한 다 는 것 을 알 게 되 었 다.
그리고 문 제 를 다시 생각해 보 니 새로운 친구 번호 와 회장 번호 가 서로 질 적 이라는 사실 이 밝 혀 졌 다. 그래서 또 서로 질 적 인 노력 을 하기 시작 했다.
두 개의 수 는 서로 질 적 이다. 즉, 두 개의 수 는 공공 질 인자 가 없다. 즉, 두 개의 수의 최대 공약 수 는 1 이다.
구체 적 인 실현 방법 은 전전 상 제법 (유클리드 알고리즘) 이 공약수 로 공약수 가 1 인지 아 닌 지 를 판단 해 결론 을 내 리 는 것 이다.
다음은 두 수의 상호 질 여 부 를 판단 하 는 함수 의 실현 입 니 다.

void IsHz(int a, int b){
	int tmp,r;
	
	//先判断一下a,b的大小，约定一下a是较大的数
	if(a < b){
		tmp = a;
		a = b; 
		b = tmp;
	}
	
	//辗转相除拿最大公约数
	while(r=a%b){
		a = b;
		b = r;
	}
//	cout << "最大公约数是：" << b << endl;
	
	//判断最大公约数是否等于1，得出结论
	if(b==1){
		cout << "YES" << endl; 
	} else{
		cout << "NO" << endl;
	}
		 
} 

이렇게 하면 AC 가 될 줄 알 았 는데, 결 과 는 여전히 시간 을 초과 했다. 나 는 이미 더 좋 은 방법 을 생각 하지 못 했 고, 다른 사람 이 어떻게 썼 는 지 볼 수 밖 에 없 었 다.
검색 결과 에 따 르 면 이 문 제 는 오로라 함수 의 전형 적 인 응용 이다. 오로라 함수 누가 귀신 이 야!!
좋아, 그리고 오로라 함수 가 무엇 인지 보충 하기 시작 하 자.
오로라 함 수 는 n 보다 작고 n 과 서로 질 적 인 정수 (1 포함) 의 개 수 를 S (n) 로 기록 하고 Sn = n * (1 - 1/p1) * (1 - 1/p2) * (1 - 1/p3) *... * (1 - 1/pn) 가 있 습 니 다.
   그 중에서 p1, p2, p3... pn 은 n 의 모든 질 인자 이 고 n 은 0 이 아 닌 정수 입 니 다. 또한 S (1) = 1 (유일 과 1 의 상호 질 수 는 1 자체 입 니 다)
질 수 p 에 대해 서 는 S (p) = p - 1 이 있 습 니 다.
오로라 정리: 상호 질의 정수 a 와 n 에 대해 a ^ S (n) 가 있 습 니 다. ≡ 1(mod n)
모 n 동 여 의 개념 에 대해 약간 잊 어 버 렸 다.
두 개의 정수 a, b, 만약 에 그들 이 정수 m 로 나 누 어 얻 은 나머지 가 같다 면 a, b 는 모델 m 에 대해 같은 나머지 라 고 부 르 고 a 로 기록한다. ⊙ b (mod m). a 동 여 b 모드 m 또는 a 와 b 의 m 동 여 를 읽 습 니 다.
오로라 함수 에 대해 서 는 아직 많은 성질 이 있 으 니 여 기 는 전개 되 지 않 습 니 다.
그리고 나 서 나 는 어떻게 실현 하고 싶 었 을 까? 내 생각 은 먼저 CN 의 질 인 자 를 꺼 내 서 공식 적 으로 계산 하 는 것 이다. 분명히 이것 이 가장 멍청 한 방법 이 었 다. 나중에 이 동화 의 문제 풀이 보고 서 를 보 았 다.http://blog.csdn.net/u011514451/article/details/44946789, 코드 는 다음 과 같 습 니 다:

#include  
int oula(int n)  
{  
    int i,sum=n;  
    for(i=2;i<=n;i++)  
    if(n%i==0)  
    {  
        sum-=sum/i;  
        while(n%i==0)  
        {  
            n/=i;  
        }  
    }  
    return sum;  
}  
int main()  
{  
    int s,n;  
    scanf("%d",&s);  
    while(s--)  
    {  
        scanf("%d",&n);  
        printf("%d
",oula(n));  
    }  
    return 0;  
}  

그 는 CN 의 질 인 자 를 꺼 내지 않 았 지만 계산 과정 은 나무 가 적 었 다.
sum - = sum/i 는 처음에는 이해 하지 못 했 지만 사실은 오로라 의 정 리 였 다. CN 과 같은 질 인 자 를 가 진 수 (1 을 포함 하지 않 고 순환 초기 조건 은 이 문 제 를 설명 한다) 를 없 앴 다.
전형 적 인 오로라 함수, 오로라 정리의 응용 ~
처음으로 문제 풀이 노트 를 쓰 는데, 이 문 제 는 많은 시간 이 걸 렸 으 니, 절대 뿌리 지 마 세 요 ~