UVA11426 GCD - Extreme (II)

这几天我看了 LRJ 的书看到了这一题，就把这道题写了，正好这道题挺不错的。

题目

题目PDF

知识

欧拉函数

• 定义： $\varphi(n)$ 为小于等于 $n$ 与 $n$ 互质的数的个数

它有一些有趣的性质：

• $\varphi(n)$ 是积性函数 ： 如果有 $\gcd(i,j) = 1$ 那么就有 $\varphi(i \times j) = \varphi(i) \times \varphi(j)$

如何求欧拉函数：

用一个类似于筛法求素数的方法，时间复杂度相似于埃氏筛法 $\mathcal{O}(n\log \log n)$

模板代码如下：

int phi[maxn];
void table(int n){
	for(int i = 0;i <= n;i ++)
        phi[i] = 0;
    phi[1] = 1;
    for(int i = 2;i <= n;i ++)
    	for(int j = i;j <= n;j ++){
    		if(!phi[j])		phi[j] = j;
    		phi[j] = phi[j] / i * (i-1);
    	}
   	return;
}

思路

首先，我们能想到暴力，每一次将每一个的 $\gcd$ 求出 ，最差时间复杂度为 $\mathcal{O}(n^2\log n )$ ，太慢，在这个数据目前无能为力，所以想办法优化。

设 $\large f(n) = \sum\limits_{i=1}^{n-1}\gcd(i,n)$ ，

所以答案为 $\large S(n) = \sum\limits_{i=1}^{n} f(i)$。

易证 ，$\gcd(i,n)$ 的值都是 n 的约数，我们好好看看这个柿子有什么优化的地方

设 $\dfrac{x}{i}$ ，所以 $\gcd(\dfrac{x}{i},\dfrac{n}{i}) = 1$

$\therefore$ $\dfrac{x}{i}$ 与 $\dfrac{n}{i}$ 互质

所以小于等于 $\dfrac{n}{i}$ 的互质的 $\dfrac{x}{i}$ 一共有 $\varphi(\dfrac{n}{i})$ 个

又 $\because$ $\gcd(i,n)$ $\leqslant n$

$\therefore $ $\large f(n) = \sum\limits_{i\subset A} i \times \varphi(\dfrac{n}{i})$ $( A = n$ 的约数 $)$

上面的柿子就是我们所需要的，时间复杂度与求欧拉筛法同阶。

代码 ：

#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;
const int maxn = 4000000;

long long phi[maxn],s[maxn],f[maxn];

void phi_c(){
	for(int i=2;i<=maxn;i++)	phi[i] = 0;
	phi[1] = 1;
	for(int i=2;i<=maxn;i++){
		if(!phi[i])
		for(int j=i;j<=maxn;j+=i){
			if(!phi[j])
				phi[j] = j;
				phi[j] = phi[j] / i * (i-1);
		}
	}
}

int main()
{
	phi_c();
	memset(f,0,sizeof(f));
	for(int i=1;i<=maxn;i++)
		for(int j=i*2;j<=maxn;j+=i)
			f[j] += i*phi[j/i];
			
	s[2] = f[2];
	for(int j=3;j<=maxn;j++)
		s[j] = s[j-1] + f[j];
		
	int n;
	while(scanf("%d",&n) && n)
		printf("%lld\n",s[n]);
	return 0;
}