# 「补档计划」求解乘法逆元的方法

### 定义

$$x \times x^{-1} \equiv 1 \text{ (mod p)}$$

# 「BJ模拟」简单精暴的题目-二项式定理

$\sum\limits_{j = 1}^1 (\sum\limits_{l = j}^1 s(l))^k) \text{ mod } 1000000007$
$\sum\limits_{j = 1}^2 (\sum\limits_{l = j}^2 s(l))^k) \text{ mod } 1000000007$
$\cdots$
$\sum\limits_{j = 1}^n (\sum\limits_{l = j}^n s(l))^k) \text{ mod } 1000000007$

# 「POJ-2720」Last Digits-欧拉函数

Exponentiation of one integer by another often produces very large results. In this problem, we will compute a function based on repeated exponentiation, but output only the last n digits of the result. Doing this efficiently requires careful thought about how to avoid computing the full answer.

Given integers b, n, and i, we define the function f(x) recursively by f(x) = b f(x-1) if x > 0, and f(0)=1. Your job is to efficiently compute the last n decimal digits of f(i).

# 「BZOJ-2242」计算器-BSGS

1,给定y,z,p,计算Y^Z Mod P 的值；

2,给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数；

3,给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。

# 「POJ-1284」Primitive Roots-原根+欧拉函数

We say that integer x, 0 < x < p, is a primitive root modulo odd prime p if and only if the set { (xi mod p) | 1 <= i <= p-1 } is equal to { 1, …, p-1 }. For example, the consecutive powers of 3 modulo 7 are 3, 2, 6, 4, 5, 1, and thus 3 is a primitive root modulo 7.
Write a program which given any odd prime 3 <= p < 65536 outputs the number of primitive roots modulo p.

# 「POJ-3243」Clever Y-BSGS

Little Y finds there is a very interesting formula in mathematics:

$X^Y$ mod $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?

# 「BZOJ-1876」SuperGCD-高精度

Sheng bill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大公约 数）！因此他经常和别人比赛计算GCD。有一天Sheng bill很嚣张地找到了你，并要求和你比 赛，但是输给Sheng bill岂不是很丢脸！所以你决定写一个程序来教训他。

# 「POJ-2891」Strange Way to Express Integers-扩展欧几里德

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 a1, a2, \cdots , ak. For some non-negative m, divide it by every ai (1 \leq i \leq k) to find the remainder ri. If a1, a2, \cdots , ak are properly chosen, m can be determined, then the pairs (ai, ri) 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?