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;
}
1、python - easy_install的安装和使用
2、Daily Scrum 11.10
3、构建自定义组件
4、新网站发布问题多多！
5、【摘自张宴的"实战:Nginx"】Nginx的server指令