글 읽기 - 답답해 미치겠습니다 두 코드의 차이점좀 알려주세요

p_ce1052 3년 전 0

큰 수의 이항 계수를 페르마 소정리로 계산하는 코드입니다. 아무리 봐도 둘의 차이점을 모르겠는데 위의 코드는 제대로 계산이 되고 밑의 코드는 이상한 숫자를 출력합니다. 뭐가 다른가요? 부탁드립니다

#include<iostream> //제대로 돌아가는 코드 
#include<vector>
using namespace std;
long long factorial[4000001];
const long long p = 1000000007;

long long f(long long b,long long num){
	if(num==1) return b;
	if(num%2){//홀수인경우  
		long long temp = f(b,num/2); 
		return (((temp*temp)%p)*b)%p;
	}
	else{//짝수인경우  
		long long temp = f(b,num/2);
		return (temp*temp)%p;
	}
}
int main(){
	factorial[0] = 1;
	for(long long i=1; i<=4000000; i++){
		factorial[i] = factorial[i-1]*i;
		factorial[i]%=p;
	}
	int query;
	cin>>query;
	while(query--){
		int n,k;
		cin>>n>>k;
	long long a = factorial[n];
	long long b = (factorial[k]*factorial[n-k])%p;
	long long B = f(b,p-2);
	cout<<(a*B)%p<<'\n';
	}
}
//////////////////////////////////////////////////////////////
#include<iostream> //안돌아가는 코드
using namespace std;
const int maxn = 4000000;
const long long p = 1000000007;
long long fac[maxn+1];
long long multi(long long n,long long a){
	if(a==0) return 1;
	if(a==1) return n;
	if(a%2){
		long long ret = multi(n,a/2);
		return (n*ret*ret)%p;
	}
	else{
		long long ret = multi(n,a/2);
		return (ret*ret)%p;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
	fac[0] = 1;
	for(int i=1; i<=maxn; i++) fac[i] = (fac[i-1]*i)%p;
	int query;
	cin>>query;
	while(query--){
		int n,k;
		cin>>n>>k;
		long long a = fac[n];
		long long b = (fac[k]*fac[n-k])%p;
		long long B = multi(b,p-2);
		cout<<(a*B)%p<<'\n';
	}
}

djm03178 3년 전 1

11번째 줄과 46번째 줄이 다릅니다.

slah007 3년 전 1

n*ret*ret%p 는 오버플로우가 나지만 temp*temp%p*b%p는 오버플로우가 나지 않습니다.

p_ce1052 3년 전 0

아 셋다 10억가까이 될 수도 있겠군요 감사합니다

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

문제

문제

출처

ICPC

답답해 미치겠습니다 두 코드의 차이점좀 알려주세요

p_ce1052 3년 전 0

djm03178 3년 전 1

slah007 3년 전 1

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말