머지소트트리
int arr[100002]; vector tree[4 * 100002]; int N, M, K; void update(int bucket, int start, int end, int node, int x) { if (node < start || end < node) return; tree[bucket].push_back(x); if (start != end) { update(bucket * 2, start, (start + end) / 2, node, x); update(bucket * 2 + 1, (start + end) / 2 + 1, end, node, x); } } int query(int node, int start, int end, int left, int right, int x) { if ..
모듈러 역원와 페르마의 소정리
https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 모듈러 역원에 대해서 잘 설명해 놓은 문제이다. 핵심은 7/3 과 같은 분수를 답으로 하는 문제들을 판별하기 위해 a × b ^(-1) mod X 형태로 만드는것이다. 여기서 b^-1 이 모듈러 곱셈의 역원이다. ll dq(ll a, ll b) { if (b == 1) return a; if (b % 2 == 1) return a * dq(a, b - 1) % MOD; ll c = dq(a, b / 2); return c * c % MOD; } fo..
