글 읽기 - 다이나믹 프로그래밍 팩토리얼 모듈러연산 질문

vegahouse102 3년 전 0

다이나믹 프로그래밍을 배우다가 궁금한것이 생겨 질문드립니다.

아래에 있는 코드는 n을 입력받아 (n!)mod(c)를 구하는 것입니다.

보시면 전에있는 값에 i를 곱하고 mod를 취하는것을 볼 수 있는데

이 방법이 왜 (n!)mod(c)와 같은지 궁금해서 질문드립니다.

#include<iostream>
using namespace std;
int main(){
    int n,c;
    scanf("%d %d",&n,&c);
    int *p = new int[n+1];
    p[0];
    for(int i = 1; i <= n; i++){
        p[i] = (p[i-1]*i)%c;
    }
    printf("%d",p[i]);
}

wider93 3년 전 1

a * b % r = (a % r) * (b % r) % r가 성립하기 때문입니다. a = a0 * r + a1 등으로 두고 직접 확인해보시는 것도 좋겠습니다.

vegahouse102 3년 전 0

모듈러 공식은 알지만

(n!)mod(c)과 (....(((1*1)%c*2)%c)*3)%c)....)*n)%c가 왜 같은지 이해하지 못하겠습니다.

공식대로면 (((...((1*1)%c*2%c)%c*3%c)%c*4%c)....*n%c)%c가 되어야 맞는게 아닌가요?

혹시 증명해주실 수 있나요?

wider93 3년 전 1

n! % c = (n-1)! * n % c = ((n-1)! % c) * (n % c) % c = ((n-1)! % c) * n % c

모듈러 c를 취하는 공간 아래에서 나머지가 같은 두 수는 같은 수라는 느낌을 갖고 계시는 게 좋겠습니다.

wider93 3년 전 1

혹시 질문이 왜 i % c가 아닌 i인지 물으신 것이라면, i % c로 하셔도 됩니다.

다만 저런 계산을 해야 한다면 n < c일 테니( 안 그러면 당연히 답은 0이겠죠?) i % c가 항상 i가 되어서 필요가 없을 뿐입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

다이나믹 프로그래밍 팩토리얼 모듈러연산 질문

vegahouse102 3년 전 0

wider93 3년 전 1

vegahouse102 3년 전 0

wider93 3년 전 1

wider93 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말