傳送門
2818: Gcd
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 3649 Solved: 1605
[Submit][Status][Discuss]
Description
給定整數(shù)N，求1<=x,y<=N且Gcd(x,y)為素數(shù)的
數(shù)對(x,y)有多少對.
Input
1個整數(shù)N
Output
如題
Sample Input
4
Sample Output
4
HINT
hint
對樣例(2,2),(2,4),(3,3),(4,2)
1<=N<=10^7
Source
湖北省隊互測
解題思路：
這個題是讓求的<=n的GCD(x,y)==素數(shù)的個數(shù)(2,4)和(4,2)認(rèn)為是不1樣的，那末我們可以想到枚舉每個素數(shù)，讓其GCD(x,y)=p,那末我們可以想到在[1,y/p]內(nèi)與y/p互素的個數(shù)（在這里默許 y>x），那末我們就是求1個歐拉函數(shù)值，那末我們將其擴(kuò)大到1-n區(qū)間內(nèi)，就是求[1,n/p]的歐拉函數(shù)值，但是我們需要求的是sigmaEualr(n/p)的前綴和，由于y是從1-n之間取的，所以對數(shù)就是sum[n/p]*2⑴,由于是對數(shù)，而且還有重復(fù)的情況（本身是素數(shù)的情況）
具體詳見代碼：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long LL;
const LL MAXN = 1e7+5;
bool prime[MAXN];///標(biāo)記數(shù)組是否是素數(shù)
LL phi[MAXN];///歐拉函數(shù)值，i的歐拉函數(shù)值=phi[i]
LL p[MAXN];///素因子的值
LL cnt = 0;
void get_Phi()///篩法求歐拉函數(shù)
{
cnt = 0;
memset(prime, true, sizeof(prime));
phi[1] = 1;
for(LL i=2; i<MAXN; i++)///線性篩法
{
if(prime[i])///素數(shù)
{
p[cnt++] = i;
phi[i] = i-1;///素數(shù)的歐拉函數(shù)值是素數(shù) - 1
}
for(LL j=0; j<cnt; j++)
{
if(i*p[j] > MAXN)
break;
prime[i*p[j]] = false;///素數(shù)的倍數(shù)，所以i*p[j]不是素數(shù)
if(i%p[j] == 0)///性質(zhì)：i mod p == 0, 那末 phi(i * p) == p * phi(i)
{
phi[i*p[j]] = p[j] * phi[i];
break;
}
else
phi[i*p[j]] = (p[j]-1) * phi[i];///i mod p != 0, 那末 phi(i * p) == phi(i) * (p⑴)
}
}
}
LL sum[MAXN];///前綴和
void get_sum()
{
memset(sum, 0, sizeof(sum));
for(LL i=1; i<MAXN; i++)
sum[i] = sum[i-1]+phi[i];
}
int main()
{
get_Phi();
get_sum();
LL n;
while(~scanf("%lld",&n))
{
LL ans = 0;
for(LL i=0; i<cnt&&p[i]<=n; i++)
{
ans = ans+sum[n/p[i]]*2-1;
}
printf("%lld\n",ans);
}
return 0;
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權(quán)所有
