TotalSubmission(s):980    AcceptedSubmission(s):376ProblemDescriptionAsweknow,anypositiveintegerC(C>=2)canbewrittenasthemultiplyofsomepri...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ450.html首先有一个东西叫做“单位根反演”，它在FFT的时候用到过：$$frac1nsum_{i=0}^{n-1}omega_n^{dcdoti}=[n|d]$$其中$omega_n$表示$n$次单...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ62.html太久没更博客了，该拯救我的博客了。$$sum_{1leqjleqn}gcd(i,j)^{c-d}i^dj^dx_j=b_i\A_i=i^dx_i,B_i=frac{b_i}{i^d},f(x)=x^{c-d}\f(...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ33.html　　首先我们把问题转化成处理一个数组ans，其中ans[i]表示d(u,a)和d(v,a)同时为i的倍数的(u,v)个数。（最后求答案的时候只要莫比乌斯反演回来就好了。）　　注意一下我的代码中对于(u,v)有祖先关...

原文链接http://www.cnblogs.com/zhouzhendong/p/8666106.html　　定义$f(0)=0,f(1)=1,f(i)=f(i-1)+f(i-2)$。　　$T$组数据，每组数据两个整数$n,m$，求$prod_{i=1}^nprod_{j=1}^mf(gcd(i,j))$。　　$Tl...

原文http://www.cnblogs.com/zhouzhendong/p/8665675.html　　给定序列$a,b$，让你求满足$gcd(x,y)=1,a_{b_x}=b_{a_y}$的$(x,y)$的个数。　　我们先考虑没有$gcd(x,y)=1$的情况。　　仔细一看发现$a_{b_x}=b_{a_y}$是...

原文链接http://www.cnblogs.com/zhouzhendong/p/8116330.htmlUPD(2018-03-26):回来重新学数论啦。之前的博客版面放在更新之后的后面。　　给出$n,m$,求$Largesum_{i=1}^nsum_{j=1}^mlcm(i,j)^{gcd(i,j)}$。　　$1...

莫比乌斯函数：  voidget_mu(intn){mu[1]=1;for(inti=2;i<=n;i++){if(!vis[i]){prim[++cnt]=i;mu[i]=-1;}for(intj=1;j<=cnt&&prim[j]*i<=n;j++){vis[p...