Wannafly挑战赛27 D绿魔法师

链接Wannafly挑战赛27 D绿魔法师

一个空的可重集合$S$，$n$次操作，每次操作给出$x,k,p$，要求支持下列操作：
1、在$S$中加入$x$。
2、求$$\sum_{y\in S}gcd(x,y)^k\ mod\ p$$
所有输入的数不超过$10^5$。
不是莫比乌斯啊。
做法比较暴力，应该有更好的$idea$
首先把$1$到$n$的每个数的所有因数筛出来，$nlnn$即可。
然后考虑怎么算一个数的答案。
首先$gcd$意味着最后算入答案的数一定是$x$的约数，那么对于加入一个数$x$，我们把他所有的约数都加上1，对于询问元素$x$，直接查他的约数的值即可。
但是这样会算重复，原因是一个数的贡献会被算他和$x$的公共约数次，所以对于每个约数，再枚举他的约数容斥减去即可。
复杂度$O(n\sqrt n\ logn)$？？？，感觉不太对。

#include<bits/stdc++.h>

#define R register int

#define ll long long

#define il inline

using namespace std;

const int N=100002;

int n,lim,x,k,mod,tp,S[N],hav[N],STK[N];

vector<int>G[N];

il int gi(){

    ll x=0,k=1;char c=getchar();

    while((c<'0'||c>'9')&&c!='-')c=getchar();

    if(c=='-')k=-1,c=getchar();

    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();

    return x*k;

}

il int Qpow(R x,R y){

    R ans=1,bas=x;

    while(y){

        if(y&1)ans=1ll*ans*bas%mod;

        bas=1ll*bas*bas%mod,y>>=1;

    }return ans;

}

il void sol(){

    R res=0;

    x=gi(),k=gi(),mod=gi();

    for(R i=0,lim=G[x].size();i<lim;++i)

        S[G[x][i]]++;

    for(R i=G[x].size()-1,v=G[x][i];i>=0;--i,v=G[x][i]){

        if(!S[v])continue;

        res=(res+1ll*S[v]*Qpow(v,k)%mod)%mod;

        for(R j=G[v].size()-2;j>=0;--j){

            S[G[v][j]]-=S[v];

            if(!hav[G[v][j]])STK[++tp]=G[v][j];

            hav[G[v][j]]+=S[v];

        }

    }

    while(tp)S[STK[tp]]+=hav[STK[tp]],hav[STK[tp]]=0,tp--;

    printf("%d\n",res);

}

int main(){

    n=gi(),lim=1e5+1;

    for(R i=1;i<=lim;++i)

        for(R j=i;j<=lim;j+=i)

            G[j].push_back(i);

    while(n--)sol();

    return 0;

}

巴特西

Wannafly挑战赛27 D绿魔法师

链接Wannafly挑战赛27 D绿魔法师

最新文章

热门文章