[BOJ 11290 // C++] Wonowon

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 11290번 문제인 Wonowon이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/11290 

11290번: Wonowon

$k$번째 wonowon 수를 $w_k$라 할 때, $k+1$번째 wonowon 수는 $100w_k+1$로 계산할 수 있음을 관찰하자.

 

이를 이용해 (2, 3 및 5를 제외한) $N$ 이하의 소수 $p$에 대하여 $W(p)$를 각각 직접 계산해 조건을 만족하는 소수의 개수를 세는 것으로 문제를 해결할 수 있다. 이 과정에서 wonowon 수를 1010101...의 형태로 모든 자릿수를 보관하는 대신 각 소수 $p$로 나눈 나머지의 형태로 보관해 오버플로우를 피하자.

 

각 수가 소수인지는 에라토스테네스의 체를 이용해 미리 전처리해두는 것으로 판별할 수 있다. 이 문제에서는 입력의 크기가 충분히 작으므로 $p$가 소수인지 판단하기 위해 $\sqrt{p}$까지의 각 양의 정수로 직접 나눠봐도 무방하다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int ans;
int cur = 1, cnt = 1;

bool sieve[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 2; i < 100; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 10001; j += i) sieve[j] = 1;
	}

	int N; cin >> N;
	for (int p = 7; p <= N; p++) {
		if (sieve[p]) continue;
		cur = 1, cnt = 1;
		while (cur) cur = (cur * 100 + 1) % p, cnt += 2;
		if (cnt == p - 2) ans++;
	}

	cout << ans;
}