글 읽기 - 어떤 부분에서 틀렸을까요?

plan222 3년 전 0

루트 10억까지의 소수를 구하고, n을 소인수 분해해 set에 집어넣었습니다.

그리고 소수 i 개를 가지고 만들 수 있는 조합을 생성해 factor[i]에 넣었습니다.

포함 배제의 원리를 이용해 순차적으로 빼거나 더해주었습니다.

혹시 어느 부분이 틀렸을까요?

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>

#define MAX(A,B) A>B?A:B
#define MIN(A,B) A<B?A:B
#define forn(i,n) for(long long i=0;i<n;i++)
#define ll long long
ll gcd(ll a, ll b) { return a % b ? gcd(b, a % b) : b; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
ll wasdX[4] = { 1,0,-1,0 }; ll wasdY[4] = { 0,1,0,-1 };
using namespace std;

bool notPrime[32000];
int primeList[15000], pl;
ll a, b, n;
void makePrime() // 루트 10억까지의 소수를 구함
{
	for (int i = 2; i < 180; i++) //루트 32000은 약 179 
	{
		if (notPrime[i])
			continue;
		for (int j = i * 2; j < 32000; j += i) //루트 10억은 약 31623
			notPrime[j] = true;
	}
    
	for (int i = 2; i < 32000; i++) //구한 소수를 배열에 저장, 최대 인덱스는 pl-1 까지
	{
		if (!notPrime[i])
		{
			primeList[pl] = i;
			pl++;
		}
	}
}

ll getSize(ll a, ll b, ll num) //A B 구간에 num이 얼마나 들어있는지
{
	ll result = (b - a + 1) / num;
	ll remain = (b - a + 1) % num;
	if (remain - b % num > 0)
		result++;
	return result;
}

ll cntc(bool isAdd, set<ll> v) //set에 들어있는 원소가 들어있는 갯수만큼 각각 더하거나 빼줌
{
	ll cur = 0;
	set<ll>::iterator iter;
	for (iter = v.begin(); iter != v.end(); iter++)
	{
		if (isAdd)
			cur += getSize(a, b, *iter);
		else
			cur -= getSize(a, b, *iter);
	}
	return cur;
}

void solve(int t)
{
	cin >> a >> b >> n;
	set<ll> factor[11]; //중복 방지 set 이용
	ll cnt = b - a + 1;

	for (int i = 0; i < pl; i++) //n 소인수 분해하기
	{
		while (!(n % primeList[i]))
		{
			factor[0].insert(primeList[i]);
			n /= primeList[i];
		}

	}

	for (int i = 1; i < factor[0].size(); i++) //factor[i] 는 서로다른 소수 i개로 만들 수 있는 조합
	{
		set<ll>::iterator iter, iter1;
		for (iter = factor[i - 1].begin(); iter != factor[i - 1].end(); iter++)
		{
			for (iter1 = factor[0].begin(); iter1 != factor[0].end(); iter1++)
			{
				if (*iter % *iter1 == 0 || *iter1 % *iter == 0)
					continue;
				factor[i].insert((*iter) * (*iter1));
			}
		}
	}

	bool isAdd = false;
	for (int i = 0; i < factor[0].size(); i++)  //시작할 땐 더하고 그 이후는 번갈아감
	{
		cnt += cntc(isAdd, factor[i]);
		isAdd = !isAdd;
	}
	printf("Case #%d: %lld\n", t, cnt);

}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); //cout.tie(NULL);
	ll t = 1;
	cin >> t;
	ll tmp = t;

	makePrime();
	while (t--)
	{
		solve(tmp - t);
	}

}

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

문제

문제

출처

ICPC

어떤 부분에서 틀렸을까요?

plan222 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말