문제/백준
c++ 백준_13172_"Σ"
나 진짜 못차마
2023. 6. 9. 22:19
728x90
13172번: Σ
모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다.
www.acmicpc.net
*
정확한 풀이는 아닙니다.
우연히 맞춰서 얼떨떨하네
문제 양, 내용 미쳤다
풀기 껄끄러웠는데
CLASS 4 다 해보고싶어서
억지로 잡고 읽어봤다.
진짜 문제만 40분 가까이 읽은 거 같다.
그래도 많은 문제에서 나온
1000000007
의 기원에 대해 조금은 알은 듯하다.
아주 조금
그래도 이해가 안돼서
대충 하나하나 엮어가봤다.
1.
일단 S/N 모양의 더하기 집합 형태라는 것
2.
a/b 이면,
a x b^-1modX 형태로 가능하다는 것
3.
b^(X-2) = b^-1(modX)
(여기서 모듈러 합동이라는 기호지만 편하게 =으로 표시)
그래서 입력으로
N, S 가 입력으로 주어지니까
3 7 이 주어졌다 가정하면
S/N = 7/3
7/3 = 7 * 3^-1(modX)
여기서 3^-1(modX) = 3^(X-2) 형태로 바뀐다.
그럼 최종적으로
7 * 3^(X-2)를 계산하면된다.
여기서 X 는 1,000,000,007 을 넣으면 된다.
그럼
3^(1000000005)를 구해야하는데
복잡하니 분할정복을 이용한 거듭제곱으로 시간복잡도를 낮춰 진행했다.
**
검색해보니 합동 연산자랑 =기호랑 의미가 다른데
그냥 =로 생각해 일단 계산했는데 왜 돌아간지 신기하다.
#include <iostream>
using namespace std;
typedef unsigned long long type;
#define MOD 1000000007
type myPow(type x, type n) {
type result = 1;
while (n) {
if (n & 1)
result = (result * x)%MOD;
x = (x * x)%MOD;
n >>= 1;
}
return result;
}
int main(void) {
int M;
cin >> M;
type ans = 0;
int N, S;
for (int i = 0; i < M; i++) {
cin >> N >> S;
ans += (S * myPow(N, MOD - 2))%MOD;
}
cout << ans % MOD;
}
728x90