SWEA[7965] - 퀴즈[D4]

링크

SWEA[7965]

문제설명

• 분할정복

문제풀이

• 분할정복 + 범위초과 검사

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;

public class Solution7965 {

    public static long dcPower(long x, long n) {
        if(n==0)return 1;
        if(n==1)return x%1000000007;
        long result = dcPower(x,n>>1)%1000000007;
        if(n%2==0) {
            return (result*result)%1000000007;
        }else {
            return ((result*result)%1000000007)*x%1000000007;
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/swea/7965.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T=Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(br.readLine());
            long ans = 0;
            for (int i = 1; i <= N; i++) {
                ans+=(dcPower(i%1000000007, i)%1000000007);
                ans%=1000000007;
            }
            System.out.println("#"+test_case+" "+ans);
            /*
             * 초기화
             */
        }//end test_case
    }//end main
}//end class

아쉬운점

• long 범위 초과하는 모든 경우에 %연산 해줘야함
  • result*result 에도 mod 해줘야함

잘한점

• pow함수를 분할정복으로 함.
  • 시간초과 방지