莫比乌斯反演总结

问题提出

我们可能会遇到一些形如

$$F(n)=\sum_{d|n}f(d)$$

的恶心函数。结果发现$f(x)$很难求，但是$F(x)$非常好求。于是就想到怎么用$F(x)$逆推一下$f(x)$。

注意：本文中没有特殊说明的话$\large \frac{a}{b}=\lfloor \frac{a}{b} \rfloor$。

ps:此文章为线下书写，用到的很多公式可能对wordpress环境不适应，如果有公式错误请在下方评论，感谢！

解决问题

莫比乌斯反演

定义

我们观察一下这个函数

然后我们提出一个定理：

$$f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})$$

这就是莫比乌斯反演

莫比乌斯函数

定义

注意到上面提出了一个$\mu(x)$函数，它是这么定义的：

1.若$x=1$，则$\mu(x)=1$

2.把$x$唯一分解，$x=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$且对于$\forall k_i=1$，此时$\mu(x)=(-1)^n$

3.其他情况$\mu(x)=0$

积性函数

定义

对于正整数$n$的一个算术函数$ f(n)$，若$f(1)=1$，且当 $a,b$ 互质时$f(ab)=f(a)f(b)$，在数论上就称它为积性函数。而且积性函数的前缀和也是积性函数。

证明

1.当$\mu(a)=0$，也就是$a$有至少一个质因子出现多次，则$ab$也会出现多次，所以$\mu(ab)=0$。

2.当$\mu(a)=1,\mu(b)=1$，也就是两个都是偶数个质因子，偶+偶=偶，所以$\mu(ab)=1$。

3.当$\mu(a)=1,\mu(b)=-1$，奇+偶=奇，所以$\mu(ab)=-1$。

4.当$\mu(a)=-1,\mu(b)=-1$，奇+奇=偶，所以$\mu(ab)=1$。

线性筛

void get_mu(int n)
{
    mu[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!not_prime[i])
            prime[++tot]=i,mu[i]=-1;
        for (int j=1;prime[j]*i<=n;j++)
        {
            not_prime[prime[j]*i]=1;
            if (i%prime[j]==0)
            {
                mu[prime[j]*i]=0;
                break;
            }
            mu[prime[j]*i]=-mu[i];
        }
    }
}

性质

对于$\forall n \in \mathbb{N}_+ $
$$
\begin{aligned}
\sum_{d|n}\mu(d)=
\left\{
\begin{aligned}
1 \ & (n=1) \\
0 \ & (n>1) \\
\end{aligned}
\right.
\end{aligned}
$$

证明

1.当$n=1$时显然成立

2.当$n \not = 1$时，把$n$分解一下$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$

在$n$的因子中，$\mu$值不为零的只有所有质因子次数都为1的因子，其中质因数个数为$i$的因子个数有$C_k^i$个。

那么就有

$$\sum_{d|n}\mu(d)=C_k^0-C_k^1+C_k^2-\cdots+(-1)^kC_k^k=\sum_{i=0}^k(-1)^iC_k^i$$

然后我们又发现了牛顿老家伙的二项式定理

$$(x+y)^n=\sum_{i=0}^nC_n^ix^iy^{n-i}$$

然后令$x=-1,y=1$，就可以了。

杜教筛

莫比乌斯反演应用

假如我们要求一个

$$\sum_{i=1}^n\mu(i),n\leq 10^{11}$$

这样线性筛就直接爆了。

但我们上面那个性质

$$\sum_{i=1}^n\sum_{d|i}\mu(d)=1$$

化简一下啊

$$\large \sum_{i=1}^n\sum_{j=1}^{\frac{n}{i}}\mu(j)=1,\sum_{i=1}^n\mu(i)=1-\sum_{i=2}^n\sum_{j=1}^{\frac{n}{i}}\mu(j)$$

然后就是枚举因子，递归求解。

这样的话我们就发现它的复杂度就是$O(n^{\frac{4}{3}})$

但是$n$较小的时候可以线筛啊，所以就可以分类讨论一下

我们线筛出$\leq x$的，然后再递推

$$\large O(x+\sum_{i=1}^{\frac{n}{x}}\sqrt{\frac{n}{i}})=O(x+\frac{n}{\sqrt{x}})$$

对$f(x)=x+\frac{n}{\sqrt{x}}$求导得
$$
\begin{aligned}
f'(x) &= (x)’+(\frac{n}{\sqrt{x}})’\\
&=1+\frac{(n)’\sqrt x-n(\sqrt x)’}{(\sqrt x)^2}\\
&=1+\frac{0-n\times \frac{1}{2\sqrt x}}{x}\\
&=1+\frac{-n}{2x^{\frac{3}{2}}}\\
\end{aligned}
$$
这样当$x=n^{\frac{2}{3}}$的时候大概就取到最小值了。。此时为$O(n^{\frac{2}{3}})$。

证明

我们可以试着倒推一下
$$
\large
\begin{aligned}
&\ \ \ \ \sum_{d|n}\mu(d)F(\frac{n}{d})\\
&=\sum_{d|n}\mu(d)\sum_{d’|\frac{n}{d}}f(d’)\\
&=\sum_{d’|n}f(d’)\sum_{d|\frac{n}{d’}}\mu(d)\\
&=f(n)
\end{aligned}
$$
对于第二行，就是代入了一下。

第三行就是对于$f(d’)$他会出现很多次，我们就可以计算它的贡献。

因为我们枚举了所有$d$为$n$ 的因子，所有$d’$是$n \over d$的因子，所以$d’$也是$n$的所有因子。

考虑一下这个$d’|\frac{n}{d}$，它的意思就是枚举所有的$d’$是$\frac{n}{d}$的因子。但是我们反向考虑一下，对于所有的$d$也是$\frac{n}{d‘}$ 的因子。

所以我们就可以直接枚举$d|\frac{n}{d’}$来计算贡献。

然后我们就用上面$\mu$的性质直接计算。当且仅当$d’=n$的时候$d=1$，它后面的式子不为0。所以得证。

形式二

$$F(n)=\sum_{n|d}f(d) \rightarrow f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)$$

证明同理。这是主要应用形式。

变形

$$\large F(x)=\sum_{d=1}^{\frac{n}{x}}f(d\times x) \rightarrow f(x)=\sum_{d=1}^{\frac{n}{x}}F(d\times x)\mu(d)$$

你可以小推一下，其实和形式二是一样的，但是约束了$n$的上界。

例题

hdu1695

地址

题意

给出$n,m,k$ ，求出$1\leq x\leq n, 1 \leq y \leq m$ 且$gcd(x,y) == k$ 的$(x,y)$的对数

题解

显然就是求$ [1,n/k] $与$ [1, m/k]$有多少数对的最大公约数是1

我们设

$f(d)$为满足$gcd(x,y)=d,1\leq x\leq n,1\leq y \leq m$的$(x,y)$的对数

$F(d)$为满足$d|gcd(x,y),1\leq x \leq n,1 \leq y \leq m$的$(x,y)$的对数

就能得到

$$\large F(x)=\sum_{d=1}^{\frac{n}{k}}f(x\times d)$$

如何快速求出$F(x)$呢？

假如$i,j$能被$k$整除，那么就能写成$i=k\times x_1,j=k \times x_2$，那我们就要直接求有多少对$x_1,x_2$。可得

$$F(x)=\frac{n}{x}\times\frac{m}{x}$$

反演一下

$$\large f(x)=\sum_{d=1}^{\frac{n}{k}}\mu(d)F(x\times d)=\sum_{d=1}^{\frac{n}{k}}\mu(d)\frac{n}{xd} \times\frac{m}{xd}$$

这样的话$f(1)$就是答案了，但是暴力是$O(n)$的，如何优化？

我们可分块算啊！$n \over d$最多有$\sqrt{n}$个值。

证明:

1.当$1\leq d < \sqrt n$时，$d$就只有$\sqrt n$个，$n \over d$最多有$\sqrt n$个。

2.当$\sqrt n \leq d \leq n$时，由于$n \over d$小于$\sqrt n$，所以$n \over d$最多有$\sqrt n$个。

证毕。

同理的话，$m \over d$就最多有$\sqrt m$个取值。又因为取值连续，所以$n \over d$和$m \over d$它两个都不变的有$\sqrt n +\sqrt m$个。

那么对于相等的段，就可以求$\mu$的前缀和，批量计算，把复杂度优化到$O(\sqrt n+\sqrt m)$。

具体的实现的时候，假如遍历到了位置$i$，找到下一个相同位置代码为min(n/(n/i),m/(m/i))

对于$n$来说，找到最大的$j$满足

$$\frac{n}{i} \leq\frac{n}{j}$$

化简一下得到

$\large j\leq \frac{n}{\frac{n}{i}}$

对于$m$同理，求最小值就好了。

代码

#include <cstdio>
#include <algorithm>
#define N 100010
using namespace std;
int prime[N],tot,mu[N],n,sum[N];
int a,b,c,d,k,T;
bool not_prime[N];
void get_mu(int n)
{
    mu[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!not_prime[i])
            prime[++tot]=i,mu[i]=-1;
        for (int j=1;prime[j]*i<=n;j++)
        {
            not_prime[prime[j]*i]=1;
            if (i%prime[j]==0)
            {
                mu[prime[j]*i]=0;
                break;
            }
            mu[prime[j]*i]=-mu[i];
        }
    }
    sum[0]=0;
    for (int i=1;i<n;i++)
        sum[i]=sum[i-1]+mu[i];
}
int main()
{
    int T,cs=0;
    scanf("%d",&T);
    get_mu(N);
    while(T--)
    {
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        printf("Case %d: ",++cs);
        if (!k)
        {
            printf("0\n");continue;
        }
        b/=k,d/=k;
        if (b>d) swap(b,d);
        long long ans1=0,ans2=0,last;
        for (int i=1;i<=b;i=last+1)
        {
            last=min(b/(b/i),d/(d/i));
            ans1+=(long long)(sum[last]-sum[i-1])*(b/i)*(d/i);
        }
        for (int i=1;i<=b;i=last+1)
        {
            last=b/(b/i);
            ans2+=(long long)(sum[last]-sum[i-1])*(b/i)*(b/i);
        }
        printf("%lld\n",ans1-ans2/2);
    }
}

这题其实是三倍经验题

luogu3455

luogu2522

就是改改容斥过程啥的。。

luogu3327

题意

有$T \leq 50000$次询问，给你$n,m \leq 50000$，求

$$\sum_{i=1}^n\sum_{j=1}^md(i,j)$$

其中$d(x)$为$x$的因子个数。

题解

先证一个弱弱的引理

引理

$$\sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} d(x_1 x_2 \cdots x_k) = \sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} \prod_{i=1}^{k} \left \lfloor \frac{y_i}{x_i} \right \rfloor \prod_{i < j } [gcd(x_i, x_j)=1]$$

证明

好久没有证过这么舒畅的东西了

首先对于$k=1$，就可以简化一下

$$\sum_{i}^nd(i)=\sum_{i}^n\lfloor \frac{n}{i} \rfloor[gcd(n,i)=1]$$

我们对于$n$的因子可以想一下它的贡献。它一共就计算了$n \over x$次。

现在我们对$k>1$进行归纳：

我们需要证明：

$$d_1(y_1, y_2, \cdots, y_k) = \sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} d(x_1 x_2 \cdots x_k) = f_1 (y_1, y_2, \cdots, y_k) = \sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} \prod_{i=1}^{k} \left \lfloor \frac{y_i}{x_i} \right \rfloor \prod_{i < j} [gcd(x_i, x_j)=1]$$

这样通过$y_1$来归纳一下：

当$y_1=1$时，发现是$k-1$维的证明，成立。

然后对于$y_1>1$，设一下

$$d_2(y_1, y_2, \cdots, y_k) = d_1(y_1, y_2, \cdots, y_k) – d_1(y_1-1, y_2, \cdots, y_k)$$

$$f_2(y_1, y_2, \cdots, y_k) = f_1(y_1, y_2, \cdots, y_k) – f_1(y_1-1, y_2, \cdots, y_k)$$

然后再用$y_2$归纳出$d_2=f_2$。一直做下去，直到归纳$d_{k+1}=f_{k+1}$

就需要证明这个

$$d_{k+1}(y_1, y_2, \cdots, y_k) = d(y_1 y_2 \cdots y_k) = f_{k+1}(y_1, y_2, \cdots, y_k) = \sum_{x_1|y_1} \sum_{x_2|y_2} \cdots \sum_{x_k|y_k} \prod_{i < j} [gcd(x_i, x_j)=1]$$

这样话我们就要考虑所有质因子的贡献。就可以得出了。我有一个绝妙的证明，但是懒得写

然后就直接推式子就好了
$$
\large
\begin{align}
ans& = \sum_{i=1}^{n} \sum_{j=1}^{m} d(ij) \\
& = \sum_{i=1}^{n} \sum_{j=1}^{m} \left \lfloor \frac{n}{i} \right \rfloor \left \lfloor \frac{m}{j} \right \rfloor [(i, j)=1] \\
& = \sum_{d=1}^{n} \mu(d) \sum_{i=1}^{ \left \lfloor \frac{n}{d} \right \rfloor } \sum_{j=1}^{ \left \lfloor \frac{m}{d} \right \rfloor } \left \lfloor \frac{n}{id} \right \rfloor \left \lfloor \frac{m}{jd} \right \rfloor \\
& = \sum_{d=1}^{n} \mu(d) \sum_{i=1}^{ \left \lfloor \frac{n}{d} \right \rfloor } \left \lfloor \frac{ \left \lfloor \frac{n}{d} \right \rfloor }{i} \right \rfloor \sum_{j=1}^{ \left \lfloor \frac{m}{d} \right \rfloor } \left \lfloor \frac{ \left \lfloor \frac{m}{d} \right \rfloor }{j} \right \rfloor \\
\end{align}
$$
然后就用$O(n^{1.5})$来预处理$d(x)=\sum_{i=1}^n\lfloor \frac{n}{i} \rfloor$就好了

代码

#include <cstdio>
#include <algorithm>
#define N 50010
using namespace std;
int inline read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int prime[N],tot,mu[N],n,sum[N];
int m,T;
bool not_prime[N];
long long d[N];
void get_mu(int n)
{
    mu[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!not_prime[i])
            prime[++tot]=i,mu[i]=-1;
        for (int j=1;prime[j]*i<=n;j++)
        {
            not_prime[prime[j]*i]=1;
            if (i%prime[j]==0)
            {
                mu[prime[j]*i]=0;
                break;
            }
            mu[prime[j]*i]=-mu[i];
        }
    }
    sum[0]=0;
    for (int p=1;p<=n;p++)
    {
        for (int i=1,last;i<=p;i=last+1)
            last=p/(p/i),
            d[p]+=(long long)(last-i+1)*(p/i);
        sum[p]=sum[p-1]+mu[p];
    }
}
int main()
{
    int T,cs=0;
    scanf("%d",&T);
    get_mu(50000);
    while(T--)
    {
        n=read(),m=read();
        if (n>m) swap(n,m);
        long long ans=0,last;
        for (int i=1;i<=n;i=last+1)
        {
            last=min(n/(n/i),m/(m/i));
            ans+=(long long)(sum[last]-sum[i-1])*d[n/i]*d[m/i];
        }
        printf("%lld\n",ans);
    }
}

luogu3172

地址

题意

给定区间$L,R \leq 10^9$，取区间中$n \leq 10^9$个整数，使得这些数的$gcd$为$k \leq 10^9$。

题解

还是老套路

$f(d)$为满足$gcd(x,y)=d,1\leq x\leq n,1\leq y \leq m$的方案

$F(d)$为满足$d|gcd(x,y),1\leq x \leq n,1 \leq y \leq m$的方案

可得

$$\large F(x)=\sum_{n|d}f(d)$$

考虑$F(x)$如何快速求：

对于$[L..R]$区间内的$x$倍数的个数为$d$，那么答案就是$d^n$。

那么$F(x)=(\frac{R}{x}-\frac{L-1}{x})^n$

反演

$$f(x)=\sum\limits_{x|d}\mu({d\over x})({R\over d}-{L-1\over d})^n$$

变形

$$\large f(x)=\sum_{d=1}^{r\over x}\mu(d)({{R\over x}\over d}-{{L-1\over x}\over d})^n$$

因为数据范围挺大的，直接上杜教筛。

#include <cstdio>
#include <algorithm>
#include <map>
#define N 1000005
using namespace std;
typedef long long ll;
int mod=1000000007;
int inline read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int prime[N],tot,mu[N],n,sum[N];
int m,a,k,l,r,T,maxs=1000000;
bool not_prime[N];
ll d[N];
map <int,int> ma;
void init(int n)
{
    mu[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!not_prime[i])
            prime[++tot]=i,mu[i]=-1;
        for (int j=1;prime[j]*i<=n;j++)
        {
            not_prime[prime[j]*i]=1;
            if (i%prime[j]==0)
            {
                mu[prime[j]*i]=0;
                break;
            }
            mu[prime[j]*i]=-mu[i];
        }
    }
    for (int i=1;i<=maxs;i++)
        mu[i]+=mu[i-1];
}
ll fastpow(ll x,int p)
{
    ll ans=1;
    while(p)
    {
        if (p&1)
            ans=(ans*x)%mod;
        p>>=1;
        x=(x*x)%mod;
    }
    return ans;
}
ll get_mu(int n)
{
    if (n<=maxs) return mu[n];
    if (ma.count(n)) return ma[n];
    ll temp=1;
    for (int i=2,last;i<=n;i=last+1)
        last=n/(n/i),
        temp-=get_mu(n/i)*(ll)(last-i+1);
    return ma[n]=temp;
}
int main()
{
    int T,cs=0;
    init(maxs);
    a=read(),k=read(),l=read(),r=read();
    n=r/k,m=(l-1)/k;
    //if (n>m) swap(n,m);
    ll ans=0,last;
    for (int i=1;i<=n;i=last+1)
    {
        if (m/i) last=min(n/(n/i),m/(m/i));
        else last=n/(n/i);
        ans=(ans+((ll)((get_mu(last)-get_mu(i-1))%mod)*fastpow(n/i-m/i,a))%mod)%mod;
    }
    ans=(ans%mod+mod)%mod;
    printf("%lld\n",ans);
}

bzoj2820

地址

或者做这道

题意

给出$n,m \leq 10^7$，$q \leq 10^4$次求$x \leq n,y \leq m,gcd(x,y)为质数$的$(x,y)$对数。

题解

感觉质数非常诡异啊，但是我们线性筛$\mu$的时候顺便筛出来了。

设$f(d)$为满足$gcd(x,y)=d,1\leq x\leq n,1\leq y \leq m$的$(x,y)$的对数。

根据以前的：

$$f(x)=\sum_{x|d}\mu({d \over x}){n \over d}\times {m \over d} $$

那么这个题就求(以后$p$表示质数)

$$ans=\sum_{p}^{min(n,m)}f(p)=\sum_{p}^{min(n,m)}\sum_{p|d}\mu({d \over p}){n \over d}\times {m \over d}$$

令$d={d \over p}$

$$ans=\sum_{p}^{min(n,m)}\sum_{d=1}^{min(n/p,m/p)}\mu(d){n \over dp}\times {m \over dp}$$

令$T=pd$

$$ans=\sum_{p|T}\sum_{T=1}^{min(n,m)}\mu({T \over p}) {n\over T} \times {m\over T}$$

发现后面的东西都不变

$$ans=\sum_{T=1}^{min(n,m)} {n\over T} \times {m\over T}\sum_{p|T}\mu({T \over p}) $$

现在的主要问题就是求

$$d(T)=\sum_{p|T}\mu({T \over p})$$

然后整个问题就能在$\sqrt{n}$的时间内解答

我就想到了暴力，枚举每个质数，更新他的倍数。

复杂度好像还可以？

交上去就A了

#include <cstdio>
#include <algorithm>
#define N 10000010
using namespace std;
int prime[N],tot,mu[N],n,T,m;
long long d[N];
bool not_prime[N];
void get_mu(int n)
{
    mu[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!not_prime[i])
            prime[++tot]=i,mu[i]=-1;
        for (int j=1;prime[j]*i<=n;j++)
        {
            not_prime[prime[j]*i]=1;
            if (i%prime[j]==0)
            {
                mu[prime[j]*i]=0;
                break;
            }
            mu[prime[j]*i]=-mu[i];
        }
    }
}
void get_d(int n)
{
    for (int i=1;i<=tot;i++)
        for (int j=prime[i];j<=n;j+=prime[i])
            d[j]+=mu[j/prime[i]];
    for (int i=2;i<=n;i++)
        d[i]+=d[i-1];
}
main()
{
    scanf("%d",&T);
    get_mu(10000000);
    get_d(10000000);
    while(T--)
    {
        long long ans=0;
        scanf("%d%d",&n,&m);
        if (n>m) swap(n,m);
        for (int i=1,last;i<=n;i=last+1)
        {
            last=min(n/(n/i),m/(m/i));
            ans+=(d[last]-d[i-1])*(n/i)*(m/i);
        }
        printf("%lld\n",ans);
    }
}

luogu3312

地址

题意

令$F(x)$为$i$的约数和，$q \leq 20000$次给定$n,m \leq 10^5,a \leq 10^9$求

$$\large \sum_{1 \leq i \leq n,1\leq j \leq m, F(gcd(i,j)) \leq a} F(gcd(i,j)) \bmod 2^{31}$$

题解

我觉得$a$的限制非常的恶心啊，先不去想了。

设$f(d)$为满足$gcd(x,y)=d,1\leq x\leq n,1\leq y \leq m$的$(x,y)$的对数。

那么想都不用想了：

$$ f(x)=\sum_{x|d}\mu({d \over x}){n \over d}\times {m \over d}$$

因为是表格啊，它的$x,y$都是连续的。我们知道了每个$gcd$出现的次数，$F(x)$又可以线性筛出来，就可以化一下：
$$
\begin{align}
ans&=\sum_{i=1}^{min(n,m)}F(i)f(i)\\
&=\sum_{i=1}^{min(n,m)}F(i)\sum_{i|d}\mu({d \over i}){n \over d}\times {m \over d}\\
&=\sum_{d=1}^{min(n,m)}{n \over d}\times {m \over d}\sum_{i|d}F(i)\mu({d \over i})\\
\end{align}
$$
然后把

$$g(d)=\sum_{i|d}F(i)\mu({d \over i})$$

预处理一下就可以了。这可以用上一个题的思想，枚举$i$更新倍数。

可是还有限制啊

但是我们发现对于答案有贡献的只有$F(i)\leq a$的$i$。

于是把询问按照$a$排序，把$i$按照$F(i)$排序，每次询问把$F(i)\leq a$的$i$按照原来的方式插入。

用树状数组维护前缀和就好了。

取模直接自然溢出。

#include <cstdio>
#include <algorithm>
#define N 100005
#define lowbit(x) (x&-x)
using namespace std;
struct node
{
    int fv,v;
    bool operator < (const node& a) const{return v<a.v;}
}f[N];
struct que
{
    int n,m,a,id;
    que(){}
    que(int a_,int b,int c,int d):n(a_),m(b),a(c),id(d){}
    inline bool operator<(const que& g) const{return a<g.a;}
}qu[N];
int min(int x,int y){if (x>y) return y;return x;}
int max(int x,int y){if (x<y) return y;return x;}
void swap(int &x,int &y){int t=x;x=y;y=t;}
int prime[N],tot,mu[N],n,c[N],T,m,a,mx,ans[N];
bool not_prime[N];
void get_mu(int n)
{
    mu[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!not_prime[i])
            prime[++tot]=i,mu[i]=-1;
        for (int j=1;prime[j]*i<=n;j++)
        {
            not_prime[prime[j]*i]=1;
            if (i%prime[j]==0)
            {
                mu[prime[j]*i]=0;
                break;
            }
            mu[prime[j]*i]=-mu[i];
        }
    }
    for (int i=1;i<=n;i++)
    {
        f[i].fv=i;
        for (int j=i;j<=n;j+=i)
            f[j].v+=i;
    }
}
void add(int x,int v)
{
    for (int i=x;i<=mx;i+=lowbit(i))
        c[i]+=v;
}
int query(int x)
{
    int ans=0;
    for (int i=x;i;i-=lowbit(i))
        ans+=c[i];
    return ans;
}
void solve(int n,int m,int &ans)
{
    ans=0;
    for (int i=1,last;i<=n;i=last+1)
    {
        last=min(n/(n/i),m/(m/i));
        ans+=(n/i)*(m/i)*(query(last)-query(i-1));
        ans&=0x7fffffff;
    }
}
main()
{
    scanf("%d",&T);
    for (int i=1;i<=T;i++)
    {
        scanf("%d%d%d",&n,&m,&a);
        if (n>m) swap(n,m);
        qu[i]=que(n,m,a,i);
        mx=max(n,mx);
    }
    get_mu(mx);
    sort(qu+1,qu+T+1);
    sort(f+1,f+mx+1);
    int now=0;
    for (int i=1;i<=T;i++)
    {
        while(f[now+1].v<=qu[i].a && now+1<=mx)
        {
            now++;
            for (int j=f[now].fv;j<=mx;j+=f[now].fv)
                add(j,f[now].v*mu[j/f[now].fv]);
        }
        solve(qu[i].n,qu[i].m,ans[qu[i].id]);
    }
    for (int i=1;i<=T;i++)
        printf("%d\n",ans[i]);
}

好像都刷完了，那就完结吧。撒花