반응형 페르마의소정리1 [CodeForce/C++] F. Multiplicative Arrays (Div.3) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 페르마의 소정리와 DP를 이용해서 풀 수 있는 문제다. 잘 생각해보면 이 문제는 k를 소인수 분해하는 것으로 시작할 수 있다는 것을 알 수 있다.왜냐하면 최대 길이 n의 배열의 곱이 k가 나오기 위해서는 배열 a의 안에 k의 약수들이 있다는 뜻이 되기 때문이다. 이를 이용하면 배열의 길이가 n일 때, 1을 제외한 k의 약수의 개수를 m이라고 하면 n-m개의 1과 m개의 k의 약수로 이루어진 배열의 조합을 구하는 문제로 볼 수 있다. 이를 이용해 DP로 문제를 해결할 수 있다. 아래와 같이 DP를 정의 하자. DP[k][i] = 1이 아닌 i개의 수를 곱해서 k를 만드는 경우의 수 그러면 .. 2025. 1. 23. 이전 1 다음 반응형