BZOJ-2693: jzptab

Description

多组询问 (mod 100000009) T <= 10000 N, M<=10000000

推式子！！！

=
=
=
=
设
=
将k*d提前（的d和k等价于的d和d/p）
=
因为是整除，所以可以化简一下：
=
=
积性函数乘积和的狄利克雷卷积仍然积性。快筛。之后乘以d求前缀和，前半部分分块就在O(√n)分块。时间复杂度O(n+T√n)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=100000009;
ll ans[10001000],n,m;
ll yz[10001000],pri[10001000],cnt;
bool v[10001000];
void quick_ans()
{
    ans[1]=1;
    for(ll i=2;i<=10000000;++i)
    {
        if(!v[i]) pri[++cnt]=i,yz[i]=i,ans[i]=1-i;
        for(ll j=1;i*pri[j]<=10000000&&j<=cnt;++j)
        {
            v[i*pri[j]]=1;
            if(i%pri[j]) yz[i*pri[j]] = pri[j],
                ans[i*pri[j]] = ans[i]*(1-pri[j])%mod;
            else{
                yz[i*pri[j]] = yz[i]*pri[j];
                ans[i*pri[j]] = (yz[i]==i) ? 1-pri[j] :
                ans[i*pri[j]/yz[i*pri[j]]]*ans[yz[i*pri[j]]]%mod;
                break;
            }
        }
    }
    for(ll i=1;i<=10000000;++i)
        ans[i]=(ans[i]*i%mod+ans[i-1]+mod)%mod;
}
inline ll get_f(ll x,ll y)
{
    x=x*(x+1)/2%mod;
    y=y*(y+1)/2%mod;
    return x*y%mod;
}
int main()
{
    quick_ans(); int t; scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&m); if(n>m) swap(n,m);
        ll b=1,e,fna=0;
        while(b<=n)
        {
            e=min(n/(n/b),m/(m/b));
            fna=(fna+(ans[e]-ans[b-1]+mod)%mod*get_f(n/b,m/b)%mod)%mod;
            b=e+1;
        }
        printf("%lld\n",fna);
    }
    return 0;
}