引言：今天上课老师讲了这个，但是信息量有点大，没有很好的理解，先把它放在博客上，以后再学习。

同余基本知识

• 模和同余：设 $a$ 、$b$ 和 $m$ 均为整数，且 $m>0$ 。如果 $a$ 和 $b$ 被 $m$ 除所得的余数相同，那么称 $a$ 和 $b$ 关于模 $m$ 是同余的，记作
  $$a \equiv b(mod \; m)$$
• 几个等价定义：
• $a$ 和 $b$ 关于模 $m$ 是同余的：
  $$a=mq_1+r \quad b=mq_2+r$$

$$a \equiv b(mod \; m)$$

• $b-a$ 能被 $m$ 整除，记 $m|a-b$
  $$a-b\equiv 0(mod \; m)$$

同余性质

• $a \equiv a(mod \; m)$
• $a \equiv b(mod \; m) \Longrightarrow b \equiv a(mod \; m)$
• $a \equiv b(mod \; m) \quad b \equiv c(mod \; m) \Longrightarrow a \equiv c(mod \; m)$
• 设$a \equiv b(mod \; m)$，$b \equiv c(mod \; m)$，那么
  $$ac \equiv bd(mod \; m)$$

$$ac \equiv bc(mod \; m)$$
$$a^n \equiv b^n(mod \; m)$$

• 费马小定理：设 $a$ ，$p$ 为正整数，且 $p$ 为素数，$gcd(p,a)=1$ ,那么
  $$a^{p-1} \equiv 1(mod \; p)$$

原根与离散对数

• 原根与离散对数是数论中的一个重要内容
• 给定正整数 $m$ ，正整数 $a$，$b$，$gcd(a,m)=gcd(b,m)=1$ ，求最小的非负整数 $x$ ，使得 $a$$x$ $≡$ $b$ $(mod$ $m)$ 。
• 原根： 给定整数 $m$ ，$g$ ， $gcd(g,m)=1$ ，若满足$g^x$ $≡$ $1$ $(mod$ $m)$ 的最小正整数 $x=φ(m)$ ，则 $g$ 即为模 $m$ 的原根。

剩余类与既约剩余系

• 剩余类：对于整数 $a$ 及模 $m$ ，则集合$A=\{ \;x\; | \;x≡ a (mod\; m) \;\}$ 称为模 $m$ 关于 $a$ 的一个剩余类。
• 完全剩余系：$\{0，1，2，…，m-1\}$ 是一个特殊的集合，元素个数 $m$ ，其中任何两个数都不同余，称为完全剩余系。
• 任何 $m$ 个元素的集合 $X$ ，如果其中任何两个数都不同余，那么 $X$ 也是一个完全剩余系。
• 既约剩余系：设 $m$ 为正整数，在与 $m$ 既约的所有剩余类中，每一个类中取一个数，构成一个集合 $X$ ，则 $X$ 称为模 $m$ 的一个简化剩余系。
• 既约剩余系的有 $r=φ(m)$ 个元素。

举例
1：若p是素数，则{1，2，3，…，p-1}是模p的一个既约剩余系。
2：{1，5，7，11}是模12的一个既约剩余系。

• 结论：模 $m$ 的既约剩余系的 $φ(m)$ 个元素对模 $m$ 乘法构成一个群。

模方程

$a \equiv b(mod \; m)$ 相当于求 $ax+my=b$

根据前面求 $ax+my=b$ 的步骤：

• 求 $d=gcd(a,m)$ ,写 $a=da_0$ ，$m=dm_0$
• 若 $d \nmid b$ ，则 $a \equiv b(mod \; m)$ 无解；否则，$a \equiv b(mod \; m)$ 有 $d$ 个点。
• 由 $ax_0+my_0=d$ ，改写为 $x=x_0\;\frac{b}{d}$ ，$y=y_0\;\frac{b}{d}$
• $a \equiv b(mod \; m)$ 的所有解可写为：
  $$x=(x_0\;\frac{b}{d}+i\;\frac{m}{d})mod\; m,i=0,1,2,...,d-1$$

欧拉定理与费尔玛小定理

• 欧拉定理：设 $m$ 是大于 $1$ 的整数，整数 $a$ 与 $m$ 互质，即 $(a,m)=1$ ，则 $a^{φ(m)}\equiv1(mod \; m)$；这里，$φ(m)$ 是欧拉函数，即它是正整数 $1，2，…，m$ 中与 $m$ 互质的数的个数。
• 费尔玛小定理：设 $p$ 为素数，整数 $a$ 与 $p$ 互质，即 $(a,p)=1$ ，则 $a^{p-1} \equiv 1(mod \; p)$ 。一般地，对任何整数 $a$ ，均有则 $a^p \equiv a(mod\ p)$。

快速模幂运算

• 模幂运算—快速计算法
• 将 $r$ 化为二进制数 $(b_kb_{k-1}…b_2b_1b_0)$ 的形式，然后反复平方取余数。然后从最低位开始，自右至左逐位扫描。每次迭代时．用到下面两个恒等式中的。

$$a^{2c}mod\ m=(a^2)^cmod\ m$$
$$a^{2c+1}mod\ m=a*(a^2)^cmod\ m$$

• 代码

long modular_power1(long a, long r, long m){
  long d, t;
    d=1;t=a;   
    while (r>0){   
      if ((r%2)==1) d=(d*t) % m；
      r=r/2;
      t=t*t % m;
    }
    return d;
}

原根

（一）原根有关概念

• 阶：设 $m$ 是正整数，$a$ 是整数，若有正整数 $r$ 使得，$a^r \equiv 1(mod \; m)$，但对于任何 $i$ ，$1 \leq i<r$ ，均有$a^i \equiv 1(mod \; m)$ ，那么称 $r$ 为 $a$ 模 $m$ 的阶。记$r=ord_m(a)$ ，也记为 $\delta_m(a)$
• 若 $r$ 为 $a$ 模 $m$ 的阶，则对任何 $i$ ， $0 \leq i<r$，那么 $a_i(mod \ m)$ 的结果两两不同。
• 性质：设正整数 $a$ 与 $m$ 互质，即 $gcd(a,m) = 1$ 。对正整数 $d$ ，若 $a_d≡1(mod \ m)$ ，则 $\delta_m(a)$ 整除 $d$ 。

原根

• 设 $m$ 是正整数，$g$ 是整数，若 $g$ 模 $m$ 的阶等于 $φ(m)$ ，则称 $g$为模 $m$ 的一个原根。（其中 $φ(m)$ 表示 $m$ 的欧拉函数），特别地，若 $m$ 为素数 $p$ ，若 $g$ 模 $p$ 的阶等于 $p-1$ ，那么 $g$ 为模 $p$ 的一个原根。

举例

• 例1. p=7
  $1$到$6$中的任何数均与$p$互质;取$g=3$，那么$3^0\equiv 1，3^1\equiv 3，3^2\equiv 2，3^3\equiv 6，3^4\equiv 4，3^5\equiv 5，3^6\equiv 1(mod \; 7)$(重复)；所以$g=3$为原根。
• 例2. p=11
  $1$到$10$中的任何数均与$p$互质;取$g=3$，那么$3^0\equiv 1，3^1\equiv 3，3^2\equiv 9，3^3\equiv 5，3^4\equiv 4，3^5\equiv 1 (mod \; 11)$(重复)，$r=5\neq 10$ ；所以$g=3$不为原根。

取$g=3$，那么$3^0\equiv 1，3^1\equiv 3，3^2\equiv 9，3^3\equiv 5，3^4\equiv 4，3^5\equiv 1 (mod \; 11)$(重复)，$r=5\neq 10$ ；所以$g=3$不为原根；类似地$g=4$也不为原根。
$1$到$10$中的任何数均与$p$互质;取$g=7$，那么$7^0\equiv 1$，$7^1\equiv 7$，$7^2\equiv 5$，$7^3\equiv 2$，$7^4\equiv 3$，$7^5\equiv 10$，$7^6\equiv 4$，$7^7\equiv 6$，$7^8\equiv 9$，$7^9\equiv 8$，$7^{10}\equiv 1$ $(mod \; 11)$(重复)，$r=10=p-1$ ；所以$g=7$为原根。

原根的性质

• 设正整数 $a$ 与 $m$ 互质，即 $gcd(a,m) = 1$ 。对正整数 $d$ ，若 $a^d≡1(mod \; m)$ ，则 $\delta_m(a)$ 整除 $d$ ，特别地，$\delta_m(a)$ 整除 $φ(m)$ 。应用：在 $p=7$ 例子中，当 $a= 3$ 时，我们仅需要验证 $3$ 的 $1$ 、$2$ 、$3$ 次方模 $7$ 的余数即可，如有余数为 $1$ ，那么 $a$ 不是模 $p=7$ 的原根。
• 记 $r = \delta_m(a)$ ，则 $a_1, a_2,..., a_{r-1} (mod \; m)$ 两两不同余。因此当 $a$ 是模 $m$ 的原根时，$a_0，a_1，… ，a_{r-1}$ 构成模 $m$ 的简化剩余系。
• 模 $m$ 有原根的充要条件是 $m= 1、2、4、p、2p、p^n$ ，其中 $p$ 是奇质数，$n$ 是任意正整数。（证明略）
• 对正整数 $a$ ，设 $gcd(a,m) = 1$ 。如果 $a$ 是模 $m$ 的原根，那么 $a$ 是整数模 $m$ 乘法群 $Zm^*$ 的一个生成元，即 $Zm^*$ 的元素 $x$ 均可以表示为 $a$ 的幂，$x=a^k$ 。
• $Zn$ 有 $r=φ(m)$ 个元素，如果 $g$ 是生成元，那么 $1=g^0$ ，$g^1$ ，$g^2$ ， ……，$g^{r-1}$ 互不相同（mod m下）。
  注：
• 所有整数在模 $m$ 下所有余数相同的数构成一个等价类（称为同余类）；所有同余类取一个代表构成一个集合，实际上是整数集 $Z$ 模 $m$ 构成的商集合 $Z/mZ$ 。
• 所有与 $m$ 互质的正整数构成的等价类构成的集合 $Zm^*$ 构成一个乘法群 $Zn$ 。$Zn$ 有 $φ(m)$ 个元素。
  (1) 上述 $r=φ(m)$ 个元素中， $g^t$ 能够成为生成元，其充分必要条件是 $t$ 与 $φ(m)$ 互质。在 $1$ 到 $r$ 中与 $r$ 互质的个数为 $φ(r)$ ；(2) 若 $Zn$ 有生成元，那么个数为 $φ(φ(m))$ 个；
• 若模 $m$ 有原根，则它有 $φ(φ(m))$ 个原根。
• 如果 $p$ 为素数，那么素数 $p$ 一定存在原根，并且模 $p$ 的原根个数为 $φ(p-1)$ 。

原根的判断

(1) 按定义判定：$g$ 的阶 $r= φ(m)$

(2) 设 $p$ 为素数：

• 设一个数 $g$ 是与 $p$ 互质的整数，$p$ 为模 $p$ 的原根，当且仅当，$g^i \; mod \; p$ $(0 \leq i<p-1)$ 的结果两两不同（两两不同余）。
  即：$g^i mod \; p$ $≠$ $g^j mod \; p$ （ $p$ 为素数），$i≠j$ ，$0<i$ , $j<p-1$ 。
• 设一个数 $g$ 是与 $p$ 互质的整数，$g$ 为模 $p$ 的原根，当且仅当，$g^r \equiv 1 (mod \; p)$ 仅在 $r=p-1$ 时成立、而在 $0<r<p-1$ 时不成立。

注 ：以后为了描述方便起见，将 $a$ 的生成元 $g$ 表示 $a \equiv g^x (mod \; p)$ 直接表示成 $a=g^x$ ，其实在群的观点下是合理的。

原根求法

(1) 求原根目前的做法只能是从 $2$ 开始枚举，然后暴力判断 $g^{p-1} \equiv 1 (mod \; p)$ ,是否当且仅当指数为 $p-1$ 的时候成立。如成立，则为原根。由于原根一般都不大，所以可以暴力得到。

(2) 求素数 $p$ 模原根的方法：对 $p$ 求素因子分解，即是的标准分解式
$$p-1=p_1^{e_1}p_2^{e_2}...p_k^{e_k}$$
若恒有
$$g^{ \frac{p-1}{p_i}} \neq 1(mod \; p),i=1,2...k$$
成立，则 $g$ 就是 $p$ 的原根。

原根求法举例

$p=47$ 是素数，求 $p$ 的原根。

• $r=p-1=46=2×23$（ $2$ 和 $23$ 都是素数），那么，$p=47$ 的原根 $g$ 需满足 $g^{p-1} \equiv 1(mod \; p)$，但 $g^2 \neq 1$ $(mod \; p)$，且 $g^{23} \neq 1$ $(mod \; p)$。原根个数 $φ(r)= φ(46)=22$ 。模 $47$ 的非二次剩余有：$3$ , $5$ , $6$ ,$10$ , $11$ , $12$ , $14$ , $17$ , $19$ , $21$ , $22$ , $24$ , $27$ , $29$ , $31$ , $32$ , $34$ , $38$ , $39$ , $40$ , $43$ , $45$ ，正好 $22$ 个,这些就是模 $47$ 的原根。

求原根的程序

#include <iostream>  
#include <string.h>  
#include <algorithm>  
#include <stdio.h>  
#include <math.h>  
#include <bitset>    
using namespace std;  
typedef long long LL;    
const int N = 1000010;    
bitset<N> prime;  
int p[N],pri[N];  
int k,cnt;
void isprime() {  //素数表构建
    prime.set();  
    for(int i=2; i<N; i++) {  
        if(prime[i]){  
            p[k++] = i;  
            for(int j=i+i; j<N; j+=i)  prime[j] = false;  
        }  
    }  
}    
void Divide(int n) {  //求n的所有的质因子 
    cnt = 0; int t = (int)sqrt(1.0*n);  
    for(int i=0; p[i]<=t; i++) {  
        if(n%p[i]==0) {  
            pri[cnt++] = p[i];  while(n%p[i]==0) n /= p[i];  
        }  
    }  
    if(n > 1) pri[cnt++] = n;  
}
LL quick_mod(LL a,LL b,LL m){//快速幂计算  
    LL ans = 1;  
    a %= m;  
    while(b) {  
        if(b&1){  
            ans = ans * a % m;  
            b--;  
        }  
        b >>= 1;  
        a = a * a % m;  
    }  
    return ans;  
}
int main(){  
    int p;  isprime();  
    while(cin>>p) {  
        Divide(p-1);  
        for(int g=2; g<p; g++) {  
            bool flag = true;  
            for(int i=0; i<cnt; i++) {  
                int t = (p - 1) / pri[i];  
                if(quick_mod(g,t,p) == 1) {  flag = false;  break;  }  
            }  
            if(flag) {  
                int root = g;  
                cout<<root<<endl;  
            }  
        }  
    }  
    return 0;  
}

例题

Description

We will give you a non-negative integer $m$ and a prime number $p$ . And we define $f(i)$ is the number of pair( $x,y$ ) that satisfies $(x+y)^i≡x^i \% p$ and $1≤x≤p−1,1≤y≤m$ . Now, you have to calculate the sum. Maybe the sum is too big, so you only need to output the sum $\sum^{p-1}_{i=0} if(i)$ after mod $1e9+7$ .

Input

The first line contains only one integer $T$ , which indicates the number of test cases.
For each test case, there are a integer $m(1≤m≤p−1)$ and a prime number $p(2≤p≤1e9+7)$ on one line.

Output

For each test case, output one line "Case #x: y" , where x is the case number (starting from $1$ ) and $y$ is the sum after mod $1e9+7$ .

Sample Input

3
5 7
3 11
2 103

Sample Output

Case #1: 210
Case #2: 390
Case #3: 50388

题意

给定正整数 $m>0$ 和素数 $p$ 。记 $f(i)$ 为满足条件 $(x+y)^i≡x^i \% p$ 及 $1≤x≤p−1、1≤y≤m≤p−1$ 的数对 $(x,y)$ 的组数。你的任务是计算和
$\sum^{p-1}_{i=0} if(i)(mod \; 10^9+7)$ 。

分析

本题要求满足 $(x+y)^i≡x^i \%p$ ，$1≤x≤p−1$、$1≤y≤m≤p−1$ 的数对 $(x,y)$ 个数。直接去求 $x，y$ 不现实，但可以计算个数。对于素数 $p$ ，有原根 $g$ ，$g$ 也是生成元，即 $1$ 到 $p-1$ 的任何整数 $k$ 都可以用 $g$ 的幂 $g^t$ 表示，$0 \leq t<p-1$ 。现在，对于满足 $1≤x≤p−1$ 的 $x$ ，由于 $x$ 与 $p$ 互质，因此 $x$ 可写成 $x=g^u$ ；类似地，$y$可写成 $y=g^v$ ，$0≤u$ ，$v≤p-2$。

将 $x=g^u，y=g^v$ 代入 $(x+y)^i \equiv x^i(mod \; p)$ ,可得 $(g^u+g^v)^i \equiv g^{ui} (mod \; p)$. 变形为
$$[g^u(1+g^{v-u})]^i \equiv g^{ui} (mod \; p)$$
$$g^{ui}(1+g^{v-u})^i \equiv g^{ui}(mod \; p)$$
$$(1+g^{v-u})^i \equiv 1(mod \; p)$$

$w$ 共有 $gcd(i,p-1)$ 个（包括 $w$ 取 $0$ 的情况，应排除）。
注意 $x=g^u$ ，$y=g^v$ ，$1≤x≤p−1$ 、$1≤y≤m≤p−1$ ，$y$ 可有 $m$ 个，每个 $y$ 对应的 $v$ 是唯一的，因此 $v$ 也有 $m$ 个。

从 $1+g^{v-u}=g^w$ 可得 $g^{v-u}=g^w-1$ ，因此，对每个 $w$ ，$v-u$ 的值是唯一的；现在 $v$ 有 $m$ 个，每个 $v$ 对应的 $u$ 只有一个。

结论:对每个 $w$ ，数对 $(u,v)$ 共有 $m$ 个，因此数对 $(g^u，g^v)$ 共有 $m$ 对，从而数对 $(x，y)$ 共用 $m$ 对。实际的 $w$ 共有 $gcd(i,p-1)-1$ 个，因此对于确定的 $i$ ，$1≤i≤p−1$ ，$f(i)=[gcd(i,p-1)-1] \times m$

最后就是求
$$\sum^{p-1}_{i=1} if(i)(mod \; 10^9+7)=\sum^{p-1}_{i=1} i \times m \times [gcd(i,p-1)-1] (mod \; 10^9+7)$$

$$\sum^{p-1}_{i=1} if(i) = \sum^{p-1}_{i=1} i \times m \times [gcd(i,p-1)-1]=m\sum^{p-1}_{i=1} i \times gcd(i,p-1) - \frac{p(p-1)m}{2}$$

将 $1≤i≤p−1$ 中的所有 $i$ 进行分类，即 $gcd(i,p-1)$ 相同的放在一起。

设 $d=gcd(i,p-1)$ ，由于 $d=gcd(p-1-i,p-1)$ ， $0≤p-1-i≤p−2$

配对

$i:1,2,3,...,p-2,p-1$

$p-1-i:p-1-1,p-1-2,...,1,0$

$$\sum^{p-1}_{i=1}i \times gcd(i,p-1)=\sum_{d|p-1} d \sum^{p-1}_{i=1,d|i} i \times [gcd(i,p-1)=d]$$

$$=\sum_{d|p-1} d \sum^{p-1}_{i=1,d|i} i \times [gcd(\frac{i}{d},\frac{p-1}{d})=1]$$

对 $d|i$ ,记 $i=d_j$ ,则 $j=1,2,..., \frac{p-1}{d}$ ,代入上述等式最后一个公式,并重新将 $j$ 换回到 $i$ ,则有

$$\sum_{d|p-1} d \sum^{p-1}_{i=1} i \times [gcd( \frac{i}{d} , \frac{p-1}{d}) = 1]=\sum_{d|p-1} d^2 \sum^{ \frac{p-1}{d}}_{i=1} i \times [gcd(i , \frac{p-1}{d}) = 1]$$

$$=\sum_{d|p-1}d^2\frac{\frac{p-1}{d} \varphi (\frac{p-1}{d})+[\frac{p-1}{d}=1]}{2}$$

注:

• 当z>1时
  $$\sum_{i=1}^z i \times [gcd(i,z)=1]$$

$$=\frac{1}{2}(\sum_{i=1}^z i \times [gcd(i,z)=1]+\sum_{i=1}^z i \times [gcd(z-i,z)=1])$$
$$=\frac{1}{2}(\sum_{i=1}^z i \times [gcd(i,z)=1]+\sum_{i=1}^z (z-i) \times [gcd(z-i,z)=1])$$
$$=\frac{1}{2}\sum_{i=1}^z(i+(z-i)) \times [gcd(i,z)=1]=\frac{1}{2}\sum_{i=1}^z z \times [gcd(i,z)=1]$$
$$=\frac{1}{2}z\sum_{i=1}^z[gcd(i,z)=1]=\frac{1}{2}z \varphi(z)$$

• 当z=1时
  $$\sum_{i=1}^z i \times [gcd(i,z)=1]=1=\frac{z \varphi(z) + 1}{2}$$

代码

#include<bits/stdc++.h>
const int mod = 1e9+7;
using namespace std;
typedef long long ll;

int mod_mul(int a,int b)
{
    ll c = 1LL * a * b;
    return c - c / mod * mod;
}

int euler(int n) 
{
    int ret = n;
    int i;
    for(i = 2 ; i * i <= n ; i ++)
    {
        if(n % i == 0)
        {
            ret = ret - ret / i;
            while(n % i == 0)
            {
                n /= i;
            }
        }
    }
    if(n > 1)
    {
        ret = ret - ret / n;
    }
    return ret;
}

int solve(int n)
{
    int ans = 0;
    int tmp = 0;
    for(int i = 1 , j ; i * i <= n; i++)
    {
        j = n / i;
        if(i * j == n)
        {
            tmp = mod_mul( (1LL * j * euler(j) + ( j == 1 ) ) / 2 % mod, mod_mul( i , i ) );
            if((ans += tmp) >= mod) ans -= mod;


            if(i != j)
            {
                tmp = mod_mul( (1LL * i * euler(i) + ( i == 1 ) ) / 2 % mod, mod_mul( j , j ) );
                if((ans += tmp) >= mod) ans -= mod;
            }

        }
    }
    ans -= mod_mul( mod_mul( n, n + 1), 500000004);
    if(ans < 0) ans += mod;
    return ans;
}
int main()
{
    int t;
    int m,p,cas=0;
    scanf("%d",&t);
    while(t--)
    {
        cas++;
        scanf("%d%d",&m,&p);
        int ans = mod_mul( solve(p - 1), m );
        printf("Case #%d: ",cas);
        printf("%d\n",ans);
    }
    return 0;
}