P9920 题解
usermin
·
·
题解
题目描述
给出一个函数 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
核心代码：
```cpp
cout<<0<<endl;
```
### Sub3
最抽象的一集，发现 $g(p^k)$ 是一个随机数，反演可得 $f(n)=g(n)=\sum\limits_{d\neq n,d|n}f(d)$。
核心代码：
```cpp
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)$。
核心代码：
```cpp
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$。
核心代码：
```cpp
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})$。
核心代码：
```cpp
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](https://www.luogu.com.cn/problem/P4718)。
### Sub7
看看数据，动了亿点脑子，得 $f(p^k)=ap^{3k}+bp^{2k}+cp^k+d$，运用拉格朗日插值，脑量不足，只得 $a=114$，运用人类智慧，得 $a=114,b=514,c=1919,d=810$。
核心代码：
```cpp
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$，正确！
核心代码：
```cpp
cout<<1ll*n*n%3<<endl;
```
总结，非常好莫比乌斯反演，下次别出了。