$n=p_1^{a_1}p_2^{a_2}…p_k^{a_k}，p_i$为素数，定义$f(n)=max(a_1,a_2…,a_k)$。
给定a,b<=1e7求$sumlimits_{i=1}^{a}sumlimits_{j=1}^{b}f((i,j))$
先简化。
egin{eqnarray*} sumlimits_{i=1}^{a}sumlimits_{j=1}^{b}f((i,j)) &=& sum_{d=1}^{min(a,b)}sumlimits_{i=1}^{a}sumlimits_{j=1}^{b}f(d)[(i,j)=d] ewline &=& sum_{d=1}^{min(a,b)}sumlimits_{i=1}^{lfloor frac{a}{d} floor}sumlimits_{j=1}^{lfloor frac{a}{d} floor}f(d)[(i,j)=1] ewline &=& sumlimits_{{ m{d = 1}}}^{min (a,b)} {sumlimits_{i = 1}^{leftlfloor {frac{a}{d}} ight floor } {sumlimits_{j = 1}^{leftlfloor {frac{b}{d}} ight floor } {sumlimits_{k|(i,j)}^{} {mu (k)f(d)} } } } ewline &=& sumlimits_{d = 1}^{min (a,b)} {sumlimits_{k = 1}^{min (leftlfloor {frac{a}{d}} ight floor ,leftlfloor {frac{b}{d}} ight floor )} {f(d)mu (k)} leftlfloor {frac{a}{{kd}}} ight floor leftlfloor {frac{b}{{kd}}} ight floor } ewline &=& sumlimits_{T = kd = 1}^{min (a,b)} {sumlimits_{d|T}^{} {f(d)mu (frac{T}{d})} leftlfloor {frac{a}{T}} ight floor leftlfloor {frac{b}{T}} ight floor } ewline end{eqnarray*}
所以只要能够预处理出$sumlimits_{d|T} {f(d)mu (frac{T}{d})}$就能分块了。
注意观察该函数，根据$f()$取素因子次数的最大值及$mu()$数论意义上的容斥性质，可以发现当$a_i$的值都一样时，才存在一个次数的组合使$frac{T}{d}=p_1^{1}p_2^{1}…p_k^{1}$值无法被消去，因为它的$f()$值要比对称的组合$f(p_1^{0}p_2^{0}…p_k^{0})$大1，而其他的所有组合都可找到一个素因子数量对称的组合使得两者的$mu$互为相反数而相消。
故最后$sumlimits_{d|T} {f(d)mu (frac{T}{d})}=(-1)^{k+1}$
线性筛里处理数论函数。预处理其前缀和就好了。
/** @Date : 2017-09-28 21:09:51
* @FileName: bzoj 3309 反演.cpp
* @Platform: Windows
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version : $Id$
*/
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int ,int>
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e6+20;
const double eps = 1e-8;
int c = 0;
bool vis[N*10];
int pri[N];
int cnt[N*10];
int k[N*10];
int f[N*10];
void prime()
{
MMF(vis);
for(int i = 2; i < 10000010; i++)
{
if(!vis[i])
{
pri[c++] = i;
cnt[i] = 1;
k[i] = i;//最小的素因子对应的幂
f[i] = 1;
}
for(int j = 0; j < c && i * pri[j] < 10000010; j++)
{
vis[i * pri[j]] = 1;
if(i % pri[j] == 0)//倍数
{
cnt[i * pri[j]] = cnt[i] + 1;//最小质因子次数+1
k[i * pri[j]] = k[i] * pri[j];//幂增大1次
int tmp = i / k[i];//除去该因子的幂
if(tmp == 1)
f[i * pri[j]] = 1;//说明只有一个因子
else f[i * pri[j]] = (cnt[tmp]==cnt[i * pri[j]]?-f[tmp]:0);//判断次数是否相同
break;
}
else
{
cnt[i * pri[j]] = 1;//首次出现默认次数为1
k[i * pri[j]] = pri[j];//
f[i * pri[j]] = (cnt[i]==1?-f[i]:0);
}
/*getchar();
cout << i<<"~~"<<i * pri[j] << "~"<<k[i * pri[j]] <<endl;
cout << cnt[i * pri[j]] << endl;*/
}
}
for(int i = 1; i < 10000010; i++)
f[i] += f[i - 1];
}
int main()
{
int T;
prime();
cin >> T;
while(T--)
{
LL a, b;
scanf("%lld%lld", &a, &b);
if(a > b)
swap(a, b);
LL ans = 0;
for(int i = 1, last; i <= a; i = last + 1)
{
last = min(a/(a/i), b/(b/i));
ans += (a / i) * (b / i) * (f[last] - f[i - 1]);
}
printf("%lld
", ans);
}
return 0;
}