취미로 코딩하기

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

이번에 볼 문제는 백준 25025번 문제인 다항식 계산이다.
문제는 아래 링크를 확인하자.

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

주어진 다항식을 단순히 각 x값에 대해서 x^0, x^2, x^2, x^3 등을 순서대로 구해나가면서 계산하기에는 해야 하는 연산의 양이 많다. 이 문제는 어떻게 해결해야 할까?

이 문제를 푸는 핵심은 소수 P가 1000 이하라는 점을 잘 활용하는 것이다.

특히 페르마의 소정리(Fermat's little theorem; FLT)는 a가 P의 배수가 아니라면 a^(P-1) = 1 mod P라는 사실을 말해준다. 이 내용을 이용하면 다항식의 차수를 P 미만으로 줄일 수 있다.

이제 각 P 미만의 음이 아닌 정수에 대하여 다항식의 값을 단순히 직접 계산할 수 있게 되었다. 다항식의 값을 구해 문제를 해결하자.

a가 P의 배수, 즉 a=0인 경우의 예외처리를 잊지 말자.

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

#include <iostream>
using namespace std;
typedef long long ll;

int N, P;
ll num[1000];

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

	cin >> N >> P; P--;
	for (int i = N; i > 0; i--) {
		ll x; cin >> x;
		num[i % P] += x;
	}

	P++;
	ll x; cin >> x;
	x %= P;
	cout << x << '\n';
	num[0] += x;

	for (ll i = 1; i < P; i++) {
		ll ans = 0;
		ll tmp = 1;
		for (int j = 0; j < P; j++) {
			ans += num[j] * tmp;
			tmp = (tmp * i) % P;
		}
		cout << ans % P << '\n';
	}
}