laekov

多组询问，硬根号。yy了一下午，在去80MSWC的时候的病历上打了若干草稿，最后硬yy出来了。

其实拿LaTeX来当公式编辑器蛮好的。

然后d(a)函数可以线性筛，讨论一下是不是倍数就行了。

发现数论真的好神奇。

lofter的html源码好讨厌啊。

#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
#define _l (long long int)
 
const int maxn = 10000009;
const int maxq = 10009;
const int mod = 1e8 + 9;
 
int pn[maxn], tp, d[maxn];
bool pr[maxn];
int q, m[maxq], n[maxq], t;
 
#define incm(_a_,_b_) { \
    _a_+=_b_; \
    if (_a_>=mod||_a_<=-mod) \
        _a_%=mod; \
    if (_a_<0) \
        _a_+=mod; \
}
 
void pre(int n) {
    memset(pr, 0, sizeof(pr));
    tp = 0;
    d[0] = 0;
    d[1] = 1;
    for (int i = 2; i <= n; ++ i) {
        if (!pr[i]) {
           pn[tp ++] = i;   
           d[i] = (i - _l i * i) % mod;
           if (d[i] < 0)
               d[i] += mod;
        }
        for (int j = 0; j < tp && i * pn[j] <= n; ++ j) {
            pr[i * pn[j]] = 1;
            if (i % pn[j]) {
                d[i * pn[j]] = _l d[i] * d[pn[j]] % mod;
            }
            else {
                d[i * pn[j]] = _l d[i] * pn[j] % mod;
                break;
            }
        }
    }
    for (int i = 2; i <= n; ++ i)
        incm(d[i], d[i - 1]);
}
 
inline int sumr(const int& x) {
    return (((_l x + 1) * x) >> 1) % mod;
}
 
int sov(int m, int n) {
    int ans(0);
    for (int i = 1, j; i <= n; i = j + 1) {
        j = min(m / (m / i), n / (n / i));
        incm(ans, (_l d[j] - d[i - 1]) * sumr(m / i) % mod * sumr(n / i) % mod);
    }
    return ans;
}
 
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
 
    scanf("%d", &q);
    t = 0;
    for (int i = 0; i < q; ++ i) {
        scanf("%d%d", m + i, n + i);
        if (m[i] < n[i])
            swap(m[i], n[i]);
        if (t < m[i])
            t = m[i];
    }
    pre(t);
    for (int i = 0; i < q; ++ i)
        printf("%d\n", sov(m[i], n[i]));
}