Description

求

∑i=1n∑j=1mf(gcd(i,j))[f(gcd(i,j))≤a] 其中 f(n)=∑d|nd Q 组数据，每组数据给出n,m,a 1≤n,m≤105,1≤Q≤2∗104

Analysis

默认 n≤m 显然 f 可以nlogn预处理 先考虑单次询问 反演可得

Ans=∑d=1nf[d]∑i=1⌊n/d⌋⌊ndi⌋⌊mdi⌋μ[i] 这样就有60分了 接着套路，设 T=di ∑T=1n⌊nT⌋⌊mT⌋∑d|Tf(d)μ(T/d) 后面部分只与 T 相关，设为g(T)，则 ∑T=1n⌊nT⌋⌊mT⌋g(T) 单次询问可以分块，做到 O(n√) 但是这个 g(T) 会变，因为要满足 f(d)≤a 的 d 才能算进g里面 所以我们可以离线，将所有询问按 a 从小到大排序 那么对于某个d，如果满足了小于 a 就要更新所有的g(d∗i) 如果我们用树状数组维护前缀和，那么就暴力枚举倍数更新就好了 更新总复杂度复杂度 O(nlog2n) 然后分块的时候就可以在树状数组里面查询，单次查询复杂度 O(n√logn) 注意本题需要卡常技巧

Code

#include<cstdio> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std; typedef long long ll; const int N=100005,MX=100000; const ll mo=2147483648; int f[N],mu[N],pri[N],an[N],tr[N]; struct op { int n,m,k,id; }b[N]; struct lyd { int x,id; }a[N]; bool bz[N+5]; bool cmp(op a,op b) { return a.k<b.k; } bool cmpa(lyd a,lyd b) { return a.x<b.x; } void pre() { mu[1]=1; fo(i,2,MX) { if(!bz[i]) pri[++pri[0]]=i,mu[i]=-1; fo(j,1,pri[0]) { ll x=i*pri[j]; if(x>MX) break; bz[x]=1; if(i%pri[j]==0) { mu[x]=0; break; } mu[x]=-mu[i]; } } } int lowbit(int x) { return x&-x; } int get(int x) { int t=0; for(int i=x;i;i-=lowbit(i)) t=((ll)t+tr[i])%mo; return t; } void add(int x,int y) { y=((ll)y+mo)%mo; for(int i=x;i<=MX;i+=lowbit(i)) tr[i]=((ll)tr[i]+y)%mo; } int main() { freopen("table.in","r",stdin); freopen("table.out","w",stdout); fo(i,1,MX) for(int j=i;j<=MX;j+=i) (f[j]+=i)%=mo; fo(i,1,MX) a[i].x=f[i],a[i].id=i; sort(a+1,a+MX+1,cmpa); pre(); int T; scanf("%d",&T); fo(i,1,T) scanf("%d %d %d",&b[i].n,&b[i].m,&b[i].k),b[i].id=i; sort(b+1,b+T+1,cmp); int p=1; fo(l,1,T) { int n=b[l].n,m=b[l].m; if(n>m) swap(n,m); for(;a[p].x<=b[l].k && p<=MX;p++) { int t=a[p].id; for(int j=t;j<=MX;j+=t) add(j,a[p].x*mu[j/t]); } ll ans=0; int lst=0; for(int i=1,j;i<=n;i=j+1) { j=min(n/(n/i),m/(m/i)); int s=get(j); ll t=(s-lst+mo)%mo; lst=s; ans=(ans+(n/i)*(m/i)*t%mo)%mo; } an[b[l].id]=ans; } fo(i,1,T) printf("%d\n",an[i]); return 0; }