DZY Loves Math题解

first game哟~

题意：

∑i=1n∑j=1mf((i,j))\sum_{i=1}^n\sum_{j=1}^mf((i,j))i=1∑n​j=1∑m​f((i,j))

其中 f(x)表示x所含质因子的最大幂指数；

题解：

推导一下：

∑i=1n∑j=1mf((i,j))\sum_{i=1}^n\sum_{j=1}^mf((i,j))i=1∑n​j=1∑m​f((i,j))

提出gcd

∑df(d)∑i=1n/d∑j=1m/d[(i,j)==1]\sum_df(d)\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[(i,j)==1]d∑​f(d)i=1∑n/d​j=1∑m/d​[(i,j)==1]

按照套路暴力展开

∑df(d)∑i=1n/d∑j=1m/d∑t∣(i,j)μ(t)\sum_df(d)\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\sum_{t|(i,j)}\mu(t)d∑​f(d)i=1∑n/d​j=1∑m/d​t∣(i,j)∑​μ(t)

把μ\muμ提前

∑df(d)∑t=1n/dμ(t)[ndt][mdt]\sum_df(d)\sum_{t=1}^{n/d}\mu(t) [\dfrac{n}{dt}][\dfrac{m}{dt}]d∑​f(d)t=1∑n/d​μ(t)[dtn​][dtm​]

设T=dt

∑T=1n[nT][mT]∑d∣Tf(d)∗μ(Td)\sum_{T=1}^n [\dfrac{n}{T}][\dfrac{m}{T}]\sum_{d|T}f(d)*\mu(\dfrac{T}{d})T=1∑n​[Tn​][Tm​]d∣T∑​f(d)∗μ(dT​)

前面那个可以整除分块，后面的卷积只有当T的每个质因子的质数相时才为−（−1)k-（-1)^k−（−1)k(k为质因子个数，因此我们筛出不为0μ\muμ,更新它们的幂就行了。

#include<cstdio>#include<cstring>#include<map>#include<iostream>#include<cmath>#include<bitset>#include<algorithm>#include<cstdlib>#define N 10000007#include<queue>#include<string>#include<set>#define ll long long#define rint register int#include<deque>using namespace std;ll read(){ll f=1,x=0;char c=getchar();while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}int A,B,mu[N],pre[N],cnt,s[N],T;bool vis[N];ll ans;void init(){mu[1]=1;for(int i=2;i<N;++i){if(!vis[i]) pre[++cnt]=i,mu[i]=-1;for(int j=1;j<=cnt&&pre[j]*i<N;++j){vis[pre[j]*i]=1;if(i%pre[j]) mu[i*pre[j]]=-mu[i];else break;}}}int main(){init();for(int i=2;i<N;++i) if(mu[i]){for(ll j=i;j<N;j*=i) s[j]-=mu[i];}for(int i=2;i<N;++i) s[i]+=s[i-1];T=read();while(T--){ans=0;A=read(),B=read();if(A>B) swap(A,B);int r,j1,j2;for(int i=1;i<=A;i=r+1){j1=A/i,j2=B/i;r=min(A/j1,B/j2);ans+=1ll*(s[r]-s[i-1])*j1*j2;}cout<<ans<<'\n';}return 0;}

如果觉得《DZY Loves Math题解》对你有帮助，请点赞、收藏，并留下你的观点哦！