「SDOI2018」反回文串
题目描述
“回文串什么的最讨厌了……”
小 Q 讨厌任何形式的回文串：
- 如果一个字符串从左往右读和从右往左读是一样的，那么小 Q 讨厌它；例如
和 ```aba``` 。 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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
2. 对于一个字符串来说，若将某个前缀子串移除并拼接到字符串的尾部，能得到一个小 Q 讨厌的字符串，那么小 Q 也会讨厌原来的这个字符串；例如 ```aab``` 和 ```baa``` 。
现在问题来了，如果任意字符串只可以由 $k$ 种已知的字符组成（也就是说字符集的大小为 $k$），那么长度为 $n$ 的所有字符串里，有多少字符串是小 Q 讨厌的？
答案可能很大，你只需要给出答案对 $p$ 取模后的值。
**输入格式**
第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。
接下来 $T$ 行，每行描述一组测试数据，包含三个正整数 $n$, $k$ 和 $p$。
**输出格式**
对于每组测试数据，输出一行，包含一个整数，表示答案对 $p$ 取模的值。
**数据范围与提示**
对于 $30\%$ 的数据，有 $1 \leq n \leq 10^{10}$。
对于 $60\%$ 的数据，有 $1 \leq n \leq 10^{14}$。
对于 $100\%$ 的数据，有 $1 \leq T \leq 10, 1 \leq n \leq 10^{18}, 1 \leq k \leq n, 10^9 \leq p \leq 2^{30}$。
---
skywalkert的题解比较可读，只是最后一页有点小问题：$\sum_{d|n}\mu(d)d=\prod_{p|n,p \ is\ prime}(1-p)$，后面是乘积而不是求和。
关于这个的证明：注意到$\mu,Id$都是积性的，因此相乘也是积性的；而左边实际上是一个狄利克雷卷积的形式，因此整个左边的式子也应该是一个关于$n$的积性函数。积性函数就可以把$n$标准分解之后再把$f(p_1^{k_1}),f(p_2^{k_2}),...$乘起来。由于$\mu$的性质，对于$k>0$，自变量取$p^k$时，答案都会是$1-p$。所以就有了上面这个式子。
对于得到答案式子部分，我只知道最小循环节一定是一个回文串，这个画画图就知道了。
不知道的就麻烦大家指教了：
1.最小循环节长度如果是偶数，为什么就只有一种移位方式得到新的回文串。
2.题解里奇数时的矛盾我没有推出来。
最后就说一下下面这个式子在$d$为奇，$\frac{n}{d}$为偶的时候为什么是0吧：
$$
\sum_{d'|\frac{n}{d}}\mu(d')h(dd'),h(d)=d\frac{1}{1+[d \ is \ even]}
$$
由于$\frac{n}{d}$是偶数，所以对于每一个奇数的$d'|\frac{n}{d}$,都有$2d'|\frac{n}{d}$。所以考虑对于每一个奇数找到它的两倍与它配对，配对之后加起来是0：
$$
\mu(d)h(dd')+\mu(2d)h(2dd')=\mu(d)dd'-\mu(d)dd'=0
$$
如果还有没有讨论到的$\frac{n}{d}$的约数，那么一定是$2^ab(a>1,b\ is \ odd)$的形式。由于含有平方因子，$\mu$的值是0，所以剩下的部分加起来还是0，进而整个式子的值是0。
数据范围极大，注意乘法可能爆long long。
---
```c++
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#define ll long long
using namespace std;
const ll P[]={2,3,5,7,11};
ll N,mod,K,fac[205],Ans;
ll pfac[205];int cs[205],tot;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll add(ll a,ll b){
if(a>=mod)a%=mod;
if(b>=mod)b%=mod;
a+=b;a-=a<mod?0:mod;
return a;
}
ll sub(ll a,ll b){
if(a>=mod)a%=mod;
if(b>=mod)b%=mod;
a-=b;a+=a<0?mod:0;
return a;
}
ll mul(ll a,ll b,ll c){
return (a*b-(ll)((long double)a*b/c)*c+c)%c;
}
ll ksm(ll a,ll b,ll c){
ll ans=1;a%=c;
while(b){
if(b&1)ans=mul(ans,a,c);
b>>=1;a=mul(a,a,c);
}
return ans;
}
bool Miller_Rabin(ll x){
if(x==1)return false;
if(~x&1)return x==2;
int i,j,m=0;
ll p,pre,t=x-1;
while(~t&1)t>>=1,m++;
for(i=0;i<5;i++){
p=P[i];
if(x%p==0)return x==p;
p=ksm(p,t,x);
if(p==1)continue;
for(j=1;j<=m;j++){
pre=p;
p=mul(p,p,x);
if(p==1){
if(pre!=1&&pre!=x-1)return false;
break;
}
}
if(p!=1)return false;
}
return true;
}
void Pollard_Rho(ll n,ll A[]){
if(Miller_Rabin(n)){A[++A[0]]=n;return;}
ll a,b,c,t;
int i,k;
if(~n&1){
A[++A[0]]=2;
Pollard_Rho(n>>1,A);
return;
}
while(1){
a=b=1ll*rand()*rand()%n;
c=1ll*rand()*rand()%n;
i=1;k=2;
while(1){
i++;
b=(mul(b,b,n)+c)%n;
if(a==b)break;
if(a>b)t=gcd(n,a-b);
else t=gcd(n,b-a);
if(t!=1){
Pollard_Rho(t,A);
Pollard_Rho(n/t,A);
return;
}
if(i==k)k<<=1,a=b;
}
}
}
ll funcg(ll n){
return ksm(K,n+1>>1,mod);
}
ll funcf(ll n){
if(n&1)return n%mod;
return (n>>1)%mod;
}
void dfs(int cur,ll d,ll tmp){
int i;
ll t,nextmp;
if(cur==tot+1){
if(((N/d)&1)&&(~d&1))return;
t=mul(tmp,mul(funcf(N/d),funcg(N/d),mod),mod);
Ans=add(Ans,t);
return;
}
for(i=0,t=1;i<=cs[cur];i++){
if(i)nextmp=mul(tmp,sub(1,pfac[cur]),mod);
else nextmp=tmp;
dfs(cur+1,d*t,nextmp);
t*=pfac[cur];
}
}
void solve(){
int i,j;
scanf("%lld%lld%lld",&N,&K,&mod);
if(N==1){printf("%lld\n",K%mod);return;}
fac[0]=0;
tot=0;
Pollard_Rho(N,fac);
sort(fac+1,fac+fac[0]+1);
for(i=1;i<=fac[0];i=j+1){
for(j=i+1;j<=fac[0]&&fac[i]==fac[j];j++);j--;
tot++;
cs[tot]=j-i+1;
pfac[tot]=fac[i];
}
Ans=0;
dfs(1,1,1);
printf("%lld\n",Ans);
}
int main(){
srand(19260817);
int T;scanf("%d",&T);
while(T--)solve();
}