bzoj3309: DZY Loves Math | jeffswt: the ac moments

Description

对于正整数 $n$ , 定义 $f(n)$ 为 $n$ 所含质因子的最大幂指数. 例如 $f(1960) = f(2^3 \times 5^1 \times 7^2) = 3$ , $f(10007) = 1$ , $f(1) = 0$ . 现给定正整数 $a, b$ , 求: $\sum_{i=1}^{a} \sum_{j=1}^{b} f(gcd(i, j))$

Input

第一行一个数 $T$ , 表示询问数.

接下来 $T$ 行, 每行两个数 $a, b$ , 表示一个询问.

Output

对于每一个询问, 输出一行一个非负整数作为回答.

Sample Input

4
10000
7558588 9653114
6514903 4451211
7425644 1189442
6335198 4957

Sample Output

35793453939901
14225956593420
4332838845846
15400094813

Data Range

对于所有数据, 满足: $T \leq 10000, 1 \leq a, b \leq 10^7$ .

Explanation

不说话, 直接上公式: $\begin{aligned} & \sum_{i=1}^{n} \sum_{j=1}^{m} f(gcd(i, j))\\ = & \sum_{d=1}^{min(a, b)} f(d) \sum_{k=1}^{min(\left \lfloor \frac{a}{d} \right \rfloor \cdot \left \lfloor \frac{b}{d} \right \rfloor)} \mu(k) \left \lfloor \frac{a}{kd} \right \rfloor \left \lfloor \frac{b}{kd} \right \rfloor\\ = & \sum_{T=1}^{min(a, b)} \left \lfloor \frac{a}{T} \right \rfloor \left \lfloor \frac{b}{T} \right \rfloor \sum_{d|T} f(d) \cdot \mu(\frac{T}{d}) \end{aligned}$ 线性筛预处理.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 10000100;

bool flag[maxn];
int prime[maxn], pcnt;
int t[maxn], last[maxn], g[maxn];
int n, m, T;

int main(int argc, char** argv)
{
    // Retrieving mu function
    for (int i = 2; i < maxn; i++) {
        if (!flag[i]) {
            prime[++pcnt] = i;
            last[i] = t[i] = 1;
            g[i] = 1;
        }
        for (int j = 1; i * prime[j] < maxn && j <= pcnt; j++) {
            int x = i * prime[j];
            flag[x] = true;
            if (i % prime[j] == 0) {
                last[x] = last[i];
                t[x] = t[i] + 1;
                if (last[x] == 1)
                    g[x] = 1;
                else
                    g[x] = (t[last[x]] == t[x]) ? -g[last[x]] : 0;
                break;
            }
            last[x] = i;
            t[x] = 1;
            g[x] = (t[i] == 1) ? -g[i] : 0;
        }
    }
    for (int i = 1; i < maxn; i++)
        g[i] += g[i-1];
    // Queries
    scanf("%d", &T);
    for (int idx = 1; idx <= T; idx++) {
        scanf("%d%d", &n, &m);
        if (n > m)
            swap(n, m);
        // Calculating result
        lli res = 0;
        for (int i = 1, pos = 1; i <= n; i = pos + 1) {
            pos = min(n / (n / i), m / (m / i));
            res += 1ll * (g[pos] - g[i-1]) * (n / i) * (m / i);
        }
        printf("%lld\n", res);
    }
    return 0;
}