傳送門
2818: Gcd
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 3649 Solved: 1605
[Submit][Status][Discuss]
Description
給定整數N，求1<=x,y<=N且Gcd(x,y)為素數的
數對(x,y)有多少對.
Input
1個整數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)==素數的個數(2,4)和(4,2)認為是不1樣的，那末我們可以想到枚舉每個素數，讓其GCD(x,y)=p,那末我們可以想到在[1,y/p]內與y/p互素的個數（在這里默許 y>x），那末我們就是求1個歐拉函數值，那末我們將其擴大到1-n區間內，就是求[1,n/p]的歐拉函數值，但是我們需要求的是sigmaEualr(n/p)的前綴和，由于y是從1-n之間取的，所以對數就是sum[n/p]*2⑴,由于是對數，而且還有重復的情況（本身是素數的情況）
具體詳見代碼：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long LL;
const LL MAXN = 1e7+5;
bool prime[MAXN];///標記數組是否是素數
LL phi[MAXN];///歐拉函數值，i的歐拉函數值=phi[i]
LL p[MAXN];///素因子的值
LL cnt = 0;
void get_Phi()///篩法求歐拉函數
{
cnt = 0;
memset(prime, true, sizeof(prime));
phi[1] = 1;
for(LL i=2; i<MAXN; i++)///線性篩法
{
if(prime[i])///素數
{
p[cnt++] = i;
phi[i] = i-1;///素數的歐拉函數值是素數 - 1
}
for(LL j=0; j<cnt; j++)
{
if(i*p[j] > MAXN)
break;
prime[i*p[j]] = false;///素數的倍數，所以i*p[j]不是素數
if(i%p[j] == 0)///性質：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網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
