HDU 6390 GUGUFISHTION

~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

2019寒假集训题

A.GUGUFISHTION

题面

给出$m,n,p$，求：$\sum_{a=1}^m\sum_{b=1}^n\frac {\phi(ab)}{\phi(a)\phi(b)}\ mod\ \ p$

Input

第一行一个$T$代表组数。

之后的$T$行，每行包含三个整数$m,n,p$。

数据保证$p$是一个质数。

Output

输出$T$行，每行只有一个整数表示答案。

Sample Input

5 7 23

Sample Output

Hint

$1\leq T \leq 3$

$1\leq m,n\leq1,000,000$

$max(m,n)< p \leq 10^9+7$

由欧拉函数的性质$\phi(p^k)=(p-1)×p^{k-1}(p为质数)$。

令$d=gcd(a,b)=p_1^{k_1}×p_2^{k_2}×…×p_n^{k_n}$。

$G_u(a,b)=\frac {\phi(a,b)}{\phi(a)\phi(b)}=\frac{\phi(p_1^{2k_1}×p_2^{2k_2}×…×p_n^{2k_n})}{\phi(p_1^{k_1}×p_2^{k_2}×…×p_n^{k_n})^2}$

由于欧拉函数为积性函数，且因为各项上下互质，展开约去。

$G_u(a,b)=\frac {(p_1-1)×(p_2-1)×(p_3-1)×…×(p_n-1)×p_1^{2k_1-1}×p_2^{2k_2-1}×…×p_n^{2k_n-1}}{(p_1-$1)^2×(p_2-1)^2×(p_3-1)^2×…×(p_n-1)^2×p_1^{k_1-1}×p_2^{k_2-1}×…×p_n^{k_n-1}}$

$=\frac {p_1×p_2×p_3×…×p_n}{(p_1-1)×(p_2-1)×…×(p_n-1)}=\frac {p_1×p_2×p_3×…×p_n×p_1^{k_1-1}×p_2^{k_2-1}×…×p_n^{k_n-1}}{(p_1-1)×(p_2-1)×(p_3-1)×…×(p_n-1)×p_1^{k_1-1}×p_2^{k_2-2}×…×p_n^{k_n-1}}$

$=\frac {p_1^{k_1}×p_2^{k_2}×…×p_n^{k_n}}{\phi(p_1^{k_1}×p_2^{k_2}×…×p_n^{k_n})}=\frac {d}{\phi{d}}$

令$a[i]=\frac i{\phi(i)}$，$f(m,n)=\sum_{a=1}^m\sum_{b=1}^nG_u(a,b)=\sum_{a=1}^m\sum_{b=1}^na×d$

$f(m,n)=\sum_{d=1}^{min(m,n)}\sum_{a=1}^m\sum_{b=1}^na[t]×[d==t]=\sum_{d=1}^{min(m,n)}\sum_{a=1}^{\lfloor \frac mt\rfloor}\sum_{b=1}^{\lfloor \frac nt\rfloor}a[t]×[d==1]$

$[到此处d的定义取消，懒得修改，写完发现不对了]$╮(╯▽╰)╭

令$g(m,n)=\sum_{a=1}^m\sum_{b=1}^n[d==1]=\sum_{a=1}^m\sum_{b=1}^n\sum_{d|gcd(a,b)}\mu(d)=\sum_{d=1}^{min(a,b)}\mu(d)×\frac md×\frac nd$

因为有：

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

$\sum_{d|n}\mu(d)=0\ \ (n>1)$

当$gcd(a,b)==1$，则$\sum_{d|gcd(a,b)}\mu(d)=1$；

当$gcd(a,b)\ !\ =1$，则$\sum_{d|gcd(a,b)}\mu(d)=0，=[gcd(a,b)==1]$。

因为$\frac md$表示在$a∈[1,m]$中能被$d$整除的数的个数，$\frac nd$表示在$b∈[1,n]$中能被$d$整除的数的个数。

所以，可证等价。

所以有$f(m,n)=\sum_{d=1}^{min(m,n)}a[t]×(\sum_{a=1}^{\lfloor \frac mt\rfloor}\sum_{b=1}^{\lfloor \frac nt\rfloor}[d==1])=\sum_{d=1}^{min(m,n)}a[t]×g(\frac mt,\frac nt)$。

时间复杂度

$\frac n1+\frac n2+\frac n3+\frac n4+…+\frac n{n-1}+\frac nn=nln(n)+C（C为欧拉函数）$

没想平均时间复杂度为$O(ln(n))$，所以总时间复杂度为$O(nln(n))$。

CODE：

因为总有$\phi(i)<i$，预处理出$max(m,n)$个逆元即可。

#include<bits/stdc++.h>
using namespace std;
long long read()
{
	long long x = 0, w = 0;
	char ch = 0;
	while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return w ? -x : x;
}
const int N = 1e6 + 10;
bool notprime[N];
int mu[N], p[N], cnt;
long long m, n, mod;
long long phi[N], a[N], inv[N];
void Prime()
{
	phi[1] = mu[1] = 1; notprime[1] = 1;
	for (int i = 2; i <= 1000000; ++i)
	{
		if (!notprime[i])
		{
			p[++cnt] = i;
			phi[i] = i - 1;
			mu[i] = -1;
		}
		for (int j = 1; j <= cnt && i * p[j] <= 1000000; ++j)
		{
			notprime[i * p[j]] = 1;
			if (i % p[j] == 0)
			{
				phi[i * p[j]] = phi[i] * p[j];
				break;
			}
			else
			{
				phi[i * p[j]] = phi[i] * (p[j] - 1);
				mu[i * p[j]] = -mu[i];
			}
		}
	}
}
void inv_work(int lim)
{
	inv[1] = 1;
	for (int i = 2; i <= lim; ++i)
		inv[i] = inv[mod % i] * (mod - mod / i) % mod;
	for (int i = 1; i <= lim; ++i)
		a[i] = inv[phi[i]] * i % mod;
}
int main()
{
	int T = read();
	Prime();
	while (T--)
	{
		m = read(), n = read(), mod = read();
		int lim = min(m, n);
		inv_work(lim);
		long long result = 0;
		for (int i = 1; i <= lim; ++i)
		{
			int pp = m / i, qq = n / i;
			long long t = 0;
			for (int j = 1; j <= min(pp, qq); ++j)
				(t += 1ll * mu[j] * (pp / j) * (qq / j) + mod) %= mod;
			(result += a[i] * t % mod) %= mod;
		}
		cout << result << endl;
	}
	return 0;
}