luogu P2568 题解

description

求 \(\sum\limits_{x=1}^{n} \sum\limits_{y=1}^{n} [\gcd(x,y)\in \mathbb{P}]\)

\(\mathbb{P}\) 为素数集合

\(n \leq 10^7\)

solution

\(\begin{aligned} ans & = \sum\limits_{x=1}^{n} \sum\limits_{y=1}^{n} [\gcd(x,y)\in \mathbb{P}]\\ & = \sum\limits_{p\in \mathbb{P}} \sum\limits_{x=1}^{n} \sum\limits_{y=1}^{n} [\gcd(x,y)=p] \\ & = \sum\limits_{p\in \mathbb{P}} \sum\limits_{x=1}^{\left\lfloor\frac{n}{p}\right\rfloor} \sum\limits_{y=1}^{\left\lfloor\frac{n}{p}\right\rfloor} [\gcd(x,y)=1]\\ \end{aligned}\)

式子右边画图出来是一个方阵。为了利用欧拉函数，我们先取它的一半，然后乘 2 变回去，再减去重叠部分（此处只有 \(x=1,y=1\) 这种情况会被计算两次，所以减 1）。

\(\begin{aligned}\\ ans & = \sum\limits_{p\in \mathbb{P}} 2\times\left(\sum\limits_{x=1}^{\left\lfloor\frac{n}{p}\right\rfloor} \sum\limits_{y=1}^{x} [\gcd(x,y)=1]\right) -1\\ &= \sum\limits_{p\in \mathbb{P}} 2\sum\limits_{x=1}^{\left\lfloor\frac{n}{p}\right\rfloor} \varphi(x) -1\\ \end{aligned}\)

\(\varphi()\) 的前缀和可以 \(\mathcal{O}(n)\) 预处理，顺便筛出素数。然后求和就好了。

code

#include<bits/stdc++.h>

using namespace std;

const int N=10000010;

bitset<N> st;
vector<int> primes;
int n;
long long phis[N];

void get_primes(int n){
	phis[1]=1;
	for(int i=2; i<=n; i++){
		if(!st[i]){
			primes.push_back(i);
			phis[i]=i-1;
		}
		for(auto j:primes){
			if(i*1ll*j>n) break;
			st[i*j]=1;
			if(i%j==0){
				phis[i*j]=phis[i]*j;
				break;
			}
			phis[i*j]=phis[i]*phis[j];
		}
	}
}

int main(){
	
	cin>>n;
	
	get_primes(n);
	for(int i=2; i<=n; i++) phis[i]+=phis[i-1];
	
	long long ans=0;
	for(auto p:primes){
		ans=ans+2*phis[n/p]-1;
	}
	cout<<ans<<endl;
	
	return 0;
}