自动搬运

查看原文

来自洛谷，原作者为

	Soulist 再见了

搬运于2025-08-24 22:01:53，当前版本为作者最后更新于2020-04-29 22:06:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这道题很有意思，需要你进行大量的手玩来推结论

• 结论$1$：一个字符串 A 的不同的轮换的数量为 $|\sigma(A)|$，其中 $\sigma(S)$ 表示 S 的最小循环节。

这个结论比较基础/fad

• 结论$2$：一个回文串的最小循环节 $\sigma(S)$ 必然也是一个回文串。

证明的话可以手玩。

• 结论$3$：一个长度为 $n$ 的字符串可以被一个最小循环节唯一表示，同时这个循环节也会唯一表示一个长度为 $n$ 的字符串。

这个结论也非常显然。

不过我们可以开始转变思路了，我们尝试对 $\sigma$ 进行计数，根据结论 $1$ 一个 $\sigma$ 可以衍生出来的本质不同的字符串的数量为 $|\sigma|$

所以我们猜想答案是：$\sum |\sigma|$

很快你就会意识到不对，我们发现比如字符串 abbaabba 他在一定的循环之后会变成 baabbaab 我们统计 $\sigma$ 的时候会将 abba 与 baab 都一起算一遍。

我们接着又可以发现这几个结论：

• 结论$4$：如果一个合法的循环节 $\sigma$ 的长度为偶数，那么至少存在另一个 $\sigma$ 与之对应。

证明的话手玩，大概就是把 $\sigma$ 分解为 $s1+s2$，那么 $s1\ne s2,s1=rev(s2)$，那么一定存在另一个循环节为 $s2+s1$ 可以通过轮换得到一样的结果。

• 结论$5$：在结论 $4$ 的基础上，每个长度为偶数的合法最小循环节 $\sigma$ 都有且仅有一个 $\zeta$ 与之对应，即 $4$ 的证明下面补充的例子。

这个结论就需要手玩了，画一个图，然后假设一个位移 $k$ 使得其回文，最后会推导出来 $\sigma$ 是存在循环节的之类的，比较感性...不过直觉上这个结论挺对的。

• 结论$6$：类比结论 $5$，如果一个回文最小循环节 $\sigma$ 为奇数，那么其不存在任意一个与之对应 $\zeta$ 使之回文。

这个结论的手玩方式和 $5$ 类似。

• 结论 $7$：约数个数函数的增长十分缓慢，对于 $n\le 10^{18}$，有 $\max\{d(n)\}=103680$

我们发现结论 $6$ 十分的优美，他意味着如果一个回文循环节的长度为奇数，那么其对于答案的贡献就是 $|\sigma|$

而结论 $5$ 则让我们意识到对于长度为偶数的回文循环节，其总是两两配对的，所以单独一者的贡献可以直接视为 $\frac{|\sigma|}{2}$

结论 $7$ 则告诉我们，复杂度为 $O(d(n))$（$d(x)$ 表示 $x$ 的约数个数）的算法是可以通过这道题的。

现在我们可以开始计数了，令 $f(d)$ 表示最小循环节长度为 $d$ 的循环节数量，那么我们知道答案就是：

$$\sum_{d|n}f(d)\times \frac{d}{1+r(d)}$$

其中 $r(d)$ 表示 "[$d$ 为偶数]"，我们发现 $f(d)$ 不好求，但是我们不妨设 $F(x)$ 为长度为 $x$ 的回文串的数量，那么有：

$$\sum_{d|x}f(d)=F(x)$$

可以直接当作用了一次结论$2$，虽然也比较显然

我们知道 $F(x)=m^{\lceil\frac{x}{2}\rceil}$，于是我们可以通过莫比乌斯反演得到 $f$

于是有：

$$f(d)=\sum_{x|d}F(x)\times \mu(\frac{d}{x})$$

于是我们知道：

$$Ans=\sum_{d|n} \dfrac{d}{1+r(d)}\sum_{x|d}\mu(\frac{d}{x})F(x) $$

令 $g(d)=\frac{d}{1+r(d)}$，则有：

$$Ans=\sum_{d|n}\sum_{x|d}\mu(\frac{d}{x})F(x)g(d)$$ $$Ans=\sum_{x|n}F(x)\sum_{k|\frac{n}{x}}\mu(k)g(kx)$$

到目前为止，如果我们能够做到 $O(d(n))$ 的枚举约数那么本题已经可以得到部分分了。

我们肯定希望有一种玄幻的操作可以将 $g(kx)$ 分解出来，让后面变成之和 $\frac{n}{x}$ 有关的一个函数。

假设将 $k$ 从 $g(kx)$ 中提取出来变成 $kg(x)$，那么此时 $kg(x)\ne g(kx)$ 当且仅当 $x$ 为奇数，$k$ 为偶数。

由于 $k|\frac{n}{x}$，于是 $\frac{n}{x}$ 为偶数，我们现在来考虑这个式子的取值：

$$\sum_{k|\frac{n}{x}}\mu(k)g(kx)$$

通过打表可以发现这个式子的值恒定为 $0$

我们理性分析一下，这个式子的前提为 $\frac{n}{x}$ 为偶数，$x$ 为奇数，所以对于答案有贡献的 $\mu(k)$ 都满足 $\mu(k)\ne 0$，我们对于 $\frac{n}{x}$ 进行质因数分解，现在只关注 $\mu(k)\ne 0$ 的 $k$，我们发现每一个不含 $2$ 作为因数的 $k$ 都存在一个 $\mu(2k)$ 与之对应，且其值恰好相反，而且 $g(kx),g(2kx)$ 是相同的，所以这两个值会在一起抵消，所以这一部分对于答案的贡献为 $0$。

由于我们不关注 $0$ 的取值，我们可以忽略这一类，对于剩下的情况，有答案为：

$$\sum_{x|n}F(x)g(x)\sum_{k|\frac{n}{x}}\mu(k)k$$

如果能够 $O(1)$ 的求出后面的式子的值，那么我们就可以得到一个 $O(d(n))$ 的解法了，现在考虑：

$$\sum_{k|n}\mu(k)k$$

的取值，我们仍然只考虑 $\mu(k)\ne 0$ 的数，那么此时我们可以将一个 $k$ 视为 $p_1p_2...p_m$

考虑一个 dp 的思想来统计答案，每次新增一个质因数 $p'$ 进入集合的时候，显然答案有两类，一类是不选入 $p'$ 一类是选入 $p'$，选入 $p '$ 的同时会使得所有贡献都乘以 $(-1)$，令 $f_i$ 表示之前的答案，则有 $f_i'=(f_i-p'f_i)$，我们把每一项的贡献单独提取出来，则可以得到上式为：

$$\sum_{k|n}\mu(k)k=\prod(1-p_i)$$

我们先通过 Pollard−Rho 将 $n$ 进行质因数分解，然后通过质因数来进行搜索，做到 $O(d(n))$ 枚举所有约数，对于 $x$ 为奇数而 $\frac{n}{x}$ 为偶数的情况忽略，然后沿途统计一下 $\prod(1-p_i)$ 即可。

值得注意的是被统计的 $\prod (1-p_i)$ 是补集的。

复杂度 $O(T\times (d(n)\log n+n^{1/4}\log n))$

$Code:$

#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int __int128
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 10000 + 5 ; 
int T, n, m, P, st[N], top, w[N], num, c[N] ; 
int mul( int a, int b, int p ) {
	return ( a % p ) * ( b % p ) % p ;  
}
int fpow( int x, int k, int p ) {
	int ans = 1, base = x % p ; 
	while( k ) {
		if( k & 1 ) ans = mul( ans, base, p ) ;
		base = mul( base, base, p ), k >>= 1 ; 
	} return ans % p ; 
}
bool M_R( int p ) {
	if( p == 2 || p == 3 ) return 1 ; 
	if( p == 1 || ( p % 2 == 0 ) ) return 0 ; 
	re int d = p - 1, s = 0 ; while( !( d & 1 ) ) ++ s, d >>= 1 ; 
	rep( i, 0, 5 ) {
		re int a = rand() % ( p - 3 ) + 2 ; 
		re int x = fpow( a, d, p ), y = 0 ;
		for( register int j = 0; j < s; ++ j ) {
			y = mul( x, x, p ) ; if( y == 1 && ( x != 1 ) && x != ( p - 1 ) ) return 0 ;
			x = y ;
		} if( y != 1 ) return 0 ;
	} return 1 ; 
}
int gcd( int x, int y ) {
	return ( x == 0 ) ? y : gcd( y % x, x ) ;
}
int Rand( int x ) {
	return 1ll * ((rand() << 15 ^ rand()) << 30 ^ (rand() << 15 ^ rand())) % x ; //2
}
int work( int p ) {
	re int k = 2, x = Rand(p - 1) + 1, y = x, d = 1, c = Rand(p) % 999997 ;
	for( re int i = 1; d == 1; ++ i ) {
		x = ( mul( x, x, p ) + c ) % p ;
		d = gcd( (x > y) ? x - y : y - x, p ) ;
		if( i == k ) y = x, k <<= 1 ; 
	} return d ; 
}
void Pollard_Rho(int p) {
	if( p == 1 ) return ; 
	if( M_R(p) ) { st[++ top] = p; return ; }
	int x = p ; while( x == p ) x = work(x) ;
	Pollard_Rho(x), Pollard_Rho(p / x) ;
}
int Ans = 0 ;
void dfs( int x, int f, int d, int p ) {
	if( x == num + 1 ) {
		if( ( (d & 1) ) && ( !( (n / d) & 1 ) ) ) return ;
		int g = ( d & 1 ) ? d : d / 2 ;
		Ans = ( Ans + mul( mul( fpow( m, ( d + 1 ) / 2, p ), g, p ), (f + p) % p, p ) + p ) % p ;
		return ; 
	}
	int fd = 1 ; 
	rep( i, 0, c[x] ) {
		if( i == c[x] ) dfs( x + 1, f, d * fd, p ) ;
		else dfs( x + 1, f * ( 1 - w[x] ), d * fd, p ) ;
		fd = fd * w[x] ; 
	}
}
signed main()
{
	srand(time(NULL)) ; 
	T = gi() ; 
	while( T-- ) {
		n = gi(), m = gi(), P = gi(), top = 0, num = 0, Ans = 0 ;
		memset( c, 0, sizeof(c) ), memset( w, 0, sizeof(w) ), memset( st, 0, sizeof(st) ) ;
		Pollard_Rho(n) ; 
		sort( st + 1, st + top + 1 ) ;
		rep( i, 1, top ) {
			if( st[i] == st[i - 1] ) ++ c[num] ; 
			else w[++ num] = st[i], c[num] = 1 ; 
		}
		dfs( 1, 1, 1, P ) ;
		printf("%lld\n", (long long)((Ans) % P) ) ;
	}
	return 0 ;
}