题面

Sol

先不管\(a\)的限制

设\(f(n)\)表示f的约数和(\(据说是\sigma\))，它是个积性函数，\(n<m\)

则题目要求的就是\(\sum_{i=1}^{n}\sum_{j=1}^{m}f(gcd(i, j))\)

考虑每个\(gcd\)的贡献，\(\sum_{i=1}^{n}f(i)\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}\mu(j)\lfloor\frac{n}{i*j}\rfloor\lfloor\frac{m}{i*j}\rfloor\)

替换\(i*j\)就是\(\sum_{k=1}^{n}\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor\sum_{d|k}f(d)\mu(\frac{k}{d})\)

但是我们有限制，就不能直接筛\(\sum_{d|k}f(d)\mu(\frac{k}{d})\)

所以考虑离线处理，把询问按a排序，每次把小于等于a的\(f\)同它的所有倍数n的\(\sum_{d|n}f(d)\mu(\frac{n}{d})\)加进来，树状数组维护前缀和即可

只要预处理处\(\mu\)和\(f\)就好了，见上面的筛法链接

# include 
    
     # define RG register# define IL inline# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;const int _(1e5 + 1), INF(2147483647);IL ll Read(){    RG ll x = 0, z = 1; RG char c = getchar();    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);    return x * z;}int prime[_], num, N, Q, id[_], ans[_], f[_], mu[_], sumd[_], powd[_], bit[_];bool isprime[_];struct Qry{    int n, m, a, id;    IL bool operator <(RG Qry B) const{  return a < B.a;  }} qry[_];IL void Prepare(){    isprime[1] = 1; id[1] = f[1] = mu[1] = 1;    for(RG int i = 2; i < N; ++i){        id[i] = i;        if(!isprime[i]){            prime[++num] = i; f[i] = i + 1; mu[i] = -1;            sumd[i] = 1 + i; powd[i] = i;        }        for(RG int j = 1; j <= num && i * prime[j] < N; ++j){            isprime[i * prime[j]] = 1;            if(i % prime[j]){                sumd[i * prime[j]] = 1 + prime[j]; powd[i * prime[j]] = prime[j];                f[i * prime[j]] = f[i] * f[prime[j]];                mu[i * prime[j]] = -mu[i];            }            else{                mu[i * prime[j]] = 0;                powd[i * prime[j]] = powd[i] * prime[j];                sumd[i * prime[j]] = sumd[i] + powd[i * prime[j]];                f[i * prime[j]] = f[i] / sumd[i] * sumd[i * prime[j]];                break;            }        }    }}IL bool Cmp(RG int x, RG int y){  return f[x] < f[y];  }IL void Add(RG int x, RG int d){  for(; x < N; x += x & -x) bit[x] += d;  }IL int Query(RG int x){  RG int ret = 0; for(; x; x -= x & -x) ret += bit[x]; return ret;  }IL int Calc(RG int n, RG int m){    RG int ret = 0, lst = 0, now;    for(RG int i = 1, j; i <= n; i = j + 1){        j = min(n / (n / i), m / (m / i));        now = Query(j);        ret += (n / i) * (m / i) * (now - lst);        lst = now;    }    return ret;}int main(RG int argc, RG char* argv[]){    Q = Read();    for(RG int i = 1, n, m, a; i <= Q; ++i){        n = Read(); m = Read(); a = Read();        if(n > m) swap(n, m);        qry[i] = (Qry){n, m, a, i};        N = max(N, n + 1);    }    Prepare();    sort(qry + 1, qry + Q + 1); sort(id + 1, id + N, Cmp);    for(RG int i = 1, j = 1; i <= Q; ++i){        for(; j < N && f[id[j]] <= qry[i].a; ++j)            for(RG int k = id[j]; k < N; k += id[j])                Add(k, f[id[j]] * mu[k / id[j]]);        ans[qry[i].id] = Calc(qry[i].n, qry[i].m);    }    for(RG int i = 1; i <= Q; ++i) printf("%d\n", ans[i] < 0 ? ans[i] + INF + 1 : ans[i]);    return 0;}