关于数论的总结和专题练习….

乘法逆元是数论中重要的内容，也是 OI 中常用到的数论算法之一。

定义

在 $\text{mod p}$ 意义下我们把 $x$ 的乘法逆元写作 $x^{-1}$
$$x \times x^{-1} \equiv 1 \text{ (mod p)}$$

这里重新复习一下扩展欧几里得算法的常见应用。

普通快速幂在面对大量数据或单个够大数据时效率很低，这个时候我们就需要十进制快速幂，而如果模数是 long long 以内的数，我们可以用快速幂思想 $O(\text{log n})$ 完成快速乘，但我们其实可以 $O(1)$ 完成。

给定 $n$ 个整数 $A_1,A_2,A_n$ ，求有多少个三元组 $(i,j,k)$ 满足 $1 \leq i < j < k \leq n$ 且 $A_j-A_i=A_k-A_j$ 。

问题很简单，已知 $n, k, s(l)$，$\forall i \in N^+, i \leq n$，求 $\sum\limits_{j = 1}^i (\sum\limits_{l = j}^i s(l))^k) \text{ mod } 1000000007$。
即求:

共 $n$ 个数，其中 $\sum\limits_{i = a}^b f(i)$ 表示 $f(a) + \cdots + f(b)$ 的和。

将 $n_1$ 个 $A$，$n_2$ 个 $B$，$n_3$ 个 $C$，$n_4$ 个 $D$ 排成一个序列。求问有多少种排列方案使得排成的序列任意相邻的两个字母不同。

晓华所在的工作组正在编写一套高精度科学计算的软件，一些简单的部分如高精度加减法、乘除法早已写完了，现在就剩下晓华所负责的部分：实数的高精度开m次根。因为一个有理数开根之后可能得到一个无理数，所以这项工作是有较大难度的。现在要做的只是这项工作的第一步：只对自然数进行开整数次根，求出它的一个非负根，并且不考虑结果的小数部分，只要求把结果截断取整即可。程序需要根据给定的输入，包括需要开根的次数，以及被开根的整数；计算出它的非负根取整后的结果。

数论函数：定义域为正整数的函数。

积性函数

定义

积性函数：对于任意两个互质的正整数 $a,b$ ，均满足 $f(ab)=f(a)f(b)$ 的函数 $f$

完全积性函数：对于所有正整数 $a,b$ ，均满足 $f (ab) = f (a) f (b)$ 的函数 $f$

定义逐点加法： $(f + g)(x) = f(x) + g(x)$，$(f \cdot g)(x) = f(x)g(x)$

质数,欧拉函数及莫比乌斯函数的快速线性筛选法，时间复杂度 $O(n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

const int MAXN = 100000;
int phi[MAXN + 10], prime[MAXN + 10], mu[MAXN + 10], tot;
bool vis[MAXN + 10];
inline void init() {
    mu[1] = phi[1] = 1;
    for (register int i = 2; i <= MAXN; i++) {
        if (!vis[i]) prime[++tot] = i, phi[i] = i - 1, mu[i] = -1;
        for (register int j = 1; j <= tot && i * prime[j] <= MAXN; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j], mu[i * prime[j]] = 0;
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1), mu[i * prime[j]] = -mu[i];
        }
    }
}

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).

你被要求设计一个计算器完成以下三项任务：

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)的最小非负整数。

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.

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?

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

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?