@[toc]

題意

，求。
鏈接：hdu6715

思路

方法一：
打表得出：

進(jìn)一步按套路優(yōu)化，提出，令得：

• 首先這個(gè)東西是，是一個(gè)積性函數(shù)，所以可以篩出來。
• 這個(gè)東西可以按分別預(yù)處理出來，預(yù)處理的復(fù)雜度和埃式篩一樣是，空間復(fù)雜度也是。
• 最后上面這個(gè)式子就可以求和了。
• HDU數(shù)據(jù)證明，不預(yù)處理第二點(diǎn)更快。。。

方法二：

已知
又因?yàn)椋?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cmu(i*j)%3D%5Cmu(i)*%5Cmu(j)%5Bgcd(i%2Cj)%3D%3D1%5D" alt="\mu(i*j)=\mu(i)*\mu(j)[gcd(i,j)==1]" mathimg="1">

因此：

因?yàn)楫?dāng)不為時(shí)：

而當(dāng)為時(shí)，自然也是，所以也不會(huì)影響下面這個(gè)式子：

接下來的步驟和方法一就相同啦。

AC_CODE

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
#include <ctime>
#include <iostream>
#include <assert.h>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define fi first
#define se second
#define endl '\n'
#define o2(x) (x)*(x)
#define BASE_MAX 31
#define mk make_pair
#define eb push_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a),(b),sizeof((a)))
#define iis std::ios::sync_with_stdio(false); cin.tie(0)
#define my_unique(x) sort(all(x)),x.erase(unique(all(x)),x.end())
using namespace std;
#pragma optimize("-O3")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> pii;
inline LL read() {
    LL x = 0;int f = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x = f ? -x : x;
}
inline void write(LL x, bool f) {
    if (x == 0) {putchar('0'); if(f)putchar('\n');else putchar(' ');return;}
    if (x < 0) {putchar('-');x = -x;}
    static char s[23];
    int l = 0;
    while (x != 0)s[l++] = x % 10 + 48, x /= 10;
    while (l)putchar(s[--l]);
    if(f)putchar('\n');else putchar(' ');
}
int lowbit(int x) { return x & (-x); }
template<class T>T big(const T &a1, const T &a2) { return a1 > a2 ? a1 : a2; }
template<class T>T sml(const T &a1, const T &a2) { return a1 < a2 ? a1 : a2; }
template<typename T, typename ...R>T big(const T &f, const R &...r) { return big(f, big(r...)); }
template<typename T, typename ...R>T sml(const T &f, const R &...r) { return sml(f, sml(r...)); }
void debug_out() { cerr << '\n'; }
template<typename T, typename ...R>void debug_out(const T &f, const R &...r) {cerr << f << " ";debug_out(r...);}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__);
 
 
const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int HMOD[] = {1000000009, 1004535809};
const LL BASE[] = {1572872831, 1971536491};
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;//998244353
const int INF = 0x3f3f3f3f;
const int MXN = 1e6 + 7;
const int MXE = 2e5 + 7;
int n, m;
int noprime[MXN], pp[MXN], pcnt;
int phi[MXN], mu[MXN];
LL pre_mu[MXN], mumu[MXN];
std::vector<int> vs[MXN];
void init_prime() {
    noprime[0] = noprime[1] = 1;
    mu[1] = 1; phi[1] = 1;mumu[1] = 1;
    for(int i = 2; i < MXN; ++i) {
        if(!noprime[i]) pp[pcnt++] = i, phi[i] = i-1, mu[i] = -1, mumu[i]=-2;
        for(int j = 0; j < pcnt && pp[j] * i < MXN; ++j) {
            noprime[pp[j]*i] = 1;
            phi[pp[j]*i] = (pp[j]-1)*phi[i];
            mu[pp[j]*i] = -mu[i];
            mumu[i*pp[j]] = mumu[i]*mumu[pp[j]];
            if(i % pp[j] == 0) {
                phi[pp[j]*i] = pp[j]*phi[i];
                mu[pp[j]*i] = 0;
                if((i/pp[j])%pp[j]) mumu[i*pp[j]] = mumu[i/pp[j]];
                else mumu[i*pp[j]] = 0;
                break;
            }
        }
    }
    for(int i = 1, t, s; i < MXN; ++i) {
        vs[i].eb(0);
        s = 0;
        for(int j = i; j < MXN; j += i) {
            s += mu[j];
            vs[i].eb(s);
        }
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("E://ADpan//in.in", "r", stdin);
    // freopen("E://ADpan//out.out", "w", stdout);
#endif
    init_prime();
    int tim = read();
    while(tim --) {
        n = read(), m = read();
        if(n > m) swap(n, m);
        LL ans = 0, tmp1, tmp2;
        for(int i = 1; i <= n; ++i) {
            tmp1 = vs[i][n/i];
            tmp2 = vs[i][m/i];
            ans += tmp1 * tmp2 * mumu[i];
        }
        printf("%lld\n", ans);
    }
#ifndef ONLINE_JUDGE
    cout << "time cost:" << 1.0 * clock() / CLOCKS_PER_SEC << "ms" << endl;
#endif
    return 0;
}