항해99 알고리즘 7일차

package hanghee99;

import java.math.BigInteger;
import java.util.Scanner;

public class BOJ15829_07 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt();
        String s = sc.next();
        long total = 0;
        double pow = 1;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            double count = (c-96)*pow;
            pow = (pow * 31) % 1234567891;
            total += count;
        }
        System.out.println(total% 1234567891);
    }
}

 

문제가 길지만 하고 싶은 말은 

r31로 하고 M의 값은 1234567891

(알파벳의 수 * r의 자리 수 제곱) % M이다

입니다.

 

각 알파벳의 숫자는 96을 빼주면 되고 제곱은 1234567891로 나눈 나머지를 확인하면 됩니다.

 

문제와 다르게 pow 에 M을 먼저 뺀 이유는 자리수가 너무 커지기 때문이다. 그래서 정답엔 M을 빼서 모든 문제에 예외없이 처리한다.