[G1] 백준 11689번 GCD(n, k) = 1 C++ 정수론, 오일러 피 함수

리뷰

 

https://www.acmicpc.net/problem/11689

출근시간 유튜브로 오일러 피 함수에 대해 공부하여 푼 문제 수학자들은 참 위대한 것 같다.

 

 

전역 변수

없음

 

 

함수

없음

 

 

문제풀이

1. long long타입의 변수 n에 값을 입력 받고, long long타입의 변수 ans에 n값을 저장한다.
2. long long타입의 변수 p를 2로 초기화 한다.
3. n의 양의 제곱근이 p보다 크거나 같을 경우 while루프를 수행한다.
4. n을 p로 나눈 나머지가 0일 경우 더 이상 나눠질 수 없을 때 까지 n에서 p를 나누어 준다.
5. ans에 ans를 p로 나눈 몫 * p - 1만큼의 값을 저장해 준다.
6. p를 증가시켜 준다.
7. 루프가 종료된 후 n값이 1보다 클 경우 ans에 ans를 n으로 나눈 몫 * n - 1만큼의 값을 저장해 준다.
8. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. ans / n보다 ans * (n - 1)을 먼저 해주었더니 오버플로우가 발생했다.
2. 두 연산의 위치를 바꾸어 주니 AC를 받았다.

 

참고 사항

• n값이 크지 않아 p를 2부터 순회해도 특이 사항이 없다.

 

정답 코드

#include<iostream>
#include<cmath>
using namespace std;

int main() {
	long long n; cin >> n;
	
	long long ans = n;
	long long p = 2;
	while (p <= sqrt(n)) {
		if (n % p == 0) {
			while (n % p == 0) n /= p;
			ans = ans / p * (p - 1);
		}
		p++;
	}
	if (n > 1) ans = ans / n * (n - 1);
	cout << ans;
}