## 题目描述

This is an interactive problem.
For two positive integers $x, y$, we define $\pi(x, y)$ to be the number of distinct primes that divide both $x$ and $y$. For example $\pi(2, 3) = 0, \; \pi(8, 16) = 1$ and $\pi(30, 105) = 2$.
For two positive integers $a, b$, where $a \le b$, we define $S(a, b)$ to be the sum of values $\pi(x, y)$ over all pairs of integers $(x, y)$ satisfying $a \le x \lt y \le b$.
Your task is to compute the values $S(a, b)$ for many query pairs $(a, b)$. To make your task more challenging, all the queries have to be answered online.

## 代码

#include <cstdio>
#include <cstring>
#include <algorithm>

int const N = 1000005;

int tp, prime[N], rec[N], vis[N], sum[N];

void init() {
for (int i = 2; i < N; ++i) {
if (!vis[i]) {
prime[tp++] = i;
}
for (int j = 0; j < tp && i * prime[j] < N; ++j) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
break;
}
}
}
for (int i = 2; i < N; ++i)
sum[i] = sum[i - 1] + !vis[i];
}

int main() {
init();
int q;
scanf("%d", &q);
for (; q--;) {
int a, b;
scanf("%d%d", &a, &b);
long long ans = 0;
for (int i = 0; i < tp && prime[i] < b;) {
int cnt = b / prime[i] - (a - 1) / prime[i];
int nxt = 1e9;
if (b / prime[i]) nxt = std::min(nxt, b / (b / prime[i]));
if ((a - 1) / prime[i]) nxt = std::min(nxt, (a - 1) / ((a - 1) / prime[i]));
ans += 1ll * cnt * (cnt - 1) / 2 * (sum[nxt] - i);
i = sum[nxt];
}
printf("%lld\n", ans);
fflush(stdout);
}
return 0;
}


## 题目描述

$n$ black and white balls were put into a bag. Petya doesn’t know exactly how many black balls are there among them. He knows, however, that there are $0, 1, \ldots, n$ black balls among all balls in the bag with equal probability.
Petya took $l$ balls from the bag at random, and $l_1$ of them turned out black, while $l_2$ other turned out white ($l_1+l_2=l$). Now he wants to predict how many black balls were there initially in the bag. Of course, if $l \lt n$, he can’t be sure in his prediction, but he wants to predict a segment $[a, b]$, such that the amount $k$ of black balls belongs to it with probability at least $p$.
You are given $n, l_1, l_2$ and $p$, and you must find such $a$ and $b$ that $b-a$ is minimal possible. If there are several such pairs $(a, b)$, choose the one with the smallest $a$.

## 算法分析

$$P(B_i|A)={P(B_i)P(A|B_i) \over \sum_{j=0}^n P(B_j)P(A|B_j)}$$

$$P(B_i)={1 \over n+1}, \; P(A|B_i)={{i \choose l_1}{n-i \choose l_2} \over {n \choose l}}$$

## 代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 55;
double a[N];

double get_c(int n, int m) {
if (n < m)
return 0;
double ret = 1;
for (int i = 0; i < m; ++i)
ret *= 1. * (n - i) / (m - i);
return ret;
}

int main() {
int n, l1, l2, p;
scanf("%d%d%d%d", &n, &l1, &l2, &p);
double b = 0;
for (int i = 0; i <= n; ++i)
b += a[i] = 1. / (n + 1) * get_c(i, l1) * get_c(n - i, l2) / get_c(n, l1 + l2);
for (int i = 1; i <= n + 1; ++i)
for (int j = 0; j + i - 1 <= n; ++j) {
double sum = 0;
for (int k = j; k <= j + i - 1; ++k)
sum += a[k];
if (sum / b * 100 + 1e-12 >= p)
return printf("%d %d\n", j, j + i - 1), 0;
}
return 0;
}


## 题目描述

Given a positive integer $n$ and a positive prime number $p$, find $x, y$ and $z$ such that $x^n+y^n \equiv z^n \pmod p$ and $x, y$ and $z$ are nonzero modulo $p$ or report that there’s no such triple.

## 算法分析

$$g^{k_1n}+g^{k_2n} \equiv g^{k_3n}$$

$$G^{k_1}+G^{k_2} \equiv G^{k_3}$$

\begin{align} G^{k_1-k_2}+1 &\equiv G^{k_3-k_2} \\ G^{k_1-k_3}+G^{k_2-k_3} &\equiv 1 \end{align}

$$G^i+1 \equiv G^j \lor G^j+1 \equiv G^i \lor G^i+G^j \equiv 1$$

## 代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 1000005;
int a[N], b[N], pri[N];

int power(int a, int b, int p) {
int ret = 1;
for (; b; b >>= 1)
b & 1 && (ret = 1ll * ret * a % p), a = 1ll * a * a % p;
return ret;
}

int get_prt(int p) {
int top = 0, k = p - 1;
for (int i = 2; i * i <= k; ++i)
if (!(k % i)) {
pri[top++] = i;
for (; !(k % i); k /= i)
;
}
if (k > 1)
pri[top++] = k;
for (int i = 2; i <= p - 1; ++i) {
bool fg = 1;
for (int j = 0; fg && j < top; ++j)
fg &= power(i, (p - 1) / pri[j], p) > 1;
if (fg)
return i;
}
return 0;
}

int main() {
int T;
scanf("%d", &T);
for (int n, p; T--;) {
scanf("%d%d", &n, &p);
int g = get_prt(p), gn = power(g, n, p), x = 0, y = 0, z = 0;
for (int i = 1, G = gn; i <= p - 1; ++i, G = 1ll * G * gn % p)
if (b[G] == T + 1)
break;
else {
a[G] = i, b[G] = T + 1;
if (b[G + 1] == T + 1) {
x = power(g, i, p), y = 1, z = power(g, a[G + 1], p);
break;
}
if (b[G - 1] == T + 1) {
x = power(g, a[G - 1], p), y = 1, z = power(g, i, p);
break;
}
if (b[1 - G + p] == T + 1) {
x = power(g, i, p), y = power(g, a[1 - G + p], p), z = 1;
break;
}
}
x ? printf("%d %d %d\n", x, y, z) : puts("-1");
}
return 0;
}


## 题目描述

Inspired by Stephen Graham, the King of Berland started to study algorithms on strings. He was working days and nights, having a feeling that the full potential in this area is still to be unlocked. And he was right!
One day, all the sudden, he made a huge breakthrough by discovering the fact that strings can be magically transformed into integer numbers. It was so simple! You just have to map different letters to different digits and be careful enough not to introduce any leading zeroes.
Here is what he wrote in his textbook about the string ‘lalala’:

• it can be transformed to an $282828$ by mapping ‘l’ to $2$, and ‘a’ to $8$,
• it can also be transformed to $909090$ by mapping ‘l’ to $9$, and ‘a’ to $0$,
• acouple of examples of invalid transformations are $050505$ (the resulting number has a leading zero), $333333$ (different letters are mapped to the same digit), $123456$ (no mapping to the original letters at all).

But then things started to become more interesting. Obviously, it was known from very beginning that a single string can potentially be mapped to a variety of different integer numbers. But the King couldn’t even imagine that all numbers produced by the same string pattern might have common properties!
For example, every single number that can be produced from string ‘lalala’ is always divisible by $259$, irrespective of the letter-to-digit mapping you choose. Fascinating!
So the King ended up with the following problem. For any given string, he wanted to come up with an algorithm to calculate the set of its divisors. A number is called a divisor of the given string if all positive integers, that could possibly be produced from the given string, are divisible by it.
As usual, the King desperately wants you to help him, so stop thinking and start acting!

## 算法分析

• 引理 $\forall a \le b, \; (a, b) \mid b-a$。

## 代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const L = 15;
static int const M = 10000005;
char s[L];
int top, cnt, cc, p[M];
long long v[26], dv[L], dc[L], ans[M];

long long get_gcd(long long a, long long b) {
for (long long c; b; c = a % b, a = b, b = c)
;
return a;
}

void init() {
top = 0;
for (int i = 2; i < M; ++i) {
if (!p[i])
p[top++] = i;
for (int j = 0; j < top; ++j) {
int k = i * p[j];
if (k >= M)
break;
p[k] = 1;
if (!(i % p[j]))
break;
}
}
}

void dfs(int t, long long v) {
if (t == cnt)
return void(ans[cc++] = v);
for (int i = 0; i <= dc[t]; ++i, v *= dv[t])
dfs(t + 1, v);
}

int main() {
int n;
scanf("%d", &n), init();
for (int _ = 1; _ <= n; ++_) {
printf("Case %d:", _), scanf("%s", s);
int len = strlen(s), st = 0;
for (int c = 0; c < 26; ++c) {
v[c] = 0;
for (int i = 0; i < len; ++i) {
v[c] *= 10;
if (s[i] == c + 'a')
++v[c];
}
st += v[c] > 0;
}
long long gcd = 0;
if (st < 10)
for (int i = 0; i < 26; ++i)
gcd = get_gcd(gcd, v[i]);
else {
int k = 0;
for (int i = 0; i < 26; ++i)
if (v[i])
gcd += k++ * v[i];
for (int i = 0; i < 26; ++i)
for (int j = 0; j < 26; ++j)
if (v[i] && v[j] && v[i] < v[j])
gcd = get_gcd(gcd, v[j] - v[i]);
}
cnt = cc = 0;
for (int i = 0; i < top && 1ll * p[i] * p[i] <= gcd; ++i)
if (!(gcd % p[i])) {
dv[cnt] = p[i], dc[cnt] = 0;
for (; !(gcd % p[i]);)
gcd /= p[i], ++dc[cnt];
++cnt;
}
if (gcd > 1)
dv[cnt] = gcd, dc[cnt] = 1, ++cnt;
dfs(0, 1), std::sort(ans, ans + cc);
for (int i = 0; i < cc; ++i)
printf(" %lld", ans[i]);
puts("");
}
return 0;
}


## 题目描述

Gena and Petya love playing the following game with each other. There are $n$ piles of stones, the $i$-th pile contains $a_i$ stones. The players move in turns, Gena moves first. A player moves by choosing any non-empty pile and taking an arbitrary positive number of stones from it. If the move is impossible (that is, all piles are empty), then the game finishes and the current player is considered a loser.
Gena and Petya are the world famous experts in unusual games. We will assume that they play optimally.
Recently Petya started to notice that Gena wins too often. Petya decided that the problem is the unjust rules as Gena always gets to move first! To even their chances, Petya decided to cheat and take and hide some stones before the game begins. Since Petya does not want Gena to suspect anything, he will take the same number of stones $x$ from each pile. This number $x$ can be an arbitrary non-negative integer, strictly less that the minimum of $a_i$ values.
Your task is to find the number of distinct numbers $x$ such that Petya will win the game.

## 算法分析

Nim游戏后手胜利的条件是所有数的异或和为$0$。

## 代码

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

static int const N = 200005;
static int const M = 65;
int a[N], cnt[M], f[M][N], s[2][N];

signed main() {
int n;
scanf("%lld", &n);
for (int i = 0; i < n; ++i) {
scanf("%lld", a + i);
for (int j = 0; j < M; ++j)
cnt[j] += a[i] >> j & 1;
}
f[0][0] = 1;
for (int i = 0; i < M - 1; ++i) {
int c0 = n - cnt[i], c1 = cnt[i], c = 0;
for (int j = 0; j <= n; ++j) {
if (j)
if (a[j - 1] >> i & 1)
++c0, --c1;
else
--c0, ++c1, ++c;
if (!(c0 & 1))
f[i + 1][c + c0] += f[i][j];
if (!(c1 & 1))
f[i + 1][c] += f[i][j];
}
*s[0] = *s[1] = 0;
for (int j = 0; j < n; ++j)
s[a[j] >> i & 1][++*s[a[j] >> i & 1]] = a[j];
for (int j = 1; j <= *s[0]; ++j)
a[j - 1] = s[0][j];
for (int j = 1; j <= *s[1]; ++j)
a[*s[0] + j - 1] = s[1][j];
}
int sum = 0;
for (int i = 1; i < n; ++i)
sum ^= a[i] - a[0];
printf("%lld\n", f[M - 1][0] - (sum == 0));
return 0;
}


## 题目描述

Kyoya Ootori wants to take the train to get to school. There are $n$ train stations and $m$ one-way train lines going between various stations. Kyoya is currently at train station $1$, and the school is at station $n$. To take a train, he must pay for a ticket, and the train also takes a certain amount of time. However, the trains are not perfect and take random amounts of time to arrive at their destination. If Kyoya arrives at school strictly after $t$ time units, he will have to pay a fine of $x$.
Each train line is described by a ticket price, and a probability distribution on the time the train takes. More formally, train line $i$ has ticket cost $c_i$, and a probability distribution $p_{i, k}$ which denotes the probability that this train will take $k$ time units for all $1 \le k \le t$. Amounts of time that each of the trains used by Kyouya takes are mutually independent random values (moreover, if Kyoya travels along the same train more than once, it is possible for the train to take different amounts of time and those amounts are also independent one from another).
Kyoya wants to get to school by spending the least amount of money in expectation (for the ticket price plus possible fine for being late). Of course, Kyoya has an optimal plan for how to get to school, and every time he arrives at a train station, he may recalculate his plan based on how much time he has remaining. What is the expected cost that Kyoya will pay to get to school if he moves optimally?

## 算法分析

$$f_{i, j}= \begin{cases} \min(c_e+\sum_{k=1}^t p_{e, k} \cdot f_{b_e, j+k} \mid e \in [1, m] \land a_e=i), & i \lt n \land j \le t \\ d_{i, n}+x , & i \lt n \land j \gt t \\ 0, & i=n \land j \le t \\ x, & i=n \land j \gt t \end{cases}$$

$$S_{e, j}=\sum_{k=1}^t p_{e, k} \cdot f_{b_e, j+k}$$

$$f_{i, j}=\min(c_e+S_{e, j} \mid e \in [1, m] \land a_e=i)$$

## 代码

/*
*/

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

static int const N = 55;
static int const M = 105;
static int const T = 100000;
static double const PI = acos(-1);
int rev[T];

class Point {
public:
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
std::pair<double, double> pair() {
return std::make_pair(x, y);
}
friend Point operator+(Point const &a, Point const &b) {
return Point(a.x + b.x, a.y + b.y);
}
friend Point operator-(Point const &a, Point const &b) {
return Point(a.x - b.x, a.y - b.y);
}
friend Point operator*(Point const &a, Point const &b) {
return Point(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
Point operator/(double const &n) {
return Point(x / n, y / n);
}
} wn[T], A[T], B[T];

int init(int n) {
int m = n, l = 0;
for (n = 1; n <= m; n <<= 1, ++l)
;
for (int i = 1; i < n; ++i)
rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
for (int i = 0; i < n >> 1; ++i)
wn[i] = Point(cos(2 * PI / n * i), sin(2 * PI / n * i));
return n;
}

void fft(Point *a, int n, int inv = 0) {
for (int i = 0; i < n; ++i)
if (i < rev[i])
std::swap(a[i], a[rev[i]]);
for (int i = 1; i < n; i <<= 1)
for (int j = 0; j < n; j += i << 1)
for (int k = 0; k < i; ++k) {
Point x = a[j + k], y = wn[n / (i << 1) * k] * a[j + k + i];
a[j + k] = x + y, a[j + k + i] = x - y;
}
if (inv) {
std::reverse(a + 1, a + n);
for (int i = 0; i < n; ++i)
a[i] = a[i] / n;
}
}

int n, m, t, x, mp[N][N];
double p[M][T], s[M][T], f[N][T];
struct Line {
int a, b, c;
} li[M];

void update(int l, int r) {
int mid = l + r >> 1, len = init(r - l + r - mid - 2);
for (int i = 1; i <= m; ++i) {
for (int j = 0; j < len; ++j)
A[j] = B[j] = 0;
for (int j = mid + 1; j <= r; ++j)
A[j - mid - 1] = f[li[i].b][r - j + mid + 1];
for (int j = 1; j <= r - l; ++j)
B[j - 1] = p[i][j];
fft(A, len), fft(B, len);
for (int j = 0; j < len; ++j)
A[j] = A[j] * B[j];
fft(A, len, 1);
for (int j = l; j <= mid; ++j)
s[i][j] += A[r - j - 1].x;
}
}

void solve(int l, int r) {
if (l == r) {
for (int i = 1; i <= m; ++i)
f[li[i].a][l] = std::min(f[li[i].a][l], s[i][l] + li[i].c);
return;
}
int mid = l + r >> 1;
solve(mid + 1, r), update(l, r), solve(l, mid);
}

int main() {
scanf("%d%d%d%d", &n, &m, &t, &x);
memset(mp, 0x3f, sizeof mp);
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &li[i].a, &li[i].b, &li[i].c);
mp[li[i].a][li[i].b] = std::min(mp[li[i].a][li[i].b], li[i].c);
for (int j = 1; j <= t; ++j)
scanf("%lf", &p[i][j]), p[i][j] /= 100000;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k)
mp[j][k] = std::min(mp[j][k], mp[j][i] + mp[i][k]);
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= t << 1; ++j)
if (i == n)
if (j <= t)
f[i][j] = 0;
else
f[i][j] = x;
else
if (j <= t)
f[i][j] = 1e9;
else
f[i][j] = x + mp[i][n];
update(0, t << 1), solve(0, t), printf("%.8lf\n", f[1][0]);
return 0;
}


## 题目描述

Math is important!! Many students failed in 2+2’s mathematical test, so let’s AC this problem to mourn for our lost youth..
Look at this sample picture:

An ellipse in a plane centered on point $O$. The $L, R$ lines will be vertical through the $X$-axis. The problem is calculating the blue intersection area. But calculating the intersection area is dull, so I have to turn to you, a talent of programmer. Your task is telling me the result of calculation. (defined $\pi=3.14159265$, the area of an ellipse $A=\pi ab$)

## 算法分析

$$\int_a^b f(x) \, {\rm d}x \approx {b-a \over 6} \left(f(a)+4f\left({a+b \over 2}\right)+f(b)\right)$$

$$g(l, r)=\int_l^r f(x) \, {\rm d}x, \; h(l, r)={r-l \over 6} \left(f(l)+4f\left({l+r \over 2}\right)+f(r)\right)$$

$$g(l, r)=h(l, r)$$

$$g(l, r)=g\left(l, {l+r \over 2}\right)+g\left({l+r \over 2}, r\right)$$

## 代码

/*
* Today is what happened to yesterday.
*/

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

static double const EPS = 1e-8;
int a, b;

double get_y(double x) { return 2 * b * sqrt((1 - x * x / a / a)); }

double get_s(double l, double r) {
return (get_y(l) + 4 * get_y((l + r) / 2) + get_y(r)) * (r - l) / 6;
}

double calc(double l, double r) {
double mid = (l + r) / 2;
if (fabs(get_s(l, r) - get_s(l, mid) - get_s(mid, r)) < EPS)
return get_s(l, r);
return calc(l, mid) + calc(mid, r);
}

int main() {
int T;
scanf("%d", &T);
for (; T--;) {
int l, r;
scanf("%d%d%d%d", &a, &b, &l, &r);
printf("%.3lf\n", calc(l, r));
}
return 0;
}


## 题目描述

Little Y finds there is a very interesting formula in mathematics:
$$X^Y \bmod Z=K$$
Given $X, Y, Z$, we all know how to figure out $K$ fast. However, given $X, Z, K$, could you figure out $Y$ fast?

## 算法分析

$$X^Y \equiv K \pmod Z$$

\begin{align} X^{aM-b} &\equiv K \pmod Z \\ X^{aM} &\equiv K \cdot X^b \pmod Z \end{align}

\begin{align} (Dx)^Y &\equiv Dk \pmod{Dz} \\ x \cdot (Dx)^{Y-1} &\equiv k \pmod z \end{align}

$$(Dx)^{Y-1} \equiv k \cdot x^{-1} \pmod z$$

$$(X’)^{Y’} \equiv K’ \pmod{Z’}$$

## 代码

/*
* You will be singled out for promotion in your work.
*/

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

class HashTable {
private:
static int const MOD = 3214567;
int numr, h[MOD], id[MOD], val[MOD], nxt[MOD];

public:
void clear() { memset(h, numr = 0, sizeof h); }

int count(int const &n) {
for (int i = h[n % MOD]; i; i = i[nxt])
if (i[id] == n)
return 1;
return 0;
}

int &operator[](int const &n) {
for (int i = h[n % MOD]; i; i = i[nxt])
if (i[id] == n)
return i[val];
++numr, numr[id] = n, numr[nxt] = h[n % MOD], h[n % MOD] = numr;
return numr[val];
}
} mp;

int ex_gcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int ret = ex_gcd(b, a % b, y, x);
y -= a / b * x;
return ret;
}

int get_gcd(int a, int b) {
int x, y;
return ex_gcd(a, b, x, y);
}

int get_inv(int a, int b) {
int x, y;
return ex_gcd(a, b, x, y), (x + b) % b;
}

int bsgs(int a, int b, int c) {
a %= c;
if (a == 0)
return b == 0 ? 1 : -1;
if (b == 0)
return -1;
if (b == 1)
return 0;
int k = 0;
for (int t; (t = get_gcd(a, c)) > 1; ++k) {
if (b % t)
return -1;
c /= t, b /= t, b = 1ll * b * get_inv(a / t, c) % c;
}
mp.clear();
int d = a, m = sqrt(c) + 1;
for (int i = 1; i <= m; ++i, d = 1ll * d * a % c)
mp[1ll * d * b % c] = i;
d = 1ll * d * get_inv(a, c) % c;
int e = d;
for (int i = 1; i <= m; ++i, e = 1ll * e * d % c)
if (mp.count(e))
return i * m - mp[e] + k;
return -1;
}

int main() {
for (int a, b, c; scanf("%d%d%d", &a, &c, &b), a || b || c;) {
int ans = bsgs(a, b, c);
if (~ans)
printf("%d\n", ans);
else
puts("No Solution");
}
return 0;
}


## 题目描述

Dr. Ceizenp’ok from planet i1c5l became famous across the whole Universe thanks to his recent discovery – the Ceizenpok’s formula. This formula has only three arguments: $n, k$ and $m$, and its value is a number of $k$-combinations of a set of $n$ modulo $m$.
While the whole Universe is trying to guess what the formula is useful for, we need to automate its calculation.

## 算法分析

$$x={n \choose k}, \; m=p_1^{a_1}p_2^{a_2} \cdots p_q^{a_q}$$

$$\left\{ \begin{array}{c} x \equiv r_1 \pmod{p_1^{a_1}} \\ x \equiv r_2 \pmod{p_2^{a_2}} \\ \cdots \\ x \equiv r_q \pmod{p_q^{a_q}} \end{array} \right.$$

$${n \choose k}={n! \over k!(n-k)!}$$

$$f(n)=n! \bmod p_i^{a_i}$$

$$f(n)=\left(f\left(\left\lfloor{n \over p_i}\right\rfloor\right)\cdot p_i^{\lfloor n/p_i \rfloor}\cdot\left(\prod_{i \in [1, p_i^{a_i}], \; p_i\not\mid i}i\right)^{\lfloor n/p_i^{a_i} \rfloor}\cdot\prod_{i \in [1, n \bmod p_i^{a_i}], \; p_i\not\mid i}i\right)\bmod p_i^{a_i}$$

## 代码

/*
* Your lucky number has been disconnected.
*/

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

int power(int a, int b, int m) {
int ret = 1;
for (; b; b >>= 1)
b & 1 && ((ret *= a) %= m), (a *= a) %= m;
return ret;
}

void ex_gcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return;
}
ex_gcd(b, a % b, y, x), y -= a / b * x;
}

int get_inv(int a, int b) {
int x, y;
ex_gcd(a, b, x, y);
return (x + b) % b;
}

int get_fac(int n, int p, int k) {
int m = power(p, k, 1e9), ret = 1;
for (; n; n /= p) {
if (n / m) {
int rec = 1;
for (int i = 2; i < m; ++i)
if (i % p)
(rec *= i) %= m;
(ret *= power(rec, n / m, m)) %= m;
}
for (int i = n % m; i > 1; --i)
if (i % p)
(ret *= i) %= m;
}
return ret;
}

int calc(int N, int K, int M, int p, int k) {
int a = get_fac(N, p, k), b = get_fac(K, p, k), c = get_fac(N - K, p, k),
cnt = 0;
for (int i = N; i; i /= p)
cnt += i / p;
for (int i = K; i; i /= p)
cnt -= i / p;
for (int i = N - K; i; i /= p)
cnt -= i / p;
int m = power(p, k, 1e9),
ret = a * get_inv(b, m) % m * get_inv(c, m) % m * power(p, cnt, m) % m;
return ret * (M / m) % M * get_inv(M / m, m) % M;
}

signed main() {
int N, K, M, ans = 0;
scanf("%lld%lld%lld", &N, &K, &M);
for (int i = 2, t = M; t > 1; ++i)
if (!(t % i)) {
int k = 0;
for (; !(t % i); ++k, t /= i)
;
(ans += calc(N, K, M, i, k)) %= M;
}
printf("%lld\n", ans);
return 0;
}


## 题目描述

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:

• Choose $k$ different positive integers $a_1, a_2, \ldots, a_k$. For some non-negative $m$, divide it by every $a_i$ to find the remainder $r_i$. If $a_1, a_2, \ldots, a_k$ are properly chosen, $m$ can be determined, then the pairs $(a_i, r_i)$ can be used to express $m$.

“It is easy to calculate the pairs from $m$,” said Elina. “But how can I find $m$ from the pairs?”
Since Elina is new to programming, this problem is too difficult for her. Can you help her?

## 题意概述

$$\left\{ \begin{array}{c} x \equiv r_1 \pmod{a_1} \\ x \equiv r_2 \pmod{a_2} \\ \cdots \\ x \equiv r_k \pmod{a_k} \end{array} \right.$$

## 算法分析

\begin{align} x &\equiv r_1 \pmod{a_1} \\ x &\equiv r_2 \pmod{a_2} \end{align}

$$x=r_1+k_1a_1=r_2+k_2a_2$$

$$k_1a_1=r_2-r_1+k_2a_2$$

\begin{align} k_1{a_1 \over (a_1, a_2)}&={r_2-r_1 \over (a_1, a_2)}+k_2{a_2 \over (a_1, a_2)} \\ k_1{a_1 \over (a_1, a_2)} &\equiv {r_2-r_1 \over (a_1, a_2)} \pmod{{a_2 \over (a_1, a_2)}} \\ k_1 &\equiv \left( {a_1 \over (a_1, a_2)} \right)^{-1} \cdot {r_2-r_1 \over (a_1, a_2)} \pmod{{a_2 \over (a_1, a_2)}} \end{align}

$$x \equiv r_1+k_1a_1 \pmod{{a_1a_2 \over (a_1, a_2)}}$$

## 代码

/*
* Your life would be very empty if you had nothing to regret.
*/

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

int ex_gcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int ret = ex_gcd(b, a % b, y, x);
y -= a / b * x;
return ret;
}

int get_gcd(int a, int b) {
int x, y;
return ex_gcd(a, b, x, y);
}

int get_inv(int a, int b) {
int x, y;
return ex_gcd(a, b, x, y), (x += b) %= b;
}

signed main() {
for (int k, a, r; ~scanf("%lld%lld%lld", &k, &a, &r);) {
int flag = 0;
for (int ai, ri; --k;) {
scanf("%lld%lld", &ai, &ri);
int gcd = get_gcd(a, ai);
if ((r - ri) % gcd)
flag = 1;
r += get_inv(a / gcd, ai / gcd) * ((ri - r) / gcd) % (ai / gcd) * a;
(a /= gcd) *= ai, ((r %= a) += a) %= a;
}
if (flag)
puts("-1");
else
printf("%lld\n", r);
}
return 0;
}