백준 9556번: 수학 숙제

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

9556번: 수학 숙제

---

처음엔 포함 배제로 풀려고 했다가, 제가 포함 배제에 익숙하지 못해서 구현을 포기하고 다른 방법으로 풀게 됐습니다.

 

이 문제의 첫 번째 포인트는 $N$자리 수는 한 개 이상의 0으로 시작할 수 있다는 것입니다. 즉 우리가 체크해야 할 수의 범위는 0부터 $10^{N}-1$까지입니다.

 

두 번째 포인트는 이 문제의 나눠 떨어진다는 표현은 나머지가 0이라는 것입니다. 그래서 0은 모든 양의 정수로 나누어 떨어지는 수라고 합니다.

---

이 문제는 물론 포함 배제로도 풀 수 있겠지만, 더 쉬운 관찰은 다음과 같습니다.

 

문자열 $S$를 정수 $x$가 만족한다면, $x+60$ 또한 같은 조건을 만족한다.

 

이는 $\textrm{LCM} \; (1,2,3,4,5,6) = 60$임을 이용하면 쉽게 알 수 있습니다.

 

결론적으로, $0$부터 $59$까지의 정수에 대해 문자열을 만족하는 정수가 몇 개인지 구하고, 이게 몇 주기 동안 반복되는지를 구하면 문제가 끝나게 됩니다.

---

이제 주기의 수를 구하는 함수를 구현하는 방법에 대해 설명하겠습니다. 이 링크에 따르면, 정수 나눗셈의 몫이 다음과 같습니다.

$$ \lfloor \frac{x}{k} \rfloor = \frac{x - \; x \; \textrm{mod} \; k}{k}$$

이 식을 이용하면, $10^{10^{18}}$ 을 60으로 나눈 몫을 $10^{9}+7$로 나눈 나머지 같은 값을 쉽게 구할 수 있습니다. (혹은 더 쉬운 방법이 있으면 알려주시면 감사하겠습니다)

 

시간 복잡도는 역수를 구하는 데 $O (\log P)$ 이므로 전체 복잡도 역시 $O (\log P)$ 입니다. 다음은 제 코드입니다.

#include <stdio.h>
#define mod 1000000007
 
long long N;
char string[7];
long long check (int x); // 0 <= x < 60
 
long long power_modular (long long x, long long y, long long M);
long long floor_modular (long long x, long long y);
 
int main() {
 
	int T;
	scanf("%d", &T);
	while(T--) {
		scanf("%lld %s", &N, string);
 
		long long temp = 0;
		for (int x = 0; x < 60; x++) {
			temp += check(x);
		}
 
		long long ttemp = 0;
		long long residue = (power_modular(10, N, 60) + 59) % 60;
		for (long long x = 0; x <= residue; x++) {
			ttemp += check(x);
		}
 
		long long answer = (floor_modular(N, 60) * temp + ttemp) % mod;
		printf("%lld\n", answer);
	}
	return 0;
}
 
long long check (int x) {
	for (int i = 0; i < 6; i++) {
		if (string[i] == '2') {
			continue;
		}
		else if (string[i] == '1') {
			if (x % (i + 1) != 0) {
				return 0;
			}
		}
		else {
			if (x % (i + 1) == 0) {
				return 0;
			}
		}
	}
	return 1;
}
 
long long power_modular (long long x, long long y, long long M) {
	long long result = 1;
	while(y) {
		if (y % 2) {
			result = result * x % M;
		}
		x = x * x % M;
		y /= 2;
	}
	return result;
}
 
long long floor_modular (long long x, long long y) {
	// floor [ ( 10^x - 1 ) / y ]
	long long inv_y = power_modular (y, mod - 2, mod);
	long long temp1 = (power_modular(10, x, mod) + mod - 1) % mod;
	long long temp2 = (power_modular(10, x, y) + y - 1) % y;
	return (temp1 - temp2 + mod) * inv_y % mod;
}

(C11, 0ms, 1116KB, 제출번호 54828255)

---