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=,MX=;
const ll mo=;
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+];
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[]=;
fo(i,,MX)
{
if(!bz[i]) pri[++pri[]]=i,mu[i]=-;
fo(j,,pri[])
{
ll x=i*pri[j];
if(x>MX) break;
bz[x]=;
if(i%pri[j]==)
{
mu[x]=;
break;
}
mu[x]=-mu[i];
}
}
}
int lowbit(int x)
{
return x&-x;
}
int get(int x)
{
int t=;
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,,MX)
for(int j=i;j<=MX;j+=i) (f[j]+=i)%=mo;
fo(i,,MX) a[i].x=f[i],a[i].id=i;
sort(a+,a+MX+,cmpa);
pre();
int T;
scanf("%d",&T);
fo(i,,T) scanf("%d %d %d",&b[i].n,&b[i].m,&b[i].k),b[i].id=i;
sort(b+,b+T+,cmp);
int p=;
fo(l,,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=;
int lst=;
for(int i=,j;i<=n;i=j+)
{
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,,T) printf("%d\n",an[i]);
return ;
}