오일러 피 함수1 [백준] 11689 - GCD(n, k) = 1 (c++) https://www.acmicpc.net/problem/11689문제 요약N과 서로소인 수의 개수를 구해라 풀이 (√N)정수론오일러 피 함수오일러 피 함수를 통해 서로소의 개수를 구할 수 있다. N*∏(1-1/p) 이게 식이다. 시간복잡도를 줄이기 위해 √N까지만 돌게 되는데 이렇게 돌면 소수 하나가 n에 남게 될 수 있어서 마지막에 한 번 더 처리해야 한다. #include using namespace std;#define ll long longint main() { cin.tie(0)->sync_with_stdio(0); ll n,ans;cin>>n;ans=n; for(ll i=2;i*i1) ans-=ans/n; cout 2024. 10. 8. 이전 1 다음