标签：const int res num SDOI2014 query 数表
链接：https://www.luogu.com.cn/problem/P3312
题目描述：求$\sum_{i=1}^{n}\sum_{j=1}^{m}d(gcd(i,j))[d(gcd(i,j))<=a]$
题解：我们先会有一个直观的想法：先不考虑$a$的限制：
$\qquad\sum_{i=1}^{n}\sum_{j=1}^{m}d(gcd(i,j))$
$\quad=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}d$
$\quad=\sum_{d=1}^{n}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$
如果你这么推就推不下去了。
考虑换一种思路，将$d$看作一个不能拆开的函数：
$\qquad\sum_{i=1}^{n}\sum_{j=1}^{m}d(gcd(i,j))$
$\quad=\sum_{t=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==t]d(t)$
$\quad=\sum_{t=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}[gcd(i,j)==1]d(t)$
$\quad=\sum_{t=1}^{n}d(t)\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}\sum_{s|gcd(i,j)}μ(s)$
$\quad=\sum_{t=1}^{n}d(t)\sum_{s=1}^{n}μ(s)\lfloor\frac{n}{ts}\rfloor\lfloor\frac{m}{ts}\rfloor$
$\quad=\sum_{T=1}^{n}\sum_{t|T}d(t)μ(\frac{T}{t})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor$
我们可以将所有数按$d(x)$的值排序，将询问也按$a$排序，用树状数组处理贡献即可。
```
#include
#include
#define N 100000
using namespace std;
struct node
{
long long x,y,a,num;
bool operator < (const node &t)const
{
return a<t.a; }="" };="" struct="" reads="" {="" long="" num,data;="" bool="" operator="" <="" (const="" &a)const="" return="" data<a.data;="" node="" query[1000001];="" top[1000001];="" c[1000001],res,f[1000001],miu[1000001],mod;="" unsigned="" ans[1000001];="" prime[1000001];="" int="" lowbit(int="" x)="" x&(-x);="" void="" add(int="" x,int="" y)="" for="" (;x<="N;x+=lowbit(x))" c[x]+="y;" return;="" sum(int="" res="0;" (;x="">=1;x-=lowbit(x))
res+=c[x];
return res;
}
void prework()
{
for (int i=1;i<=N;++i)
miu[i]=1;
for (int i=2;i<=N;++i)
if (!prime[i])
for (int j=i;j<=N;j+=i)
{
prime[j]=1;
if ((j/i)%i==0)
miu[j]=0;
miu[j]=-miu[j];
}
for (int i=1;i<=N;++i)
for (int j=i;j<=N;j+=i)
f[j]+=i;
for (int i=1;i<=N;++i)
{
top[i].num=i;
top[i].data=f[i];
}
sort(top+1,top+N+1);
return;
}
int main()
{
prework();
int t,pos=0,last;
mod=(1ll<<31);
cin>>t;
for (int i=1;i<=t;++i)
{
cin>>query[i].x>>query[i].y>>query[i].a;
query[i].num=i;
}
sort(query+1,query+t+1);
for (int q=1;q<=t;++q)
{
while (pos
标签：const,
int,
res,
num,
SDOI2014,
query,
数表
From： https://www.cnblogs.com/zhouhuanyi/p/16983494.html