「Luogu P2568」 GCD

题目描述

给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对.

输入输出格式

输入格式:

一个整数N

输出格式:

答案

输入输出样例

输入样例#1: 复制

4

输出样例#1: 复制

4

说明

对于样例\((2,2),(2,4),(3,3),(4,2)\)\(1<=N<=10^7\)
来源:bzoj2818
本题数据为洛谷自造数据,使用CYaRon耗时5分钟完成数据制作。

思路

\[gcd(x, y)=p\]
\[gcd(x/p, y/p)=1\]
故筛素数的时候记录一下素数,欧拉函数,欧拉函数前缀和,之后遍历\(x/p\)即可。

代码

#include <iostream>
#include <cstdio>
using namespace std;

bool isn_pri[10000010];
int pri[5000010], phi[10000010];
long long sum[10000010], cnt, ans, n;

void judge(){
    for(int i=2; i<=n; i++){
        if(!isn_pri[i])
            pri[++cnt]=i, phi[i]=i-1;
        for(int j=1; j<=cnt&&i*pri[j]<=n; j++){
            isn_pri[i*pri[j]]=true;
            if(i%pri[j]==0){
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }else
                phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
        sum[i]=sum[i-1]+phi[i];
    }
}
int main(){
    scanf("%lld",&n);
    judge();
    for(int i=1; i<=cnt; i++)
        ans+=sum[n/pri[i]]*2+1;
    cout<<ans<<endl;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注