BZOJ 2693 JZPTAB

莫比乌斯反演。懒得写了。。直接抄CRASH的代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define mod 100000009
#define maxn 10000005
using namespace std;
long long n,m,f[maxn],pre[maxn],prime[maxn/10],cnt=0,T;
bool vis[maxn];
void get_table()
{
    f[1]=1;
    for (long long i=2;i<=maxn;i++)
    {
        if (vis[i]==false)
        {
            prime[++cnt]=i;
            f[i]=1-i;
        }
        for (long long j=1;j<=cnt && i*prime[j]<=maxn;j++)
        {
            vis[i*prime[j]]=true;
            if (i%prime[j]!=0) f[i*prime[j]]=(f[i]*(1-prime[j]))%mod;
            else 
            {
                f[i*prime[j]]=f[i];
                break;
            }
        }
    }
    for (long long i=1;i<=maxn;i++)
        pre[i]=(pre[i-1]+i*f[i])%mod;
}
long long get_answer()
{
    long long i=1,ans=0;
    while (i<=n)
    {
        long long j;
        j=min(n/(n/i),m/(m/i));
        ans=(ans+((n/i)*(n/i+1)/2%mod)%mod * ((m/i)*(m/i+1)/2%mod)%mod * (pre[j]-pre[i-1])%mod + mod)%mod; 
        i=j+1;
    }
    return ans;
}
int main()
{
    scanf("%lld
",&T);
    memset(pre,0,sizeof(pre));
    memset(vis,false,sizeof(vis)); 
    get_table();
    for (int i=1;i<=T;i++)
    {
        scanf("%lld%lld",&n,&m);
        if (n>m) swap(n,m);
        printf("%lld
",get_answer());
    }
    return 0;
}