BOJ 13172

Σ 성공

 

1 초

512 MB

2945

1404

1129

46.346%

문제

실제로 존재하는지 아닌지는 차치하고, 당신에게 삼면체 주사위가 있어서 이 주사위를 굴린다고 생각해보자. 주사위를 굴렸을 때 각 면이 나올 확률은 모두 동일하게 1/3 이다. 한 면에는 1, 다른 한 면에는 2, 남은 한 면에는 4가 적혀있다고 하면 주사위를 굴렸을 때 나오게 되는 숫자의 기댓값은 과연 몇일까? 간단하게도 셋의 평균인 7/3이 될 것이다.

이 문제를 조금 확장해서, "N면체 주사위의 각 면에 적힌 수가 주어졌을 때, 주사위를 굴렸을 때 각 면이 나올 확률이 모두 같다면 주사위를 굴렸을 때 나오게 되는 수의 기댓값은 과연 몇일까?"라는 문제가 주어졌다고 하자. 위의 예시에 대한 답을 소수로 출력한다면 2.33333333...일텐데, 무한한 자릿수를 모두 출력할 수는 없으니 적당히 끊어서 출력할 것이고, 이 끊긴 소수를 채점 프로그램이 다시 입력받아서 정답과 비교한다고 하면 결과가 얼마나 부정확할 것인가? 그렇기에 답을 정확히 판별하기 위해 출력하고자 하는 분수를 기약분수로 만들어 분모와 분자를 직접 출력하도록 했던 시기가 있었다.

이제 문제를 조금 더 확장하여, M개의 주사위가 있어서 이 중 i번째 주사위가 Ni면체 주사위이고 모든 면에 적힌 수를 더한 값이 Si일 때, 각 주사위에 대해서 주사위를 던졌을 때 주사위의 각 면이 나올 확률이 동일하다고 가정한 상태에서 모든 주사위를 각각 한 번씩 던졌을 때 나온 수들의 합의 기댓값을 구하는 문제를 만들었다. 확률변수 X의 기댓값을 E(X)로 나타내면, 기댓값의 선형성에 의해서 두 확률변수 X, Y에 대해 E(X + Y) = E(X) + E(Y)가 성립하므로, 이 문제의 답을 아래와 같이 간단하게 나타낼 수 있다.

S1/N1 + S2/N2 + ... + SM/NM

즉, 각 주사위에서 나오게 되는 수의 기댓값을 모두 더하면 답이 되는 것이다. 이 답을 정확하게 출력하기 위해, 모든 분수(여기서는 각 주사위의 기댓값)를 통분한다고 생각해보자. 이 분수의 분모와 분자의 값이 어떤 범위까지 치솟게 될 것인가? 즉, 분모와 분자를 모두 저장하고 있게 되면, 두 분수의 합을 구할 때 분모와 분자를 적정한 범위 내에서 계산해낼 수 없다는 문제에 부딪히게 된다. "그렇다면 분모와 분자를 어떤 모듈러 상에서 가지고 있으면 되지 않을까?"라고 생각할 수 있지만, 그러면 분모와 분자를 약분할 수가 없게 된다. 그렇기에, 분수를 다음과 같이 모듈러 상에서 하나의 정수로 가지고 있는 방법을 채택하게 되었다.

어떤 분수가 기약분수로 나타냈을 때 a/b이면, 이 분수는 a × b-1 mod X (X는 소수)으로 대신 계산하도록 한다. 여기서 b-1은 b의 모듈러 곱셈에 대한 역원이다.

b의 모듈러 곱셈에 대한 역원 b-1은 대체 어떤 수인 것일까? 이 수는 다음과 같은 성질을 만족하는 정수이다.

b-1 × b ≡ 1(mod X)

소수 모듈러에서만 성립하는 페르마의 소정리에 의해 bX - 1 ≡ 1 (mod X)가 성립하기에, bX - 2 ≡ b-1 (mod X) 역시 성립함을 알 수 있다.

이해를 돕기 위해 X를 11로 두고 Q = 7/3 을 계산해보자. 3-1 ≡ 4 (mod 11)이므로, Q ≡ 7 × 4 ≡ 6 (mod 11)이다. 이 Q에 3을 곱한 다음 11로 나눈 나머지를 구해 보면 7이 나오므로, 6이라는 정수가 7/3을 적절히 저장하고 있다는 것을 알 수 있다.

분수(유리수)를 이와 같은 방식으로 나타낸다면, 두 분수의 덧셈, 뺄셈, 곱셈은 mod X에서 두 정수를 가지고 계산하듯이 처리하고, 나눗셈은 나누는 분수의 곱셈에 대한 역원을 구한 후 그 역원을 mod X에서 곱하는 것으로 처리한다면, 분수를 정확히 출력하기 위해 통분을 하거나 기약분수로 만드는 골치아픈 일을 할 필요가 없어진다!

그러나 이 방법에도 문제가 있는 것은 마찬가지이다. 앞의 예에서 7/3을 6으로 저장했지만, 그냥 6/1도 6으로 저장할 것이다. 즉 서로 다른 두 분수도 모듈러 상에서 같은 정수로 저장하여, 정확한 판별을 한다는 우리의 목적에 부합하지 않는 것이다. 또다른 문제로는, 분모가 소인수로 X를 가질 때에는 역원을 계산할 수 없어서 모듈러로 나타낼 수가 없다는 점이 있다. 이러한 문제를 해결하기 위해 모듈러를 1,000,000,007와 같은 큰 소수로 하는데, 이를 통해 서로 다른 두 분수가 같은 정수로 나타나게 되는 확률을 낮추고, 분모가 가질 수 있는 소인수의 범위를 늘리는 효과를 볼 수 있다. 그는 이런 방식이 그래도 가장 정확한 방식이라고 생각하게 되었다.

이제 이 방식으로 M 개의 주사위가 있고, i번째 주사위가 Ni면체 주사위이며, 모든 면에 적힌 숫자를 더한 값이 Si일 때, 각 주사위에 대해서 주사위를 던졌을 때 주사위의 각 면이 나올 확률이 동일하다면, 모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 구하는 문제를 해결해보자.

 

입력

첫 번째 줄에는 주사위의 수를 나타내는 정수 M(1 ≤ M ≤ 104)이 주어진다.

다음 M개의 줄은 각 주사위의 정보를 나타내며, 이 중 i(1 ≤ i ≤ M)번째 줄에는 Ni, Si(1 ≤ Ni, Si ≤ 109)가 공백으로 구분되어 주어진다.

출력

모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 a/b가 된다면, (a × b-1) mod 1,000,000,007을 대신 출력하도록 한다. b-1은 b의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.

예제 입력 1 복사

1
3 7

예제 출력 1 복사

333333338

힌트

모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다.

본문 읽고 이해하는데만 세시간은 걸린거같다.

일단 역원 Notation이 굉장히 마음에 안든다. 역원을 B^-1 로 표기해놨는데 정수론 사전지식이 없다보니까 페르마 소정리 공식과 이게 너무 헷갈렸다. 

 

bX - 1 ≡ 1 (mod X)가 성립하기에, bX - 2 ≡ b-1(mod X)

 

특히 이 표기가 잘 이해가 안된다.

전자의 b^X-2는 거듭제곱을 의미하는 것으로 보이는데, 후자의 b^-1은 모듈러 역원에 해당하는 것으로 보인다.

 

모듈러 연산에서의 합동식의 기호는 모듈러 연산의 결과가 같은 수 아니었나, 빡대가리라 잘 모르겠다. 페르마 소정리 자체는 이해되는데 역원의 표기가 잘 이해되지 않는 것 같다. 모듈러연산의 결과면 정수가 나오는게 맞는데 왜 -1승으로 표기한거지, 그리고 이걸로 갑자기 거듭제곱 연산에 적용을 시키는지.

공부를 더해야겠다. 그냥 약속일 수도 있는데 뭔가 불편하다.

 

https://rebro.kr/105

PS를 위한 정수론 - (3) 페르마의 소정리와 활용 (이항 계수, 밀러-라빈)

정수론 공부좀 해야겠다.

#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
int M, ans;
long long func(int a, int power){
    if(power == 1){
        return a%1000000007;
    }
    if(power % 2 == 1){
        return a * func(a,power-1) % 1000000007; 
    
    }else{
        long long b = func(a, power/2)%1000000007;
        return b * b %1000000007;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>M;
    while(M--){
        int N, S;
        cin>>N>>S;
        int gc = gcd(N,S);
        N /= gc;
        S /= gc;
        ans += S * func(N, 1000000005) % 1000000007;
        ans %= 1000000007;
    }
    cout<<ans;
}