Bluefissure's Blog

A Place for Recording

0%

HDU 5728 PowMod 数论 欧拉函数

2016 Multischool-Training-1-1006

 题目链接

思路:

首先,考虑到\(\varphi\)是一个积性函数,我们有下面两条性质

  • \(\varphi (mn)=\varphi (m)\cdot \varphi (n))\quad (m,n)=1\)
  • \(\varphi (pn)=p\cdot \varphi (n)\quad (p,\frac { n }{ p } )=1\)   (p为n的一个质因子)

我们先来证明一下第二点

\[\begin{align}\varphi (pn) &=\varphi ({ p }^{ 2 }\cdot \frac { n }{ p } )\\ &=\varphi ({ p }^{ 2 })\cdot \varphi (\frac { n }{ p } )\\ &=p\cdot (p-1)\cdot \varphi (\frac { n }{ p } )\\ &=p\cdot \varphi (p)\cdot \varphi (\frac { n }{ p } )\\ &=p\cdot \varphi (n)\end{align}\]

题目中中说明\(n\)是square-free number,即表明它的每种质因子最多只有一个,因此我们来统计每个质因子对\(k\)的贡献:

所求\(k=\sum_{i=1}^{m} \varphi (i*n)\)  可先将\(n\)分解质因子,对于每个质因子\(p\)来说,若\((i,p)=1\)则直接由第一条性质拆出来即可,若\(i=kp\),则由第二条性质,\(\varphi (kpn)=p\cdot \varphi (kn)\),因此对质因子p有

\[\begin{align}\sum _{ i=1 }^{ m }{ \varphi (i\cdot n) } { | }_{ p } &=\sum _{ i\%p\neq 0 }^{ i=1:m }{ \varphi (i\cdot \frac { n }{ p } )\cdot \varphi (p) } +\sum _{ i=kp }^{ i=1:m }{ \varphi (i\cdot n) } \\ &=\sum _{ i\%p\neq 0 }^{ i=1:m }{ \varphi (i\cdot \frac { n }{ p } )\cdot \varphi (p) } +\sum _{ k=1 }^{ m/p }{ \varphi (k\cdot p\cdot n) } \\ &=\sum _{ i\%p\neq 0 }^{ i=1:m }{ \varphi (i\cdot \frac { n }{ p } )\cdot \varphi (p) } +\sum _{ k=1 }^{ m/p }{ \varphi (k\cdot n)\cdot p } \\ &=\sum _{ i\%p\neq 0 }^{ i=1:m }{ \varphi (i\cdot \frac { n }{ p } )\cdot \varphi (p) } +\sum _{ k=1 }^{ m/p }{ \varphi (k\cdot n)\cdot (\varphi (p)+1) } \\ &=\sum _{ i\%p\neq 0 }^{ i=1:m }{ \varphi (i\cdot \frac { n }{ p } )\cdot \varphi (p) } +\sum _{ k=1 }^{ m/p }{ \varphi (k\cdot n)\cdot \varphi (p) } +\sum _{ k=1 }^{ m/p }{ \varphi (k\cdot n) } \\ &=\sum _{ i\%p\neq 0 }^{ i=1:m }{ \varphi (i\cdot \frac { n }{ p } )\cdot \varphi (p) } +\sum _{ i\%p=0 }^{ i=1:m }{ \varphi (\frac { i }{ p } \cdot n)\cdot \varphi (p) } +\sum _{ k=1 }^{ m/p }{ \varphi (k\cdot n) } \\ &=\sum _{ i=1 }^{ m }{ \varphi (i\cdot \frac { n }{ p } ) } +\sum _{ i=1 }^{ m/p }{ \varphi (i\cdot n) }  \end{align}\]

所以我们可以递归求出\(k\)

得到\(k\)后,最后的答案只需要降幂公式降幂即可,\(k\)的无穷次方终将在递归中降成\(\%1\)的状态

\[{ A }^{ B }\%C={ A }^{ B\%\varphi (C)+\varphi (C) }\%C\]

比赛中也是找了好多办法求k都没求出来,最后也是参照大牛的博客的方法才知道怎么求的k

代码:

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
#define LL long long
const int MOD=1e9+7;
const int N=1e7+7;
LL phi[N],sum[N],pri[N];
int top,tp;
LL fac[100];
LL n,m,p;
bool vis[N];

LL mul(LL a,LL b, LL c)
{
a%=c;
b%=c;
LL ret=0;
while(b){
if(b&1) (ret+=a)%=c;
(a<<=1)%=c;
b>>=1;
}
return ret;
}
LL pow(LL x,LL n,LL mod)
{
x%=mod;
if(n==1) return x;
LL tmp=x,ret=1;
while(n){
if(n&1) ret=mul(ret,tmp,mod);
tmp=mul(tmp,tmp,mod);
n>>=1;
}
if(ret==0) ret+=mod;
return ret;
}
void init()
{
memset(vis,0,sizeof(vis));
top=0;
phi[1]=1;
for(int i=2;i<N;i++){
if(!vis[i]) {
pri[top++]=i;
phi[i]=i-1;
}
for(int j=0;j<top&&i*pri[j]<N;j++){
vis[i*pri[j]]=1;
if(!(i%pri[j])){
phi[i*pri[j]]=phi[i]*pri[j];
break;
}else phi[i*pri[j]]=phi[i]*(pri[j]-1);
}
}
sum[0]=0;
for(int i=1;i<N;i++)
sum[i]=(sum[i-1]+phi[i])%MOD;
}
void getfac(LL n)
{
tp=0;
for(int i=0;i<top;i++){
LL p1=pri[i];
if(n%p1==0){
fac[tp++]=p1;
n/=p1;
}
if(!vis[n]){
fac[tp++]=n;
return;
}
}
}


LL sol(LL k,LL p,LL add)
{
if(p==1) return 1ll;
LL tmp=sol(k,phi[p],phi[p]);
return pow(k,tmp,p)+add;
}
LL calc(int i,LL n,LL m)
{
if(n==1) return sum[m];
if(m==0) return 0;
LL pp=fac[i];
LL k=((pp-1)*calc(i+1,n/pp,m)%MOD+calc(i,n,m/pp))%MOD;
return k;
}
int main(){
init();
while(~scanf("%lld%lld%lld",&n,&m,&p)){
getfac(n);
LL k=calc(0,n,m);
LL ans=sol(k,p,0);
printf("%lld\n",ans%p);
}
return 0;
}