题目描述

Description

Input

一个正整数T表示数据组数
接下来T行 每行两个正整数 表示N、M

Output

T行 每行一个整数 表示第i组数据的结果

Sample Input

1
4 5

Sample Output

122

HINT

T <= 10000
N, M<=10000000

题目分析

---

以上公式已经足以应付 Crash的数字表格了
想要做 jzptab的话还要继续推
引用上面的结论

令


然后我们需要线性筛出
模仿快筛欧拉函数的过程

线性筛的过程先挖个坑 = =

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,t;
int prime[10000100],f[10000100],mu[10000010];
int g[10000010],h[10000010],gh[10000010];
bool vis[10000010];
int mod=100000009;
void init()
{
    mu[1]=g[1]=h[1]=gh[1]=f[1]=1;
    for(int i=2;i<=10000000;i++)
    {
        if(!vis[i]) prime[++prime[0]]=i,g[i]=i,h[i]=1,gh[i]=i,f[i]=1-i,mu[i]=-1;
        for(int j=1;j<=prime[0]&&i*prime[j]<=10000000;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j])
            {
                mu[i*prime[j]]=-mu[i];
                g[i*prime[j]]=prime[j];
                h[i*prime[j]]=1;
                gh[i*prime[j]]=prime[j];
                f[i*prime[j]]=f[i]*f[prime[j]];
            }
            else
            {
                mu[i*prime[j]]=0;
                g[i*prime[j]]=prime[j];
                h[i*prime[j]]=h[i]+1;
                gh[i*prime[j]]=gh[i]*prime[j];
                if(i*prime[j]==gh[i*prime[j]]) f[i*prime[j]]=1-prime[j];
                else f[i*prime[j]]=f[i*prime[j]/gh[i*prime[j]]]*f[gh[i*prime[j]]];
                break;
            }
        }
    }
    for(int i=1;i<=10000000;i++)
        f[i]=((long long)f[i]*i)%mod,f[i]=(f[i]+f[i-1]+mod)%mod;
}
long long cal(int x)
{
    return (long long) x*(x+1)/2%mod;
}
void slove()
{
    if(n>m) swap(n,m);
    int last=0;
    long long ans=0;
    for(int i=1;i<=n;i=last+1)
    {
        last=min(n/(n/i),m/(m/i));
        ans=(ans+(long long)(f[last]-f[i-1]+mod)%mod*cal(n/i)%mod*cal(m/i)%mod)%mod;
    }
    printf("%lld\n",ans);
}
int main()
{   
    init();
    scanf("%d",&t);
    while(t--)
        scanf("%d%d",&n,&m),slove();
    return 0;
}