[SDOI2014]数表

标签：数学 莫比乌斯反演 树状数组

---

题目描述

有一张N*m的数表，其第i行第j列（1 < =i < =n，1 < =j < =m）的数值为能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。

输入输出格式

输入格式：
输入包含多组数据。
输入的第一行一个整数Q表示测试点内的数据组数
接下来Q行，每行三个整数n，m，a（|a| < =10^9）描述一组数据。

输出格式：
对每组数据，输出一行一个整数，表示答案模2^31。

输入输出样例

输入样例#1：
2
4 4 3
10 10 5

输出样例#1：
20
148

数据范围

1 < =n,m < =10^5 ， 1 < =Q < =2*10^4

题解

题目大意就是让我们求这个:
$$\sum_{i=1}^{N}\sum_{j=1}^{M}d(gcd(i,j))(d(gcd(i,j))<=a)$$
其中d(i)表示i的约数之和
那么首先入手我们是要考虑不含a的限制的情况（由易到难嘛）
考虑对答案贡献数为x，那我们只需枚举x的倍数即可:
$$\sum_{x=1}^{min(n,m)}x\sum_{i=1}^{\left \lfloor \frac{N}{x} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{M}{x} \right \rfloor} = \sum_{x=1}^{min(n,m)}x\left \lfloor \frac{n}{x} \right \rfloor\left \lfloor \frac{m}{x} \right \rfloor$$
嗯…化简到这里我们就可以$O(n)$的时间处理这道题了。嗯..似乎少了点什么，怎么莫比乌斯反演都没用…
这样化简的话加上a的限制就做不下去辣
我们发现，对答案有贡献的话只可能是$d（i）<=a$，所以我们需要在式子中含有$d（i）$这样的函数加上a的限制才可能继续化简下去，即:$…d(x)…$其中省略号表示一些式子
有了上述想法，我们不妨考虑直接枚举（i,j）的gcd，然后后面再乘以一个$d(gcd(i,j))$
$$Ans=\sum_{x=1}^{min(n,m)}d(x)\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==x]$$
诶..是不是看着后面式子很熟悉，我们设以下函数:
$$f(x)=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==x]$$

$$F(x)=\sum_{i=1}^{n}\sum_{j=1}^{m}[x|gcd(i,j)] =\left \lfloor \frac{n}{x} \right \rfloor\left \lfloor \frac{m}{x} \right \rfloor$$
然后就可以开始化简Ans了
$$Ans=\sum_{x=1}^{min(n,m)}d(x)f(x)=\sum_{x=1}^{min(n,m)}d(x)\sum_{x|d}u(\frac{x}{d})F(d)$$
当然直接对后面那一坨式子按照套路展开也行，不过我们想如果把$d(x)$和$u(\frac{x}{d})$能放到一起处理就更好了
于是考虑更改枚举项，我们枚举x的倍数:
$$Ans=\sum_{p=1}^{min(n,m)}\left \lfloor \frac{n}{p} \right \rfloor\left \lfloor \frac{m}{p} \right \rfloor\sum_{x|p}d(x)u(\frac{p}{x})$$
诶..看后面那一坨式子像不像狄利克雷卷积形式(蛤..什么叫迪丽热巴卷积狄利克雷卷积)，不过不知道也没关系，反正后面那一坨可以预处理总对的嘛
现在，我们再来考虑有a的限制
我们发现，只有当$d(x)<=a$时才对答案有贡献，而后面那一坨我们是要前缀和处理的。因此我们可以考虑离线处理，对每个询问按照a由小到大排序，对于每一个询问我们将$d(x)<=a$的$d(x)u(\frac{p}{x})$插入到树状数组中，树状数组的$c[x]$表示$\sum_{m|x}d(m)u(\frac{m}{p})$
因此我们要按照倍数（m, 2m, 3m….）插入
对于询问$[L,R]$（因为有整除分块所以我们会得到一段区间）我们可以直接返回$find(R)-find(L-1)$就可以了

代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define N 100100
using namespace std;

int t, cnt = 0, to = 1, maxn = -1;
int u[N], d[N], g[N], pri[N], c[N];
bool vis[N];
struct node{int i, n, m, a, ans;}p[N], f[N];

int lowbit(int x) {return x & (-x);}
void add(int n, int x, int y) {while(x <= n) c[x] += y, x += lowbit(x);}
bool cmp1(node a, node b) {return a.a < b.a;}
bool cmp2(node a, node b) {return a.i < b.i;}

int find(int x)
{
    int ans = 0;
    while(x) ans += c[x], x -= lowbit(x);
    return ans;
}

void get()
{
    int t = N - 10;
    u[1] = d[1] = g[1] = 1;
    for(int i = 2; i <= t; i ++)
    {
        if(!vis[i])
        {
            u[i] = -1;
            pri[++ cnt] = i;
            d[i] = g[i] = i + 1;
        }
        for(int j = 1; j <= cnt && i * pri[j] <= t; j ++)
        {
            vis[i * pri[j]] = true;
            if(i % pri[j]) 
            {
                u[i * pri[j]] = -u[i];
                g[i * pri[j]] = g[i] * (1 + pri[j]);
                d[i * pri[j]] = 1 + pri[j]; 
            }
            else
            {
                d[i * pri[j]] = d[i] * pri[j] + 1;
                g[i * pri[j]] = g[i] / d[i] * d[i * pri[j]];
                break;
            }
        }
    }
    for(int i = 1; i <= t; i ++) f[i].i = i, f[i].a = g[i];
    sort(f + 1, f + t + 1, cmp1);
}

int main()
{
    get();
    scanf("%d", &t);
    for(int i = 1; i <= t; i ++)
    {
        scanf("%d%d%d", &p[i].n, &p[i].m, &p[i].a);
        maxn = max(maxn, min(p[i].n, p[i].m));
        p[i].i = i; 
    }
    sort(p + 1, p + t + 1, cmp1);
    for(int i = 1; i <= t; i ++)
    {
        int n = p[i].n, m = p[i].m;
        int ans = 0;
        if(n > m) swap(n, m);
        for(; f[to].a <= p[i].a && to <= N; to ++)
        {
            for(int k = 1; k * f[to].i <= maxn; k ++)
                add(maxn, k * f[to].i, f[to].a * u[k]);        
        }
        for(int l = 1, r; l <= n; l = r + 1)
        {
            r = min(n / (n / l), m / (m / l));
            ans += (n / l) * (m / l) * (find(r) - find(l - 1));
        }
        p[i].ans = ans;    
    }
    sort(p + 1, p + t + 1, cmp2);
    for(int i = 1; i <= t; i ++) printf("%d\n", p[i].ans & 2147483647);
    return 0;
} 

心得

分析题意，根据题目性质设式子然后化简。而且我们尽量可以更改枚举项使得能预处理的式子在一起（不知道怎么表达…）这种经验还是慢慢积累吧。