题目传送门
分析：
吓得我赶紧去复习了一下polya
这里有两种置换，一种是位置置换(2n)种，一种是颜色置换(m)种
组合起来就有(2nm)种
先考虑平移变色这(nm)种变换
假设一个方案变色(g)次，平移(d)次与之前相等的方案数
中途关联的(frac{n}{gcd(d,n)})个位置，颜色要变回来至少要(frac{m}{gcd(g,m)})次
这里要满足(frac{m}{gcd(g,m)}|frac{n}{gcd(d,n)})
我们列出式子开始推：
(~~~~sum_{d=1}^{n}m^{gcd(d,n)}sum_{g=1}^{m}[frac{m}{gcd(g,m)}|frac{n}{gcd(d,n)}])
(=sum_{d|n}varphi(d)m^{frac{n}{d}}sum_{g|m}varphi(g)[g|d])
(=sum_{d|n}varphi(d)m^{frac{n}{d}}sum_{g|gcd(m,d)}varphi(g))
(=sum_{d|n}varphi(d)m^{frac{n}{d}}gcd(m,d))
最终这个式子就可以(O(sqrt n))求了
(n)有点大，使用Pollard_Rho分解质因数，dfs枚举所有因数及其欧拉函数
接下来是反转变色的(nm)种变换
(n)为奇数时，处于对称轴上的点不能变颜色，于是不存在颜色变换
方案数为(nm^{frac{n+1}{2}})
(n)为偶数时，如果穿过对称轴的是两个点，那么也不存在颜色交换
方案数为(nm^{frac{n}{2}+1})
如果不穿过点，那么颜色变换可以为(gcd(2,m))种，即考虑(m)的奇偶性
方案数为(gcd(m,2)nm^{frac{n}{2}})
加在一起除以(2nm)就好了
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
#include<ctime>
#include<set>
#define maxn 200005
#define INF 0x3f3f3f3f
#define MOD 998244353
#define eps 1e-8
using namespace std;
inline long long getint()
{
long long num=0,flag=1;char c;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();
return num*flag;
}
long long n,m,ans;
map<long long,int>M;
vector<pair<long long,int> >D;
int cnt=10,pri[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};
inline long long gcd(long long p,long long q)
{return q?gcd(q,p%q):p;}
inline long long mul(long long a,long long b,long long p)
{return (a*b-(long long)((long double)a/p*b+eps)*p+p)%p;}
inline long long ksm(long long num,long long k,long long P=998244353)
{
long long ret=1;
for(;k;k>>=1,num=mul(num,num,P))if(k&1)ret=mul(ret,num,P);
return ret;
}
inline void dfs(int x,long long nw,long long phi)
{
if(x==D.size())
{ans=(ans+(gcd(m,nw)%MOD)*ksm((m%MOD),(n/nw)%(MOD-1))%MOD*(phi%MOD)%MOD)%MOD;return;}
dfs(x+1,nw,phi),nw*=D[x].first,phi*=D[x].first-1,dfs(x+1,nw,phi);
for(int i=2;i<=D[x].second;i++)nw*=D[x].first,phi*=D[x].first,dfs(x+1,nw,phi);
}
inline long long F(long long t,long long x,long long c)
{return (mul(t,t,x)+c)%x;}
inline bool Miller_Rabin(long long x)
{
if(x==2)return 1;
if(x==1||!(x&1))return 0;
long long k=x-1,t=0;
while(!(k&1))t++,k>>=1;
for(int i=0;i<cnt&&pri[i]<x;i++)
{
long long g=ksm(pri[i],k,x);
for(int j=0;j<t;j++)
{
long long g0=mul(g,g,x);
if(g0==1&&g!=1&&g!=x-1)return 0;
g=g0;
}
if(g!=1)return 0;
}
return 1;
}
inline void Pollard_Rho(long long x)
{
if(Miller_Rabin(x)){M[x]++;return;}
while(1)
{
long long c=rand()%(x-1)+1,p=rand()%x,q=F(p,x,c);
while(p!=q)
{
long long d=gcd(x,abs(p-q));
if(d!=1){Pollard_Rho(d),Pollard_Rho(x/d);return;}
p=F(p,x,c);q=F(F(q,x,c),x,c);
}
}
}
int main()
{
srand(114514);
int T=getint();
while(T--)
{
M.clear(),ans=0,D.clear();
n=getint(),m=getint();
Pollard_Rho(n);
for(map<long long,int>::iterator it=M.begin();it!=M.end();it++)D.push_back(*it);
dfs(0,1,1);
if(n&1)ans=(ans+(n%MOD)*ksm(m%MOD,((n+1)/2)%(MOD-1))%MOD)%MOD;
else
{
ans=(ans+(n/2)%MOD*ksm(m%MOD,(n/2)%(MOD-1))%MOD*gcd(2,m)%MOD)%MOD;
ans=(ans+(n/2)%MOD*ksm(m%MOD,(n/2+1)%(MOD-1))%MOD)%MOD;
}
printf("%lld
",ans*ksm(2*(n%MOD)*(m%MOD)%MOD,MOD-2)%MOD);
}
}
