2818: Gcd

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 9108  Solved: 4066

[Submit][Status][Discuss]

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(x,y)=prime[i];

gcd(x/prime[i],y/prime[i])=1;

求每个数的欧拉值再用前缀和记录该数前所有互质对数sum[i];

枚举1~n/prime[i]有多少对互质对数然后将x,y互换的情况加起来即可(注:gcd(1,1)出现两次，所以要减1次)

#include<iostream>

#include<stdio.h>

#define ll long long

using namespace std;

const int maxn=1e7+7;

bool mark[maxn];

ll prime[maxn],phi[maxn],sum[maxn];

void eular(int n){//线性筛选求欧拉值

        int cnt=0;

        phi[1]=1;

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

                if(!mark[i])

                        prime[cnt++]=i,phi[i]=i-1;

                for(int j=0;j<cnt&&i*prime[j]<=n;j++){

                        mark[i*prime[j]]=1;

                        if(i%prime[j])//互质

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

                        else{//不互质

                                phi[i*prime[j]]=phi[i]*prime[j];//原因：该质数已存在则不用乘(1-1/prime[j]);

                                break;//防止重复增加时间

                        }

                }

        }

}

int main()

{

        int n;

        scanf("%d",&n);

        eular(n);

        ll ans=0;

        for(int i=1;i<=n;i++)//i之前所有互质对数

                sum[i]=sum[i-1]+phi[i];

        for(int i=0;prime[i]&&prime[i]<=n;i++)//gcd(x/prime[i],y/prime[i])=1，x,y互换并减去(1,1)重复的情况

                ans+=sum[n/prime[i]]*2-1;

        printf("%lld\n",ans);

        return 0;

}