自动搬运

查看原文

来自洛谷，原作者为

	usermin 一个蒟蒻

搬运于2025-08-24 22:53:03，当前版本为作者最后更新于2023-12-31 16:48:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目描述

给出一个函数 $f(d)$，给出 $g(n)=\sum\limits_{d|n}f(d)$ 其中 $k$ 项 $\bmod$ $998244353$ 的值，对于每个测试点，有 $t$ 组数据，对于每一组数据，给出 $d$，求 $f(d)\bmod998244353$ 的值。

Sub0

基础结论，$g(n)=[n=1]$，$f(n)=\sum\limits_{d|n}μ(d)g(\tfrac{n}{d})=μ(n)$。

核心代码：

for(long long i=2;i*i<=n;i++)
{
	if(n%i==0)
	{
		n/=i;
		if(n%i==0)
		{
			ans=0;
		}
		else 
		{
			ans*=-1;
		}
	}
}
if(n>1)
{
	ans*=-1;
}

Sub1

一眼丁真，$g(n)=d(n)$，$f(n)=\sum\limits_{d|n}μ(d)d(\tfrac{n}{d})=1$。

核心代码：

cout<<1<<endl;

Sub2

$g(1)=0$，反演后因为 $g(1)=f(1)$，所以 $f(1)=0$，$f(n)=f(1) \times f(n)=0$。

核心代码：

cout<<0<<endl;

Sub3

最抽象的一集，发现 $g(p^k)$ 是一个随机数，反演可得 $f(n)=g(n)=\sum\limits_{d\neq n,d|n}f(d)$。

核心代码：

for(long long i=1;i<=P;i++)
{
	f[i]=y[i];//y为g(d)
}	
for(long long i=1;i<=100000;i++)
{
	for(long long j=i+i;j<=100000;j+=i)
	{
		f[j]=(f[j]-f[i]+mod)%mod;	
	}	
}

Sub4

有些难度，反演两次后，设这个奇怪的反演函数为 $j$，发现是一个平方数，即 $j(p)=(p-1)^2$，得 $j(n)=\prod(j(p^k))=\prod(p^{k-1}(p-1))^2=\varphi^2(n)$，所以 $f(n)=\sum\limits\limits_{d|n}j(d)=\sum\limits_{d|n}\varphi^2(d)$。

核心代码：

for(long long i=1;i*i<=n;i++)
{
	long long res;
	if(n%i==0)
	{
		res=phi(i);//phi部分自写
		ans=(ans+1ll*res*res)%mod;
		res=phi(n/i);
		ans=(ans+1ll*res*res)%mod;
	}
	if(i*i==n)
	{
		res=phi(i);
		ans=(ans-1ll*res*res)%mod;
	}
}

Sub5

简单一次反演后，得 $f(p^k)=p^{2k-1}$，套下数据发现大质数相乘，输出 $n$。

核心代码：

cout<<n<<endl;

Sub6

最困难的一集，我们已知 $g(n)=n^2$，则 $f(p^k)=\sum\limits_{d|p^k}d^2μ(\tfrac{p^k}{d})$，因为 $p^0,p^1,p^2$ 等整除 $p^k$，且根据 $μ$ 的定义，可知只有为 $k-1,k$ 时对总答案有贡献，所以 $f(p^k)=p^{2k}-p^{2k-2}=p^{2k}(1-\tfrac{1}{p^2})$，得 $f(n)=\prod p^{2k}(1-\tfrac{1}{p^2})=n^2\prod (1-\tfrac{1}{p^2})$。

核心代码：

long long mill[20]={0,2,325,9375,28178,450775,9780504,1795365022};
bool miller(long long n)
{
	if(n<3)
	{
		return (n==2);
	}
	long long u=n-1,t=0;
	while(u%2==0)
	{
		u>>=1,t++;
	}
	for(long long i=1;i<=7;i++)
	{
		if(mill[i]>n)
		{
			continue;
		}
		long long a=mill[i],v=pow(a,u,n),j;
		if(v==1)
		{
			continue;	
		}
		j=1;
		for(;j<=t;j++)
		{
			if(v==n-1)
			{
				break;
			}
			v=(__int128)v*v%n;
		}
		if(j==t+1)
		{
			return 0;
		}
	}
	return 1;
}
long long f2(long long x,long long c,long long n)
{
	return ((__int128)x*x+c)%n;//个人习惯
}
long long pollard(long long n)
{
	if(n==4)
	{
		return 2;
	}
	while(1)
	{
		long long c=rnd()%(n-1)+1,t=0,r=0,p=1,q,d;
		do
		{
			for(long long i=0;i<128;i++)
			{
				t=f2(t,c,n);
				r=f2(f2(r,c,n),c,n);
				if(t==r)
				{
					break;	
				}
				q=(__int128)p*abs(t-r)%n;
				if(q==0)
				{
					break;
				}
				p=q;
			}
			d=__gcd(p,n);
			if(d>1)
			{
				return d;
			}
		}while(t!=r);
	}
}
long long get(long long n)
{
	if(mp[n])
	{
		return mp[n];
	}
	if(miller(n))
	{
		return mp[n]=n;
	}
	long long k=pollard(n);
	return mp[n]=((k==n)?n:mp[n]=max(get(k),get(n/k)));
}
void ans7()
{
	while(T--)
	{
		long long n;
		cin>>n;
		__int128 ans=(__int128)n*n;
		while(n>1)
		{
			long long p=get(n);
			ans=ans/((__int128)p*p)*((__int128)p*p-1);
			while(n%p==0)
			{
				n/=p;
			}	
		}
		cout<<(long long)(ans%mod)<<endl;
	}
}

Pollard-rho 算法求质因数请转场 P4718。

Sub7

看看数据，动了亿点脑子，得 $f(p^k)=ap^{3k}+bp^{2k}+cp^k+d$，运用拉格朗日插值，脑量不足，只得 $a=114$，运用人类智慧，得 $a=114,b=514,c=1919,d=810$。

核心代码：

for(long long i=2;i*i<=n;i++)
{
	if(n%i==0)
	{
		long long k=1;
		while(n%i==0)
		{
			n/=i,k*=i;
		}
		if(k>1)
		{
			po=114;
			po=(po*k+514)%mod;
			po=(po*k+1919)%mod;
			po=(po*k+810)%mod;
			ans=ans*po%mod;
		}
	}
}
if(n>1)
{
	po=114;
	po=(po*n+514)%mod;
	po=(po*n+1919)%mod;
	po=(po*n+810)%mod;
	ans=ans*po%mod;
}

Sub8

看数据发的，猜测 $f(n)=n^2\bmod3$，正确！

核心代码：

cout<<1ll*n*n%3<<endl;

总结，非常好莫比乌斯反演，下次别出了。