自动搬运

查看原文

来自洛谷，原作者为

	良心WA题人 啦叭叭叭 啾啾啾啦叭叭叭

搬运于2025-08-24 22:39:10，当前版本为作者最后更新于2022-07-10 20:01:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

设 $f_n$ 表示答案，则显然 $f_n=\Sigma_{d|n}\phi_\frac{n}{d}\times d$

令 $g_x=x$，显然 $g_x$ 为积性函数。那么右半边就是 $f_x$ 与 $g_x$ 的迪利克雷卷积。又因为 $\phi_x$ 为积性函数，而根据积性函数的性质不难知道 $f_x$ 是积性函数。所以，$f_x$ 的值仅与 $f_{p^k}$ 有关。并且，不难推出来 $f_{p^k}=p^k+p^k\times(1-\dfrac{1}{p})\times k$。所以，我们只需要知道如何才能得到 $n$ 的因数 $p^k$。

我们可以询问 $gcd(p^\infty ,n)$。然后得到的值 $a$ 就是 $n$ 的因数 $p^k$。因为返回的值对$P$取模，所以，我们就得到了一个同余方程：$p^k \equiv a \pmod P$

那么，我们就可以用 $BSGS$ 求出第一个解。然后通解就知道了。将通解存到一个数组里，那么我们可以二分这个数组，找到数组中的 $k$，使返回值 $gcd(p^k,a)=a$ 且 $gcd(p^{k-1},a)\not=a$，那么这个 $p^k$ 就是 $n$ 的因子，计算答案即可。。。。？

注意到，这样做只能得到前三个 subtask 的分。输出一下每个解是膜多少的剩余类，发现所有的都大于 $10000$ 。所以在次数为 $0$ 到 $10000$ 的范围内只会有一个解。那么，直接用得到的解就行了。

std：

#include<bits/stdc++.h>
using namespace std;
const int NN=1004,P=998244353;
int prime[NN],vis[NN*100];
int qmi(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=1ll*res*a%P;
		a=1ll*a*a%P;
		b>>=1;
	}
	return res;
}
int bsgs(int a,int b)
{
	if(1%P==b%P)
		return 0;
	unordered_map<int,int>hash;
	int k=sqrt(P)+1;
	for(int i=0,j=b%P;i<k;i++)
	{
		hash[j]=i;
		j=1ll*j*a%P;
	}
	int ak=1;
	for(int i=1;i<=k;i++)
		ak=1ll*ak*a%P;
	for(int i=1,j=ak;i<=k;i++)
	{
		if(hash.count(j))
			return i*k-hash[j];
		j=1ll*j*ak%P;
	}
	return -1;
}
int main()
{
	vis[1]=true;
	int cnt=0;
	for(int i=2;cnt<=1000;i++)
		if(!vis[i])
		{
			prime[++cnt]=i;
			for(int j=i*i;j<=1e5;j+=i)
				vis[j]=true;
		}
	int ans=1;
	for(int i=1;i<=cnt;i++)
	{
		printf("GetGCD. 1 %d 1000000\n",prime[i]);
		fflush(stdout);
		int k;
		scanf("%d",&k);
		int t=bsgs(prime[i],k);
		ans=1ll*ans*((k+1ll*k*(prime[i]-1)%P*qmi(prime[i],P-2)%P*t%P)%P)%P;
	}
	printf("IFoundTheAnswer! %d",ans);
	return 0;
}