题目概述

令 $f(x)$ 表示 $x$ 质因数分解之后最大的次幂，$m$ 次询问，每次求 $\sum_{i=1}^{A}\sum_{j=1}^{B}f[(i,j)]$ 。

解题报告

先正常操作一下：

$$ \sum_{i=1}^{A}\sum_{j=1}^{B}f[(i,j)]=\sum_{T=1}^{min\{A,B\}}\lfloor{A\over T}\rfloor\lfloor{B\over T}\rfloor\sum_{k|T}f(k)\mu({T\over k}) $$

上面是谁都会环节，我用调和级数算 $H(T)=\sum_{k|T}f(k)\mu({T\over k})$ 然后果断GG，想线性筛发现这并不是积性函数，就搞不来了……于是膜PoPoQQQ！

大概就是说考虑 $\mu({T\over k})$ ，会发现 $k$ 的每一个素数都不能和 $T$ 相差 $>1$ ，否则就没有贡献了。

因此决定 $f(k)$ 的是 $T$ 中次幂最大的那些素数，此时有两种情况：

1. 所有素数的次幂不都相等

   • 此时决定 $\mu({T\over k})$ 的是次幂不是最大的素数的选取情况（每个素数只有两种情况：相同和 $-1$ ），显然选取的奇偶情况相同（一个奇数的状态反一下变成偶数），所以这种情况没有贡献。

2. 所有素数的次幂相等

   • 此时次幂最大的素数的选取情况同时决定了 $f(k)$ 和 $\mu({T\over k})$ ，只有一种特殊情况：$k$ 的每个素数都比 $T$ 少选一个，此时 $f(k)$ 为 $T$ 中最大次幂 $MAX-1$ ，反过来时 $\mu$ 变号，但是 $f$ 不是 $MAX-1$ 而是 $MAX$ ，所以有 $-1\mu({T\over k})$ 的贡献，其他情况则同第一种情况互相抵消。

因此可以用线性筛来处理出 $H(T)$ ，只需要讨论 $T$ 的所有素数的次幂是否相同即可。为了实现这个，需要记录 $num_i$ 表示 $i$ 的最小素数 $p_i$ 的次幂以及 $pw_i=p_i^{num_i}$ 。从而获得 $i$ 去除最小素数后的数来讨论。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=10000000;

int te,n,m,p[maxn+5],D[maxn+5],pw[maxn+5],num[maxn+5],H[maxn+5];bool pri[maxn+5];LL ans;

inline void Make(){
    for (int i=2;i<=maxn;i++){
        if (!pri[i]) p[++p[0]]=i,H[i]=1,pw[i]=i,num[i]=1;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=maxn;j++)
            if (i%p[j]) pri[t]=true,pw[t]=p[j],num[t]=1,H[t]=(num[i]==1?-H[i]:0); else{
                pri[t]=true;pw[t]=pw[i]*p[j];num[t]=num[i]+1;
                H[t]=(t==pw[t])?1:(num[t]==num[t/pw[t]]?-H[t/pw[t]]:0);break;
            }
    }for (int i=1;i<=maxn;i++) H[i]+=H[i-1];
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (Make(),scanf("%d",&te);te;te--){
        scanf("%d%d",&n,&m);ans=0;
        for (int l=1,r;l<=n&&l<=m;l=r+1)
            r=min(n/(n/l),m/(m/l)),ans+=(LL)(H[r]-H[l-1])*(n/l)*(m/l);
        printf("%lld\n",ans);
    }return 0;
}