记忆崩塌.官方题解

良心WA题人 · 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;
}