Kattis anothercoinweighingpuzzle Another Coin Weighing Puzzle

Link
我们让每个包对应一个长度为(m)的的序列({a})，其中(a_iin[-k,k])表示在第(i)次称的时候这一包硬币放了多少个（如果放在左边的话(a_i>0)，放在右边的话(a_i<0)）。
最后将称重结果序列约分即可找到假币包，因此答案就是合法的序列数。
此处的合法指的是序列元素全为(0)或所有元素的(gcd)为(1)。
因为若存在一个序列每个元素都是另一个序列的(x)倍，且这两个包中有一个是假币包，那么我们无法区分这两个包。
考虑如何计算合法序列数，先忽略全(0)序列。
设(f_i)表示元素(gcd)为(i)的序列数，这看上去不太好算。
设(g_i)表示元素都为(i)的倍数的非全零序列数，那么(g_i=(2lfloorfrac ki floor+1)^m-1)。
(g_d=sumlimits_{d|t}f_tLeftrightarrow f_d=sumlimits_{d|t}g(t)mu(frac td))
那么(f_1=sumlimits_{i=1}^nmu(i)g_i)，注意到不同的(g_i)只有(sqrt k)种，那么记忆化(g)并线性筛(mu)可以做到(O(k+sqrt klog m))的时间复杂度。

#include<cstdio>
const int N=2000007,P=998244353;
int pow(int a,int k){int r=1;for(;k;k>>=1,a=1ll*a*a%P)if(k&1)r=1ll*a*r%P;return r;}
int mu[N],pr[N],is[N],pw[N];
int main()
{
    int m,k,tot=0,ans=mu[1]=1;scanf("%d%d",&m,&k);
    for(int i=2;i<=k;++i)
    {
	if(!is[i]) mu[i]=-1,pr[++tot]=i;
	for(int j=1;pr[j]*i<=k;mu[i*pr[j++]]=-mu[i]) if(is[i*pr[j]]=1,!(i%pr[j])) break;
    }
    for(int i=1,x;i<=k;++i) x=k/i*2+1,(ans+=mu[i]*(pw[x]? pw[x]:pw[x]=pow(x,m))-mu[i])%=P;
    printf("%d",(ans+P)%P);
}