$f(m)=\sum\limits_{i=1}^{m-1}\sum\limits_{j=1}^{m-1}[(ij,m) \ne m]$，$g(n)=\sum\limits_{m|n}f(m)$,$1 \le n \le 10^9$，求$g(n)$模$2^{64}$。

要求为$i j ∤ m$，说明$ij$不为$m$的倍数，但是可以有公共因子，直接求很麻烦，不如先反着来求不符合的，最后再减掉。然后就是化式子，枚举一个数$(m, i)=d$，则另一个数满足$\frac{m}{d}|j$，二者各自有$\varphi(\frac{m}{d})$和$d$个数量，继续化简，之后可以观察到右半式就是某很经典的欧拉函数的结论，然后预处理素数，素因子分解计算下贡献，最后左右两个半式相减就行了。

\begin{eqnarray*} g(n) &=& \sum\limits_{m|n}(m^2-\sum\limits_{i=1}^{m-1}\sum\limits_{j=1}^{m-1}[(ij,m) = m]) \newline &=&\sum\limits_{m|n} {m^2} - \sum\limits_{m|n} \sum\limits_{d|m} d\varphi \left( \frac{m}{d} \right) \newline &=& \sum\limits_{m|n} {m^2} - \sum\limits_{d|n}d {\sum\limits_{\frac{m}{d}|\frac{n}{d}} {\varphi \left( {\frac{m}{d}} \right)} } \newline &=& \sum\limits_{m|n} {m^2} - \sum\limits_{d|n}{d \frac{n}{d}} \newline &=& \sum\limits_{m|n} {m^2} - n \sum\limits_{d|n}{1} = \sum\limits_{m|n} {m^2} - n \tau(n) \end{eqnarray*}

还有另外一种方法就是直接利用积性函数的性质，再用欧拉函数化简。得到的最后式子是一样的。

/** @Date    : 2017-10-20 14:18:28

  * @FileName: HDU 5528 反演.cppc

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL unsigned 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 = 5e4+20;

const double eps = 1e-8;

LL pri[N];

bool vis[N];

int c = 0;

void prime()

{

	MMF(vis);

	for(int i = 2; i < N; i++)

	{

		if(!vis[i]) pri[c++] = i;

		for(int j = 0; j < c && i * pri[j] < N; j++)

		{

			vis[i * pri[j]] = 1;

			if(i % pri[j] == 0) break;

		}

	}

} 

int main()

{

	prime();

	int T;

	scanf("%d", &T);

	while(T--)

	{

		LL n;

		scanf("%llu", &n);

		LL t = n;

		LL sum = 1ULL, dis = 1ULL;

		for(int i = 0; i < c && pri[i] * pri[i] <= t; i++)

		{

			if(t % pri[i] == 0)

			{

				LL cnt = 1;

				LL tmp = 1ULL;

				LL k = 1ULL;

				while(t % pri[i] == 0)

					t /= pri[i], cnt++;

				for(int j = 0; j < cnt - 1; j++)

				{

					tmp *= pri[i];

					k += (LL)tmp * tmp;// ()* m^2

				}

				sum *= k;

				dis *= cnt;

			}

		}

		if(t > 1)

		{

			sum *= t * t + 1;

			dis *= 2ULL;

		}

		dis *= n;

		printf("%llu\n", sum - dis);

	}

    return 0;

}