【SDOI2018】反回文串
莫比乌斯反演，Pollard_Rho。
题目大意：
给定 $n,k,p$，问有多少个长度为 $n$ 的，字符集大小为 $k$ 的字符串，它是由一个回文串将一个前缀放到后面形成的。答案对 $p$ 取模。
题解：
如果一个回文串由一个子串循环多次得到，那么这个回文串能产生的串就会出现重复。这个子串也一定是个回文串。
具体地，长度为 $n$ 的串由长度为 $m$ 的子串重复得到，则只会产生 $m$ 个本质不同的字符串。
特别地，若 $m$ 为偶数，则循环位移 $\frac m 2$ 位后，会得到另外一个长度为 $n$ 的子串。所以如果 $m$ 为偶数，则只能产生 $\frac m2$ 个本质不同的字符串。
令 $f(m)$ 表示长度为 $n$ 的存在长度为 $m$ 的循环节的回文串个数。$f(m)=k^{\lceil\frac m 2\rceil}$。
令 $g(m)$ 表示长度为 $n$ 的最小循环节为 $m$ 的回文串个数。
可以推出：
莫比乌斯反演得：
令 $h(n)=\frac{n}{1+[n\bmod 2=0]}$。
则：
考虑 $\sum\limits_{m|\frac n d}\mu(m)h(d\cdot m)$。
我们希望它变为：
我们发现，只有当 $d$ 为奇数且 $m$ 为偶数时，$h(d\cdot m)\neq m\cdot h(d)$。
所以 $\frac n d$ 是偶数。
那么后面的式子中，$\mu(m)h(d\cdot m)$ 和 $\mu(2m)h(2\cdot d \cdot m)$（$m$ 为奇数）时互为相反数，而当 $m\bmod 4=0$ 时，有$\mu(m)=0$。所以当 $\frac n d$ 为偶数且 $d$ 为奇数时，对答案的贡献为 $0$。
那么：
我们考虑 $\sum\limits_{d|n}\mu(d)\cdot d$ 怎么求。
这个式子相当于把 $d$ 的所有最高次数为 $1$ 的因数拿出来，乘上 $-1$ 的质因子个数次方后加起来。也就是说，
我们用 Pollard_Rho 分解质因数后，进行 dfs，枚举 $\frac n d$ 的值，则后半部分可以在 dfs 中计算出来。
时间复杂度 $O(T(\sqrt{\sqrt n}+d(n)\log n))$。
Code：
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<algorithm>
#include<ctime>
using namespace std;
typedef long long LL;
int T;
LL n,k;int md,ans;
inline LL mul(LL a,LL b,const LL&md){
LL c=a*b-LL((long double)a*b/md+.5)*md;
return(c>>63&md)+c;
}
inline int intpow(int a,LL b){
int ret=1;for(;b;b>>=1,a=(LL)a*a%md)if(b&1)ret=(LL)ret*a%md;return ret;
}
inline LL pow(LL a,LL b,const LL&md){
LL ret=1;for(a%=md;b;b>>=1,a=mul(a,a,md))if(b&1)ret=mul(ret,a,md);return ret;
}
namespace MR{
const int P[]={2,3,5,7,11,13,17,19,23,29,31,37};
bool check(int a,LL n){
LL x=n-1;int d=0;
while(!(x&1))x>>=1,++d;
for(x=pow(a,x,n);d--;){
const LL lst=x;x=mul(x,x,n);
if(x==1&&lst!=1&&lst!=n-1)return 0;
}
return x==1;
}
bool test(LL n){
if(n==1)return 0;
for(int i:P)if(n==i)return 1;
if(!(n&1))return 0;
for(int i:P)if(!check(i,n))return 0;
return 1;
}
}
vector<LL>v;
LL find(LL n,int c){
LL x=rand()%(n-1)+1,y=x,k=2,q=1,t=1;
for(;;k<<=1,y=x,q=1){
for(int i=1;i<=k;++i){
x=mul(x,x,n)+c-n;x+=x>>63&n;
q=mul(q,llabs(x-y),n);
if(!(i&127)){
t=std::__gcd(q,n);
if(t>1)return t;
}
t=std::__gcd(q,n);
if(t>1)return t;
}
}
}
void rho(LL n){
if(n==1)return;
if(MR::test(n))return v.push_back(n);
LL p=n;int c=19260817;
while(p==n)p=find(p,c--);
while(n%p==0)n/=p;
rho(p),rho(n);
}
void dfs(int nw,LL t,int mx){
if(nw==v.size()){
if(t%2==0&&n/t%2==1)return;
t=n/t;
ans=(ans+intpow(k%md,t+1>>1)*((t%2==0?t/2:t)%md)%md*mx)%md;
}else
for(LL x=1;x<=n&&n%x==0;x=(x<=n/v[nw])?x*v[nw]:n+1)
dfs(nw+1,t*x,(x==1)?mx:(mx*(md+1-v[nw]%md)%md));
}
int main(){
srand(time(0));
for(scanf("%d",&T);T--;){
scanf("%lld%lld%d",&n,&k,&md),ans=0,v.clear();
rho(n),sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end());
dfs(0,1,1),printf("%d\n",ans);
}
return 0;
}