-
[PS] 백준 11689번: GCD(n, k) = 1문제해결 2023. 11. 20. 14:44
1'000'000까지의 소수를 모두 만들고,
소인수분해 한 후 오일러 곱 공식을 이용해서 풀려고 했다.
하지만 반례를 못찾아서 계속 끙끙대다
결국 답지를 열어버렸다.
반례는, 소인수분해를 했을 때, 소인수가 p, q, r, s일 경우
$ans = n\times \left ( 1-\frac{1}{p} \right )\times \left ( 1-\frac{1}{q} \right )\times \left ( 1-\frac{1}{r} \right )\times \left ( 1-\frac{1}{s} \right )$
이 답이 되는데, s가 만약 1'000'000보다 큰 수라면, 해당 연산에 포함되지 못해 생기는 문제였다.
남은 s를 소인수에 추가해서 해결했다.
저번에도 정확히 같은 문제를 겪었었는데, 답지 보는걸 좀만 더 참고 생각해볼걸 그랬다.
#include <bits/stdc++.h> using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i < static_cast<long long>(N); i++) #define FORL(e, S) for (auto& e : S) #define ll long long int ll n; #define MAX 1'000'000 int is_prime[MAX + 1]; vector<int> primes; int main() { cin >> n; if (n == 1) { cout << 1 << endl; return 0; } for (int i = 0; i <= MAX; i++) is_prime[i] = true; for (int i = 2; i <= MAX; ++i) { if (!is_prime[i]) continue; for (int j = i * 2; j <= MAX; j += i) is_prime[j] = false; } for (int i = 2; i <= MAX; i++) if (is_prime[i]) primes.push_back(i); set<double> s; ll original_n = n; for (int i = 0; i < primes.size(); ++i) { if (n % primes[i] == 0) { s.insert(1.0 - 1.0 / primes[i]); n /= primes[i]; --i; } } if (n != 1 && n != original_n) s.insert(1.0 - 1.0 / n); if (s.size() == 0) cout << original_n - 1 << endl; else { FORL(e, s) original_n *= e; cout << original_n << endl; } }
'문제해결' 카테고리의 다른 글
[PS] 백준 9251번: LCS, 백준 5582번: 공통 부분 문자열 (2) 2023.11.20 [PS] 백준 9935번: 문자열 폭발 (0) 2023.11.20 [PS] 백준 17390번: 이건 꼭 풀어야 해! (입출력 관련) (1) 2023.11.09 [PS] 백준 1016번: 제곱 ㄴㄴ 수 (0) 2023.11.09 [PS] 백준 1882번: 분수 찾기, 30449번: Reafy 수열 (0) 2023.11.07