글 읽기 - 거의다 온거 같은데 ㅠㅠ 모르겠습니다..

sotter1020 4년 전 0

원리는 알겠는데.. 거의 다 한거 같은데

잘모르겠습니다.. 주석 있어요 ㅠㅠ

#include<iostream>
#include<vector>
#include<cmath>
#include<string>
using namespace std;
typedef long long ll;
ll TC, N, A, B;
bool prime[100010];
vector<ll> p;
int main() {
	cin >> TC;
	for (int i = 2; i <= sqrt(10e9); i++) {
		if (prime[i]) continue;
		for (int j = 2; j * i <= sqrt(10e9); ++j)
			prime[j*i] = true; // 소수 구하기
	}
	for (int i = 2; i <= sqrt(10e9); ++i)
		if (!prime[i])
			p.push_back(i); // 소수인것들 push_back
	for (int t = 1; t <= TC; ++t) {
		vector<ll> set;
		cin >> A >> B >> N;
		if (N == 1) {
			cout << "Case #" << t << ": " << 0 << endl;
			continue;
		}
		for (auto pr : p)
			if (N % pr == 0)
				set.push_back(pr); // N과 소수인것들 골라내기
		ll ans = B - A + 1; // A <= K <= B에서 K의 개수
		for (int k = 1; k < (1 << set.size()); ++k) {
			ll div = 1;
			int cnt = 1;
			for (int j = 0; j < set.size(); ++j)
				if (k&(1 << j)) div *= set[j], cnt *= -1; // 비트가 켜져있는 것들만큼 곱해준다.
                                                          // cnt 교집합 없애기위한 sign부호
			ans += cnt * abs(A / div - B / div);          // A의 집합과 B의 집합을 수 차이
		}
		cout << "Case #" << t << ": " << ans << endl;
	}
	return 0;
}

windflower 4년 전 0

실수오차가 매우 클 수 있습니다. 정수와 실수를 비교하기 보다는 i*i<10e9 사용하세요.

2. A와 B가 N과 서로소가 아닐 때 문제가 될 수 있을 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

거의다 온거 같은데 ㅠㅠ 모르겠습니다..

sotter1020 4년 전 0

windflower 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말