题解 P3312 【[SDOI2014]数表】
Dirichlet
2018-05-03 15:23:57
令$g(k)=\sum\limits_{i=1}^n \sum\limits_{j=1}^m gcd(i,j)==k$
$g(k)=\sum\limits_{i|d} \mu(\frac{d}{i})\cdot \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor$
那么 $\sum\limits_{i=1}^n \sum\limits_{j=1}^m F(gcd(i,j))$
$=\sum\limits_{i=1}^n F(i)g(i)$
$=\sum\limits_{i=1}^n F(i) \sum\limits_{i|d} \mu(\frac{d}{i})\cdot \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor$
$=\sum\limits_{e=1}^n \lfloor \frac{n}{e} \rfloor \lfloor \frac{m}{e} \rfloor \sum\limits_{i|e} F(i)\cdot \mu (\frac{e}{i})$
如果我们预处理 $\xi (e) = \sum\limits_{i|e} F(i)\cdot \mu (\frac{e}{i})$
就可以在$O(q\sqrt{n})$时间内求出答案.
现在考虑a的限制.
注意到所有$F(i)<a$的$i$会对答案产生贡献.
故将操作离线,对询问按$a$升序排序,对$F(i)$按$i$排序.
每次将所有满足要求的函数值插入"某个数据结构"中,该数据结构需支持单点修改和区间求和.
那当然是常数小又好写的BIT啦.
模数的特殊性质:
可以直接爆int取模.
蒟蒻的代码:
```cpp
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<ctime>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#define size 520010
#define debug(x) cerr<<#x<<"="<<x
#define gc getchar()
#define db double
#define ll long long
#define rep(i,s,n) for (register int i=s;i<=n;i++)
#define drep(i,n,s) for (register int i=n;i>=s;i--)
#define il inline
using namespace std;
il ll r()
{
char c; ll x,f=1;
for (c=gc;!isdigit(c);c=gc) if (c=='-') f=-1; x=c-'0';
for (c=gc;isdigit(c);c=gc) x=(x<<1)+(x<<3)+c-'0';
return f*x;
}
int pri[size],mu[size+10],pnt;
bool isp[size+10];
void euler()
{
mu[1]=1; isp[1]=1;
rep(i,2,size)
{
if (!isp[i]) pri[++pnt]=i,mu[i]=-1;
rep(j,1,pnt)
{
if (i*pri[j]>size) break;
isp[i*pri[j]]=1;
if (i%pri[j])
mu[i*pri[j]]=-mu[i];
else
{
mu[i*pri[j]]=0; break;
}
}
}
}
struct qwq
{
int n,m,a,id;
}q[20010];
bool cmp(qwq A,qwq B)
{
return (A.a<B.a);
}
struct sigma
{
int id,dat;
}seq[size];
bool cmp1(sigma S,sigma T)
{
return (S.dat<T.dat);
}
int c[size],ans[size],T;
#define lb(x) x&(-x)
void add(int i,int x)
{
for (;i<=100000;i+=lb(i)) c[i]+=x;
}
int query(int x)
{
int ans=0; for (int i=x;i;i-=lb(i)) ans+=c[i]; return ans;
}
int calc(int n,int m)
{
int ans=0;
if (n>m) swap(n,m);
for (int now=1,nxt;now<=n;now=nxt+1)
{
nxt=min(n/(n/now),(m/(m/now)));
ans+=(n/now)*(m/now)*(query(nxt)-query(now-1));
}
return ans;
}
int main()
{
euler();
T=r();
for (int i=1;i<=100000;i++)
{
seq[i].id=i;
for (int j=1;j*i<=100000;j++) seq[i*j].dat+=i;
}
sort(seq+1,seq+100000+1,cmp1);
for (int i=1;i<=T;i++) {scanf("%d%d%d",&q[i].n,&q[i].m,&q[i].a);q[i].id=i;}
sort(q+1,q+T+1,cmp);
memset(c,0,sizeof(c));
int tmp=0;
for (int i=1;i<=T;i++)
{
while (tmp<100000 && seq[tmp+1].dat<=q[i].a)
{
tmp++;
for (int j=1;j*seq[tmp].id<=100000;j++) add(j*seq[tmp].id,mu[j]*seq[tmp].dat);
}
ans[q[i].id]=calc(q[i].n,q[i].m);
}
for (int i=1;i<=T;i++) printf("%d\n",ans[i]&0x7fffffff);
return 0;
}
```