$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求$\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}f((i,j))$

先简化。

\begin{eqnarray*} \sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}f((i,j)) &=& \sum_{d=1}^{min(a,b)}\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}f(d)[(i,j)=d] \newline &=& \sum_{d=1}^{min(a,b)}\sum\limits_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{a}{d} \rfloor}f(d)[(i,j)=1] \newline &=& \sum\limits_{

{\rm{d = 1}}}^{\min (a,b)} {\sum\limits_{i = 1}^{\left\lfloor {\frac{a}{d}} \right\rfloor } {\sum\limits_{j = 1}^{\left\lfloor {\frac{b}{d}} \right\rfloor } {\sum\limits_{k|(i,j)}^{} {\mu (k)f(d)} } } } \newline  &=& \sum\limits_{d = 1}^{\min (a,b)} {\sum\limits_{k = 1}^{\min (\left\lfloor {\frac{a}{d}} \right\rfloor ,\left\lfloor {\frac{b}{d}} \right\rfloor )} {f(d)\mu (k)} \left\lfloor {\frac{a}{

{kd}}} \right\rfloor \left\lfloor {\frac{b}{

{kd}}} \right\rfloor }  \newline &=& \sum\limits_{T = kd = 1}^{\min (a,b)} {\sum\limits_{d|T}^{} {f(d)\mu (\frac{T}{d})} \left\lfloor {\frac{a}{T}} \right\rfloor \left\lfloor {\frac{b}{T}} \right\rfloor } \newline \end{eqnarray*}

所以只要能够预处理出$\sum\limits_{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$互为相反数而相消。

故最后$\sum\limits_{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 
    
     #define LL long long#define PII pair
     
      #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<<"~~"<
      > 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\n", ans);	}    return 0;}