Description
给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.
Input
一个整数N
Output
如题
Sample Input
4
Sample Output
4
HINT
hint
对于样例(2,2),(2,4),(3,3),(4,2)
1<=N<=10^7
思路
最近看了很多关于gcd和mod的题目。
通过最近几道题目了解了很多=。=
首先有这么一个性质：如果a∈[1,n]，b∈[1,m]，那么gcd(a,b)|k的有(n/k)*(m/k)组。
那么令f[x]为gcd(a,b)==k的组数，f[k]=(n/k)*(m/k)-f[2k]-f[3k]-f[4k]……
对于这一题来说。。好像是并不可以过的。
那么就有别的性质：
如果a,b∈[1,n]，gcd(a,b)==k的组数等价于a,b∈[1,n/k]，gcd(a,b)==1的组数。
这就很好求了吧，就是1->n的phi值之和（欧拉函数）*2-1。
首先每组数必须要算两遍，比如(3,5)和(5,3)，所以要*2。然后(1,1)不要算两遍，所以再-1。
然后就是如何求出1-n中所有的质数以及欧拉函数了。现场学习线性筛。。
其实我完全不理解啊。。先记住好了。。核心代码如下:
phi[]=;memset(is_prime,true,sizeof(is_prime));
for(int i=;i<=n;i++){
if (is_prime[i]){
phi[i]=i-;
prime[++cnt]=i;
}
for(int j=;j<=cnt&&i*prime[j]<=n;j++){
is_prime[i*prime[j]]=false;
if (i%prime[j]!=) phi[i*prime[j]]=phi[i]*(prime[j]-);
else{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
}
}
线性筛
应该没写错吧。。为了加强记忆默写的。。如果有问题就看下面的那个版本吧，那个是AC了的。
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
///==============struct declaration============== ///==============var declaration=================
const int MAXN=;
int n,tot=,ans=;
int prime[MAXN];
long long phi[MAXN];
bool is_prime[MAXN];
///==============function declaration============
void Init();
///==============main code=======================
int main()
{
//#define FILE__
#ifdef FILE__
freopen("input","r",stdin);
freopen("output","w",stdout);
#endif
scanf("%d",&n);
Init();
for(int i=;i<=n;i++) phi[i]+=phi[i-];
long long ans=;
for(int i=;i<=tot;i++)
ans+=phi[n/prime[i]]*-;
printf("%lld\n",ans);
return ;
}
///================fuction code====================
void Init(){
memset(is_prime,true,sizeof(is_prime));phi[]=;
for(int i=;i<=n;i++){
if (is_prime[i]){
phi[i]=i-;
prime[++tot]=i;
}
for(int j=;j<=tot;j++){
if (i*prime[j]>n) break;
is_prime[i*prime[j]]=false;
if (i%prime[j]==){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else
phi[i*prime[j]]=phi[i]*(prime[j]-);
}
}
}
BZOJ2818
不要问我那些性质是为什么。。我也布吉岛(╯‵□′)╯︵┻━┻