P 2568 GCD

对于这道题，我们要求的是 \(\displaystyle \sum_{i=1}^{N}\sum_{j = 1} ^{N}\) gcd(i,j)为质数

首先我们很容易想出来怎么打暴力，我们可以对于每个 i 和 j 都求一遍他们的gcd 最后累计一下gcd为质数的就完成了。

可是这样得神仙时间复杂度为O（n^2）, 对于这道题，我们肯定会 TLE。

然后我们只能苦逼的想正解QAQ

然后就开始我们的推柿子时间QAQ

我们考虑这样一个柿子

gcd(x,y) = p

那么这个柿子可以写成 gcd(x' * p , y' * p) = p

提出p来就可以变成 gcd(x',y') = 1; x' = x / p ,y' = y / p ;

这个柿子是不是很熟悉QAQ

gcd(i,j) = 1 不就相当于 \(\displaystyle\sum_{i=1}^{N}\varphi(i)\)

因为对于每个j 我们要算有多少个i满足 1 <= i < j 并且 gcd（i,j） = 1。这样的i的数量恰好是

\(\displaystyle\varphi(j)\)

不会的童鞋请看仪仗队那个题。。。

那么我们考虑每个p的贡献，我们要强制把上面的柿子乘以二，在减去一。

乘以二其实很简单，因为他每个点（i,j）等同于（j,i）这个点，因此我们要强制乘二。

减一呢是因为当 x' = y' = 1 时，即当 x = y = p的时候这个点算了两遍，但（x,y）(x=y)这个数对

只有一个所以要减一。

综上对于每个p，他的贡献就是 \(\displaystyle\sum_{i=1}^{N\over p}\varphi(i)\) *2 -1.

那么有多少个这样的p呢？？？

其实p就是N以内的质数，对于每个p，求一下他的贡献，在相加，不就可以轻松AC了吗QAQ。。。

那么最后的总柿子就是

\(\displaystyle\sum_{p}\sum_{i=1}^{N\over p}\) φ（i）-1 （ p 是1~n的质数）

优化我们再求p的贡献时，不必要一个个的去求欧拉函数的值，我们可以考虑维护

一下前缀和。这样就会减少不少时间了...

最后附上我的代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int N = 1e7+10;

long long n,ans = 0,cnt;

long long prime[N] ,phi[N], tot[N];

bool check[N];

void calc(int n){//边进行欧拉筛，边求欧拉函数

     memset(check,-1,sizeof(check));

     phi[1] = 1;

     for(int i = 2; i <= n; i++){

     	if(check[i]){

     		phi[i] = i-1;

     		prime[++cnt] = i;

     	}

     	for(int  j = 1; j <= cnt; j++){

     		if(i * prime[j] > n) break;

     		check[i*prime[j]] = 0;

     		if(i % prime[j] == 0){

     			phi[i*prime[j]] = phi[i] * prime[j];

     			break;

     		}

     		else{/积性函数性质

     			phi[i*prime[j]] = phi[i] * phi[prime[j]];

     		}

     	}

     }

     for(int i = 1; i <= n; i++) tot[i] = tot[i-1] + phi[i];//前缀和

}

int main(){

    scanf("%d",&n);

    calc(n);

    for(int i = 1; i <= cnt; i++){//枚举每个p

    	ans += 2 * tot[n/prime[i]] - 1;//求p的贡献

    }

    printf("%d\n",ans)

    return 0;

}

本蒟蒻码风过丑，不喜勿喷。。。。

//手敲不易，点个吧

最后完美结束，✿✿ヽ(°▽°)ノ✿ QAQ 。。。

巴特西

P 2568 GCD

然后就开始我们的推柿子时间QAQ

gcd(x,y) = p

最新文章

热门文章