백준 1016번 제곱 ㄴㄴ 수

문제 링크 : https://www.acmicpc.net/problem/1016

문제 풀이

(0) 생각

1보다 큰 제곱 수로 나누어지는 X 를 '제곱 ㅇㅇ 수' 라고 합시다.

저는 min ~ max 사이의 수들 중 제곱 ㅇㅇ 수를 세줄 것입니다.

정답은 min~max 사이 총 개수 -  제곱 ㅇㅇ 수 일 것입니다.

(1) 코드 15~34

 2의 제곱부터 차례로 max 전 까지 제곱 수를 모두 생각해줍니다.

 각 제곱 수의 배수들이 min~max 사이에 얼마나 들어가는지 세줍니다.

 이때 중복을 피하기 위해 배열을 하나 잡아 중복 체크를 해줍니다.

(2) 코드 25

 숫자 범위가 10^12 입니다. 굉장히 큽니다.

 그러나 min ~ max 사이 개수는 최대 10^6 입니다.

 따라서 각 제곱 ㅇㅇ 수 의 중복 체크를 해당 수로 하지 않고, 

 해당 수 - min 값 으로 해주었습니다.

(3) 시간...

 사실 2의 제곱 ~ max 전 까지 10^6 개입니다. ( 10^6 * 10^6 = 10^12 )

 각 제곱 수 마다 적당히 추가 처리가 필요합니다...

 사실 그냥 돌아갈 것 같아서 돌려보니 돌아갔습니다... 죄송합니다 ㅠ

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	const int MAX = 1000005;
	ll mini, maxi;
	bool visited[MAX];
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> mini >> maxi;
	ll cnt = maxi-mini+1;
	ll yesyes = 0LL; // 제곱 ㅇㅇ 수 세기
	for(ll i=2; i*i<=maxi; ++i){
	ll x = i*i; // 제곱수
	ll q = mini/x; // 몫
	if(q*x<mini) q++;
	while(1){
	ll curr = q*x;
	if(curr>maxi) break;
	int diff = (int)(curr-mini);
	if(visited[diff]) { // 중복확인
	q++;
	continue;
	}
	yesyes++;
	visited[diff] = true;
	}
	}
	cout << cnt - yesyes << '\n';
	return 0;
	}

view raw BOJ 1016.cpp hosted with ❤ by GitHub