—— Summon, Light!
0%

hdu 5728 PowMod 数论

发表于 更新于 Valine：

[PowMod][1]

先贴官方题解

官方题解

其中第二段根本不懂。。。然后就去学习了一下

引理：设 p 为 n 的一个质因数，
$$if\quad p^2|n\quad then\quad \varphi(n)=\varphi(\frac{n}{p})\times p\quad else\quad \varphi(n)=\varphi(\frac{n}{p})\times \varphi(p)$$
前一部分可以用 $\varphi(n)$ 的定义来证明，后一部分就是积性函数的性质(详见[欧拉函数为什么是积性函数][2])

题中n is a square-free number表示 $n$ 没有平方因子。
我们设 $p$ 为 $n$ 的一个质因数，对 $p\mid i$ 的情况分类讨论：
$$\sum_{i=1}^{m}\varphi(i\times n)=\sum_{p\nmid i}^{m}\varphi(i\times n)+\sum_{p\mid i}^{m}\varphi(i\times n) \\
=\varphi(p)\times \sum_{p\nmid i}^{m}\varphi(i\times \frac{n}{p})+p\times \sum_{p\mid i}^{m}\varphi(i\times \frac{n}{p}) \\
(\because\ p\ is\ a\ prime\ number) \\
=\varphi(p)\times \sum_{p\nmid i}^{m}\varphi(i\times \frac{n}{p})+(\varphi(p)+1)\times \sum_{p\mid i}^{m}\varphi(\frac{i}{p}\times n) \\
(\because p\mid i\ 和\ p\nmid i\ 合并为全集 ) \\
=\varphi(p)\times \sum_{i=1}^{m}\varphi(i\times \frac{n}{p})+\sum_{p\mid i}^{m}\varphi(\frac{i}{p}\times n) \\
=\varphi(p)\times \sum_{i=1}^{m}\varphi(i\times \frac{n}{p})+\sum_{i=1}^{m/p}\varphi(i\times n)$$

再解释另一个式子：$a^b\equiv a^{\varphi(p)+b%\varphi(p)}\pmod p$，我们分两种情况：

  1. $a$与$p$互质，那么由费马-欧拉定理，$a^{\varphi(p)}\equiv 1 \pmod p$，原式成立；
  2. $a$与$p$不互质，则$a^x$在$\varphi(p)$次之内就会变为0。需要一个条件，$b\geq \varphi(p)$，那么实际上$a^b\equiv a^{\varphi(p)+b%\varphi(p)}\equiv 0 \pmod p$，原式成立。

但是为什么满足$b\geq \varphi(p)$我还是觉得很难解释，代码是抄标程的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int MOD=1000000007;
const int N=1e7+5;
bool b[N];
int phi[N],s[N],prime[700000];
int tot=0;

void getphi()
{
    phi[1]=1;
    for (int i=2;i<N;i++) {
        if (!b[i]) {
            phi[i]=i-1;
            prime[++tot]=i;
        }
        for (int j=1;j<=tot;j++) {
            if (i*prime[j]>=N) break;
            b[i*prime[j]]=1;
            if (i%prime[j]==0) {
                phi[i*prime[j]]=phi[i]*prime[j];
            } else {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
    s[0]=0;
    for (int i=1;i<N;i++)
        s[i]=(s[i-1]+phi[i])%MOD;
}

int getsum(int n,int m)
{
    if (m==0) return 0;
    if (m==1) return phi[n];
    if (n==1) return s[m];
    for (int i=1;i<=tot;i++) {
        if (n%prime[i]==0)
            return (1LL*(prime[i]-1)*getsum(n/prime[i],m)%MOD+getsum(n,m/prime[i]))%MOD;
    }
    return 0;
}

int pow(long long x,int n,int M)
{
    long long res=1;
    while (n) {
        if (n&1) res=res*x%M;
        x=x*x%M;
        n>>=1;
    }
    return res;
}

int solve(int k,int p)
{
    if (p==1) return 0;
    int now=solve(k,phi[p]);
    return pow(k,phi[p]+now,p);
}

int main()
{
    int n,m,p;
    getphi();
//  printf("%d\n",tot);
    while (scanf("%d%d%d",&n,&m,&p)!=EOF) {
        int k=getsum(n,m);
        printf("%d\n",solve(k,p));
    }
    return 0;
}

本篇博客借助 markdown 高清重制~~
[1]:http://acm.hdu.edu.cn/showproblem.php?pid=5728
[2]:http://blog.csdn.net/summonlight/article/details/51967425

咖啡，亦我所需也