ImOlivia_uu!

最近在学欧拉函数，数学太烂，遂写一题解。

其实这个东西是我5月底咕咕写的，但是1整月了我还没发过东西，所以我今天来把这道题补完

洛谷

---

前言

欧拉函数

不会欧拉函数

好的，欧拉函数，AKA. Euler’s totient function，AKA. $\varphi(n)$ ，表示小于等于 $n$ 和 $n$ 互质的数的个数

这个 $\varphi(n)$ 是满足积性函数的性质的：

$\gcd(a,b)==1 \rightarrow \varphi(ab)=\varphi(a)\varphi(b)$

还有一些性质：

$n=\sum_{d|n} \varphi(d)$

$n=p^k \rightarrow \varphi(n)=p^k-p^{k-1}$

$n=\prod{i=1}^{s}p_i^{k_i} \rightarrow \varphi(n)=n\times\prod{i=1}^{s}\frac{p_i-1}{p_i}$

…

重点，是如何快速求出欧拉函数

现在我们处理好数组 $p[]$，表示一个范围内的质数（可以用欧拉筛）

若对于 $i$，如果已知所有的 $1−i$ 的 $\varphi $，枚举 $<=i$的质数 $p[j]$，可以求得 $\varphi (x×p[j])$

1.若 $p[j]$ 与 $x$ 互质 $\varphi (x \times p[j])=\varphi (x)\times\varphi (p[j])$

2.若不互质，设 $x=t\times p[j]^k$

$\varphi (x \times p[j])=\varphi (t \times p[j]^{k+1})=\varphi (t) \times \varphi (p[j]^{k+1})=\varphi (t) \times \varphi (p[j]^k) \times p[j]=\varphi (x) \times p[j]$

代码

ll tot;
ll p[1000005];
bool pr[10000005];
ll phi[10000005];

void init(int n)
{
	phi[1]=1;
	for(ll i=2;i<=n;i++)
	{
		if(!pr[i])
		{
			p[++tot]=i;
			phi[i]=i-1;
		}
		for(ll j=1;j<=tot&&i*p[j]<=n;j++)
		{
			pr[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]*phi[p[j]];
			}
		}
	}
}

思路

根据题意知道：$\gcd(x,y)=p$为一个素数，因此：$\gcd(x/p,y/p)=1$，即 $x/p,y/p$ 是互质的，因此我们想到欧拉函数。

在原来板子的基础上进行一个前缀和的添加。

正常来说我们会进行一个双层枚举，枚举 $i,j$ 使得 $\gcd(i,j)=1$ 的情况，就相当于分别考虑 $i,j$ 的欧拉函数，对于 $i==j$ 的情况要减一。

代码

#include<bits/stdc++.h> 

using namespace std;

#define ll long long

ll n;

ll tot;
ll p[1000005];
bool pr[10000005];

ll phi[10000005];

void init()
{
	phi[1]=1;
	for(ll i=2;i<=n;i++)
	{
		if(!pr[i])
		{
			p[++tot]=i;
			phi[i]=i-1;
		}
		for(ll j=1;j<=tot&&i*p[j]<=n;j++)
		{
			pr[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]*phi[p[j]];
			}
		}
	}
	for(ll i=1;i<=n;i++) //前缀和
	{
		phi[i]+=phi[i-1];
	}
}

ll ans;

int main()
{	
	ios::sync_with_stdio;
	cin.tie(0),cout.tie(0);
	
	cin>>n;
	
	init();
	
	for(ll i=1;i<=tot;i++)
	{
		ans+=2*phi[n/p[i]]-1; //会重复算gcd(i,i)的情况所以-1
	}                                                  
	
	cout<<ans<<"\n";
                       
	return 0;
}                                                          

---

Abalabakabala…