JZOJ 4379 盈虚方田

这不原题？？？
手动左转「『SDOI2014』数表」……

首先单纯度可以在欧拉筛的时候顺便筛出来。
然后设 n 的单纯度为 f(n)。

n∑i=1m∑j=1[f(gcd(i,j))≤p]=min(n,m)∑d=1[f(d)≤p]∑id≤min(n,m)μ(i)⌊nid⌋⌊mid⌋=min(n,m)∑T=1⌊nT⌋⌊mT⌋∑d|T[f(d)≤p]μ(Td)

然后套路地套上一个树状数组，复杂度 O(nlog2n+T√nlogn)（认为所有 n,m 同阶）。

代码：

#include <cstdio>
#include <algorithm>
#define lowbit(x) ((x) & -(x))
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w ? x = -x : x;
}

const int N = 5e5;
const int Q = 5e3;
int q;
struct s_query
{
    int n,m,p,id;
    inline bool operator<(const s_query &o) const
    {
        return p < o.p;
    }
} qry[Q + 5];
int vis[N + 5],prime[N + 5],cnt,mu[N + 5],f[N + 5];
struct note
{
    int id,f;
    inline bool operator<(const note &o) const
    {
        return f < o.f;
    }
} a[N + 5];
int c[N + 5];
inline void update(int x,int k)
{
    for(;x <= N;x += lowbit(x))
        c[x] += k;
}
inline int query(int x)
{
    long long ret = 0;
    for(;x;x -= lowbit(x))
        ret += c[x];
    return ret;
}
long long ans[N + 5];
int main()
{
    mu[1] = 1;
    for(register int i = 2;i <= N;++i)
    {
        if(!vis[i])
            mu[prime[++cnt] = i] = -1,f[i] = 1;
        for(register int j = 1;j <= cnt && i * prime[j] <= N;++j)
        {
            vis[i * prime[j]] = 1,f[i * prime[j]] = f[i] + 1;
            if(!(i % prime[j]))
                break;
            else
                mu[i * prime[j]] = -mu[i];
        }
    }
    for(register int i = 1;i <= N;++i)
        a[i].id = i,a[i].f = f[i];
    sort(a + 1,a + N + 1);
    read(q);
    for(register int i = 1;i <= q;++i)
        read(qry[i].n),read(qry[i].m),read(qry[i].p),qry[i].id = i;
    sort(qry + 1,qry + q + 1);
    for(register int i = 1,n,m,j = 1;i <= q;++i)
    {
        for(;a[j].f <= qry[i].p && j <= N;++j)
            for(register int k = a[j].id,l = 1;k <= N;k += a[j].id,++l)
                update(k,mu[l]);
        n = qry[i].n,m = qry[i].m;
        if(n > m)
            swap(n,m);
        for(register int l = 1,r;l <= n;l = r + 1)
        {
            r = min(n / (n / l),m / (m / l));
            ans[qry[i].id] += (long long)(query(r) - query(l - 1)) * (n / l) * (m / l);
        }
    }
    for(register int i = 1;i <= q;++i)
        printf("%lld\n",ans[i]);
}