BZOJ2693: jzptab(莫比乌斯反演)

#include<cstdio>
#include<algorithm>
#define LL long long 
using namespace std;
const int MAXN = 1e7 + 10, mod = 100000009;
int T, N, M;
int tot, vis[MAXN];
LL f[MAXN], prime[MAXN];
void GetF(int N) {
    f[1] = 1;
    for(int i = 2; i <= N; i++) {
        if(!vis[i]) prime[++tot] = i, f[i] = (i - 1ll * i * i  % mod + mod) % mod;
        for(int j = 1; j <= tot && i * prime[j] <= N; j++) {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j])) {
                f[i * prime[j]] = f[i] * prime[j] % mod;
                break;
            } else f[i * prime[j]] = f[i] * f[prime[j]] % mod;
        }
    }
    for(int i = 2; i <= N; i++) f[i] = (f[i - 1] + f[i] + mod) % mod;
}
LL S(LL x) {
    return (x * (x + 1)) / 2 % mod;
}
int main() {
    scanf("%d", &T);
    GetF(1e7 + 1);
    while(T--) {
        int N, M, last;
        LL ans = 0;
        scanf("%d %d", &N, &M);
        if(N > M) swap(N, M);
        for(int i = 1; i <= N; i = last + 1) {
            last = min(N / (N / i), M / (M / i));
            ans = (ans + S(N / i) * S(M / i) % mod * (f[last] - f[i - 1] + mod) % mod) % mod;
        }
        printf("%lld\n", ans);
        
    }
    return 0;
}
/*
2
4 5
123456 654321

*/