## 题目描述

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, 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;
}


## 题目描述

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;
}


## 题目描述

A natural number $d$ is a unitary divisor of $n$ if $d$ is a divisor of $n$ and if $d$ and ${n \over d}$ are coprime.
Let $\sigma^{\ast}(n)$ be the sum of the unitary divisors of $n$. For example, $\sigma^{\ast}(1)=1, \; \sigma^{\ast}(2)=3$ and $\sigma^{\ast}(6)=12$.
Let $S(n)=\sum_{i=1}^n \sigma^{\ast}(i)$.
Given $n$, find $S(n) \bmod 2^{64}$.

## 算法分析

\begin{align} S(n)&=\sum_{i=1}^n \sigma^{\ast}(i) \\ &=\sum_{i=1}^n i \sum_{j=1}^{\lfloor n/i \rfloor} [(i, j)=1] \end{align}

\begin{align} S(n)&=\sum_{d=1}^n \mu(d) \sum_{i=1}^{\lfloor n/d \rfloor} di \sum_{j=1}^{\lfloor n/d^2i \rfloor} 1 \\ &=\sum_{d=1}^n d \cdot \mu(d) \sum_{i=1}^{\lfloor n/d \rfloor} i \cdot \left\lfloor {n \over d^2i} \right\rfloor \end{align}

\begin{align} S(n)=\sum_{d=1}^{\lfloor \sqrt{n} \rfloor} d \cdot \mu(d) \sum_{i=1}^{\lfloor n/d^2 \rfloor} i \cdot \left\lfloor {n \over d^2i} \right\rfloor \end{align}

\begin{align} F(n)=1-\sum_{i=2}^n i \cdot F\left(\left\lfloor {n \over i} \right\rfloor\right) \end{align}

## 代码

#include <cmath>
#include <cstdio>

#define int long long

static const int N = 10000005;
static const int M = 50005;
int prime[N], mui[N], g[M];
bool vis[N];

void init() {
int top = 0; mui = 1;
for (int i = 2; i < N; ++ i) {
if (! vis[i]) prime[top ++] = i, mui[i] = -1;
for (int j = 0; j < top; ++ j) {
int k = i * prime[j]; if (k >= N) break; vis[k] = true;
if (i % prime[j]) mui[k] = -mui[i]; else { mui[k] = 0; break; }
}
}
for (int i = 2; i < N; ++ i) (mui[i] *= i) += mui[i - 1];
}

int get_sum(int n) {
return n & 1 ? ((n + 1) >> 1) * n : (n >> 1) * (n + 1);
}

static const int HASH = 23456789;
int numr, h[HASH];
struct Record {
int n, v, nxt;
} r[HASH];

void add_rec(int n, int v) {
r[++ numr] = (Record) { n, v, h[n % HASH] }, h[n % HASH] = numr;
}

int get_f(int n) {
if (n < N) return mui[n];
for (int i = h[n % HASH]; i; i = r[i].nxt)
if (r[i].n == n) return r[i].v;
int ret = 1;
for (int i = 2, j; i <= n; i = j + 1)
j = n / (n / i), ret -= (get_sum(j) - get_sum(i - 1)) * get_f(n / i);
return add_rec(n, ret), ret;
}

int get_g(int n) {
if (n < M && g[n]) return g[n];
int ret = 0;
for (int i = 1, j; i <= n; i = j + 1)
j = n / (n / i), ret += (get_sum(j) - get_sum(i - 1)) * (n / i);
return ret;
}

int calc(int n) {
int ret = 0;
for (int i = 1, j; i * i <= n; i = j + 1)
j = sqrt(n / (n / i / i) + 0.01), ret += (get_f(j) - get_f(i - 1)) * get_g(n / i / i);
return ret;
}

signed main() {
int T; scanf("%lld", &T), init();
for (int i = 1; i < M; ++ i) g[i] = get_g(i);
for (int n; T --;) scanf("%lld", &n), printf("%llu\n", calc(n));
return 0;
}

## 题目描述

Let $G(n)=\sum_{i=1}^n \sum_{j=i+1}^n (i, j)$.
For example, $G(1)=0, \; G(2)=(1, 2)=1, \; G(3)=(1, 2)+(1, 3)+(2, 3)=3$.
Given $N$, find $G(N)$ modulo $2^{64}$.

## 算法分析

\begin{align} G(n)&=\sum_{i=1}^n \sum_{j=i+1}^n (i, j)=\sum_{i=2}^n \sum_{j=1}^{i-1} (i, j) \\ &=\sum_{d=1}^n d \sum_{i=2}^{\lfloor n/d \rfloor} \sum_{j=1}^{i-1} [(i, j)=1] \\ &=\sum_{d=1}^n d \sum_{i=2}^{\lfloor n/d \rfloor} \varphi(i) \end{align}

\begin{align} \sum_{i=1}^n (\varphi \ast 1)(i)&={n(n+1) \over 2} \\ &=\sum_{i=1}^n \sum_{j \mid i} \varphi(j) \\ &=\sum_{ij \le n} \varphi(j) \\ &=\sum_{i=1}^n \sum_{j=1}^{\lfloor n/i \rfloor} \varphi(j) \\ &=\sum_{i=1}^n S\left(\left\lfloor {n \over i} \right\rfloor\right) \end{align}

\begin{align} S(n)&={n(n+1) \over 2}-\sum_{i=2}^n S\left(\left\lfloor {n \over i} \right\rfloor\right) \\ G(n)&=\sum_{d=1}^n d \cdot \left(S\left(\left\lfloor {n \over d} \right\rfloor\right)-1\right) \end{align}

## 代码

#include <map>
#include <cstdio>

#define int long long

static const int N = 10000000;
int prime[N], phi[N];
bool vis[N];

void init() {
int top = 0; phi = 1;
for (int i = 2; i < N; ++ i) {
if (! vis[i]) prime[top ++] = i, phi[i] = i - 1;
for (int j = 0; j < top; ++ j) {
int k = i * prime[j]; if (k >= N) break;
vis[k] = true;
if (i % prime[j]) phi[k] = phi[i] * (prime[j] - 1); else { phi[k] = phi[i] * prime[j]; break; }
}
}
for (int i = 2; i < N; ++ i) phi[i] += phi[i - 1];
}

int get_sum(int n) {
return n & 1 ? ((n + 1) >> 1) * n : (n >> 1) * (n + 1);
}

std :: map <int, int> mp;

int get_phi(int n) {
if (n < N) return phi[n];
if (mp.count(n)) return mp[n];
int ret = get_sum(n);
for (int i = 2, j; i <= n; i = j + 1)
j = n / (n / i), ret -= (j - i + 1) * get_phi(n / i);
return mp[n] = ret;
}

int calc(int n) {
int ret = 0;
for (int i = 1, j; i <= n; i = j + 1)
j = n / (n / i), ret += (get_sum(j) - get_sum(i - 1)) * (get_phi(n / i) - 1);
return ret;
}

signed main() {
int T; scanf("%lld", &T), init();
while (T --) {
int n; scanf("%lld", &n), printf("%llu\n", calc(n));
}
return 0;
}

## 题目描述

Joe is a frog who likes to jump a lot. In fact, that’s all he does: he jumps forwards and backwards on the integer axis (a straight line on which all the integer numbers, both positive and negative are marked). At first, Joe sits next to the point marked with $0$. From here, he can jump in the positive or the negative direction a distance equal to either $x_1$ or $x_2$. From the point where he arrived, he can jump again a distance equal to $x_1$ or $x_2$, in the positive or the negative direction and so on.. Joe wants to arrive next to the point marked with the number $P$, after exactly $K$ jumps. You have to decide whether such a thing is possible.

## 题意概述

\left\{ \begin{align} P_1x_1-N_1x_1+P_2x_2-N_2x_2&=P \\ P_1+N_1+P_2+N_2&=K \end{align} \right.

## 代码

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

#define int long long

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
int x1, x2, p, k;
void input() { io > x1 > x2 > p > k; }
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;
}
bool check(int x, int y) {
if (abs(x) + abs(y) > k) return false;
if (k - abs(x) - abs(y) & 1) return false;
io < (char *) "YES\n";
int t = k - abs(x) - abs(y) >> 1;
if (x > 0) io < x + t < ' ' < t < ' ';
else io < t < ' ' < -x + t < ' ';
if (y > 0) io < y < ' ' < 0 < '\n';
else io < 0 < ' ' < -y < '\n';
return true;
}
void process() {
int x, y, gcd = ex_gcd(x1, x2, x, y);
if (p % gcd) io < (char *) "NO\n";
else {
x1 /= gcd, x2 /= gcd, p /= gcd, x *= p, y *= p;
for (int i = -abs(p) - 1; i <= abs(p) + 1; ++ i)
if (check(x + x2 * i, y - x1 * i)) goto label;
io < (char *) "NO\n";
label: ;
}
}

public:
void solve() { input(), process(); }
} solver;

signed main() {
solver.solve();
return 0;
}


## 题目描述

A sequence $A$ is called an integer sequence of length $N$ if all its elements $A_1, A_2, \ldots, A_N$ are non-negative integers less than $2000000000$. Consider two integer sequences of length $N, A$ and $X$. The result of their multiplication $(A \cdot X)$ is an integer number $R=\sum_{i=1}^N A_iX_i$. Your task is to solve the equation $A \cdot X \equiv B \pmod P$, given the integer sequence $A$ and the integer numbers $B$ and $P$.

## 算法分析

\left\{ \begin{align} A_1x_1+A_2y_1&=g_2 \\ g_2x_2+A_3y_2&=g_3 \\ \cdots& \\ g_{N-1}x_{N-1}+A_Ny_{N-1}&=g_N \\ g_Nx_N+Py_N&=(g_N, P) \end{align} \right.

## 代码

#include <cctype>
#include <cstdio>

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
static const int N = 101;
int n, p, m, a[N], x[N], y[N];
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;
}
void input() {
io > n > p > m;
for (int i = 1; i <= n; ++ i) io > a[i], a[i] %= p;
}
void process() {
int g = a; x = y = 1;
for (int i = 2; i <= n; ++ i) g = ex_gcd(g, a[i], x[i - 1], y[i - 1]);
g = ex_gcd(g, p, x[n], y[n]);
if (m % g) io < (char *) "NO\n";
else {
io < (char *) "YES\n", g = m / g;
for (int i = 1; i <= n; ++ i) {
int t = g * (y[i - 1] + p);
for (int j = i; j <= n; ++ j) t = 1ll * t * (x[j] + p) % p;
io < t < ' ';
}
io < '\n';
}
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

There are two boxes. There are $A$ balls in the first box, and $B$ balls in the second box. It is possible to move balls from one box to another. From one box into another one should move as many balls as the other box already contains. You have to determine, whether it is possible to move all balls into one box.

## 题目描述

There is an equation $ax+by+c=0$. Given $a,b,c,x_1,x_2,y_1,y_2$ you must determine, how many integer roots of this equation are satisfy to the following conditions: $x_1 \le x \le x_2, \; y_1 \le y \le y_2$. Integer root of this equation is a pair of integer numbers $(x,y)$.

## 代码

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

#define int long long

using namespace std;

namespace std {
template <typename T>
void maxify(T &a, T b) { b > a && (a = b); }
template <typename T>
void minify(T &a, T b) { b < a && (a = b); }
}

struct IOManager {
template <typename T>
inline bool read(T &x) {
char c; bool flag = false; x = 0;
while (~ c && ! isdigit(c = getchar()) && c != '-') ;
c == '-' && (flag = true, c = getchar());
if (! ~ c) return false;
while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
return (flag && (x = -x), true);
}
inline bool read(char &c) {
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
inline int read(char s[]) {
char c; int len = 0;
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
if (! ~ c) return 0;
while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
return (s[len] = '\0', len);
}
template <typename T>
inline IOManager operator > (T &x) {
read(x); return *this;
}
template <typename T>
inline void write(T x) {
x < 0 && (putchar('-'), x = -x);
x > 9 && (write(x / 10), true);
putchar(x % 10 + '0');
}
inline void write(char c) {
putchar(c);
}
inline void write(char s[]) {
int pos = 0;
while (s[pos] != '\0') putchar(s[pos ++]);
}
template <typename T>
inline IOManager operator < (T x) {
write(x); return *this;
}
} io;

struct Solver {
private:
int a, b, c, x1, x2, y1, y2, x, y, gcd;
void input() { io > a > b > c > x1 > x2 > y1 > y2; }
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;
}
void process() {
if (! b) swap(a, b), swap(x1, y1), swap(x2, y2);
if (! b) {
if (c) io < 0 < '\n';
else io < (x2 - x1 + 1) * (y2 - y1 + 1) < '\n';
return;
}
gcd = ex_gcd(a, b, x, y);
if (c % gcd) { io < 0 < '\n'; return; }
a /= gcd, b /= gcd, c /= gcd, x *= -c, y *= -c;
if (b < 0) b = -b, a = -a;
x += 1000000000 * b, y -= 1000000000 * a;
y += ((x - x1) / b + 1) * a, x -= ((x - x1) / b + 1) * b;
x += b, y -= a;
if (x > x2) { io < 0 < '\n'; return; }
int ans = (x2 - x) / b + 1;
if (! a) {
if (y < y1 || y > y2) ans = 0;
} else {
int l = -1000000000, r = 1000000000, cnt = 0;
while (l + 1 < r) {
int mid = l + r >> 1;
if (y - a * mid < y1) if (a > 0) r = mid; else l = mid;
else if (a < 0) r = mid; else l = mid;
}
if (a < 0 && y - a * l == y1) -- l, -- r;
if (a > 0 && y - a * r == y1) ++ r, ++ l;
int l1 = l, r1 = r; l = -1000000000, r = 1000000000;
while (l + 1 < r) {
int mid = l + r >> 1;
if (y - a * mid < y2) if (a > 0) r = mid; else l = mid;
else if (a < 0) r = mid; else l = mid;
}
if (a < 0 && y - a * r == y2) ++ r, ++ l;
if (a > 0 && y - a * l == y2) -- l, -- r;
if (l > l1) swap(l, l1), swap(r, r1);
maxify(r, 0ll), minify(l1, ans - 1);
ans = l1 - r + 1;
}
io < ans < '\n';
}

public:
void solve() { input(), process(); }
} solver;

signed main() {
solver.solve();
return 0;
}