[JAVA]SWEA .6026 성수의 비밀번호 공격

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWajgCUaaAkDFAWM&categoryId=AWajgCUaaAkDFAWM&categoryType=CODE&problemTitle=6026&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&&

SW Expert Academy

 

 

 

이 문제에서 사용할 세 가지 공식

 

 

1. 포함배제의 원리

 

2. 페르마의 소정리

 

3. 빠른 거듭제곱

 

 

 

| 포함배제의 원리

 

 

 

∑(-1)^i * kCi * (k-i)^n

 

 

 

 

| 페르마의 소정리

 

페르마의 소정리 이론 

 

출처 : 나무위키

 

우선 조합 공식 중

위와 같이 분수로 된 공식이 있다. 

문제에 위의 식을 사용하기 위해 분수를 곱셈식으로 처리해주어야 한다. 

 

 

따라서 

nCr

= n! / ((n-r)! * r!)

 

👆 위의 식이 페르마의 소정리를 통해

 

= n! * ((n-r)! * r!)^(p-2) (mod p)

로 처리가 가능해진다. 

 

 

 

| 빠른 거듭제곱

 

 

우리가 컴퓨터에서 거듭제곱을 처리할 때

 

지수가 굉장히 큰 경우  

 

위와 같은 방법을 사용한다. 

 

 

 

단, 지수가 짝수인 경우와 홀수인 경우를 나누어 처리한다.

 

 

 

<지수가 짝수인 경우>

 

<지수가 홀수인 경우>

 

 

결과적으로 

 

빠른 거듭제곱 방식으로 문제를 풀면 

 

지수만큼 for문을 돌리는 것보다 훨씬 적은 횟수로 값을 도출할 수 있다.

 

 

 

예를들어 지수가 1,000,000,000인 경우를 생각해보자.

 

for문을 돌리면

10억번의 곱셈 연산을 하게 된다.

 

그래서 빠른 거듭제곱 방식을 이용하면,

	
	pow(a, 1000000000, c)        -> pow(a, 500000000, c)      
	-> pow(a, 250000000, c)      -> pow(a, 125000000, c)      
	-> pow(a, 62500000, c)       -> pow(a, 31250000, c)       
	-> pow(a, 15625000, c)       -> pow(a, 7812500, c)        
	-> pow(a, 3906250, c)        -> pow(a, 1953125, c)        
	-> pow(a, 976562, c)         -> pow(a, 488281, c)         
	-> pow(a, 244140, c)         -> pow(a, 122070, c)         
	-> pow(a, 61035, c)          -> pow(a, 30517, c)          
	-> pow(a, 15258, c)          -> pow(a, 7629, c)           
	-> pow(a, 3814, c)           -> pow(a, 1907, c)           
	-> pow(a, 953, c)            -> pow(a, 476, c)            
	-> pow(a, 238, c)            -> pow(a, 119, c)            
	-> pow(a, 59, c)             -> pow(a, 29, c)             
	-> pow(a, 14, c)             -> pow(a, 7, c)              
	-> pow(a, 3, c)              -> pow(a, 1, c)              
	-> pow(a, 0, c)

 

 

10억번의 연산을 31번으로 처리할 수 있다.

 

이는 큰 수를 절반으로 나누는 과정을 통해 

연산 횟수를 절반씩 줄어나가 빠르게 처리할 수 있다.

 

 

시간복잡도

 

 Θ(b)       >       Θ(log2b)  

반복문            빠른 거듭제곱 

 

 

 

 

위 세 가지 이론을 모두 적용하여 문제를 푼 코드

[JAVA] 해설 코드

package CT;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class SWEA_6026 {

	static int M, N;
	static long[] fac;
	static long MOD = 1000000007;
	static private void factorial() {
		
		fac = new long[101];
		fac[0]=fac[1]=1;
		
		for(int i=2;i<101;i++) {
			fac[i] =  (fac[i-1]* i)%MOD;
		}
		
		return;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		factorial();
		
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			long total = solve();			
			sb.append("#"+tc+" ").append(total).append("\n");
		}
		System.out.println(sb.toString());
	}
    
	// 1. 전사함수의 개수 구하기(포함배제의 원리) : ∑(-1)^i * kCi * (k-i)^n;
	static long solve() {
		long total=0;
		for(int i=0;i<=M;i++) {
			long l1 = i%2==0 ? 1 : -1;
			long l2 = nCr(i);
			long l3 = pow((M-i),N);
			long result = ((l1*l2)%MOD*l3)%MOD;
			total = (total + result + MOD) % MOD;
		}
		
		return total;
	}
    
        // 2. 페르마의 소정리를 이용한 조합 공식
	// nCr = n!/((n-r)! * r!)%MOD  ->  (n!*((n-r)! * r!)^(MOD-2)) % MOD 
	static long nCr(int r) {
		if(r==0) {
			return 1;
		}
		
		long l1 = fac[M];
		long l2 = pow(fac[M-r], MOD-2);
		long l3 = pow(fac[r], MOD-2);
				
		return ((l1 * l2)%MOD*l3)%MOD;
		
	}
	
	// 3. 빠른 거듭제곱
	static long pow(long a, long b) {
		
		if(b==1) {
			return a % MOD;
		}
		long half = pow(a, b/2);
                // 짝수인 경우
		if(b%2==0) {
			return (half * half)%MOD;
		}
                // 홀수인 경우
                else {
			return ((half * half)%MOD * a)%MOD;
		}
		
	}

}

 

 

 

 

 

참고 블로그 : https://namnamseo.tistory.com/entry/%EB%B9%A0%EB%A5%B8-%EA%B1%B0%EB%93%AD%EC%A0%9C%EA%B3%B1

 

참고 영상 : https://www.youtube.com/watch?v=wWZMYVSep0U