# [Gold I] 서로소 [문제 링크](https://www.acmicpc.net/problem/9359) ## 문제 설명 <p>자연수 N이 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 수 중에서 N과 서로소인 것의 개수를 구하는 프로그램을 작성하시오.</p> <p>두 정수를 나눌 수 있는 양의 정수가 1밖에 없을 때, 두 정수를 서로소라고 한다. 즉, 두 수의 최대공약수가 1이면 서로소이다. 1은 모든 정수와 서로소이다.</p> ## 입력 <p>첫째 줄에 테스트 케이스의 개수 T (0 < T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, A, B, N이 주어진다. (1 ≤ A ≤ B ≤ 10¹⁵, 1 ≤ N ≤ 10⁹)</p> ## 출력 <p>각 테스트 케이스마다 A보다 크거나 같고, B보다 작거나 같은 자연수 중에서 N과 서로소인 것의 개수를 출력한다. </p> ## 풀이 포함 배제의 원리를 이용하여 풀었습니다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; ll a, b, n, cnt; vector<ll> arr; void back(int depth=0, int start=0, ll val=1) { if(val>b) return; if(depth) { if(depth%2) cnt += b/val - (a-1)/val; else cnt -= b/val - (a-1)/val; } for(int i=start;i<arr.size();i++) back(depth+1, i+1, lcm(val, arr[i])); } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; for(int tc=1;tc<=t;tc++) { cin >> a >> b >> n; cnt=0; arr.clear(); for(ll i=2;i*i<=n;i++) { if(n%i==0) { arr.push_back(i); while(n%i==0) n/=i; } } if(n!=1) arr.push_back(n); back(); cout << "Case #"<< tc << ": " << b-a+1-cnt << '\n'; } } ```