AcWing 220. 最大公约数 | 欧拉函数

2021-02-08 05:15

阅读：698

标签：closed long || lld 题目 lan data- 范围 event

传送门

题目描述

给定整数N，求1

GCD(x,y)即求x，y的最大公约数。

输入格式

输入一个整数N

输出格式

输出一个整数，表示满足条件的数对数量。

数据范围

$1 \leq N \leq 10^{7}$

输入样例：

输出样例：

题解：本题要求1题目就变成了求\[\sum_{p是素数}^{p≤n} 2*\sum_{i=1}^{n/p}φ(i) -1\] 也可以用\[\sum_{p是素数}^{p≤n} 2*\sum_{i=2}^{n/p}φ(i) +1\]。

代码：

#include using namespace std;
#define ll long long
const int N = 1e7 + 10;
int v[N],prime[N];
ll sum[N],phi[N];
int cnt = 0;
int main() {
    int n;
    scanf("%d",&n);
    phi[1]=1;
    for (int i = 2; i ) {
        if(!v[i]) {
            v[i] = i;prime[cnt++] = i;
            phi[i] = i-1;
        }
        for (int j = 0; j ) {
            if (prime[j] > v[i] || prime[j] > n/i) break;
            v[i*prime[j]] = prime[j];
            phi[i*prime[j]] = phi[i] * (i%prime[j]?prime[j]-1:prime[j]);
        }
    }
    for (int i = 1; i ) 
        sum[i] = sum[i-1]+phi[i];
    ll ans = 0;
    for (int i = 0; i ) {
        int num = n/prime[i];
        ans += 2*sum[num]-1;
    }
    printf("%lld\n",ans);
    return 0;
}

View Code

AcWing 220. 最大公约数 | 欧拉函数

标签：closed long || lld 题目 lan data- 范围 event

原文地址：https://www.cnblogs.com/l999q/p/11367956.html

上一篇：TabPanel美化控件----------WinForm控件开发系列

下一篇：温度计控件----------WinForm控件开发系列

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 220. 最大公约数 | 欧拉函数
文章链接：http://soscw.com/index.php/essay/52492.html

亲，登录后才可以留言！

AcWing 220. 最大公约数 | 欧拉函数

题目描述

输入格式

输出格式

数据范围

输入样例：

输出样例：

评论

热门文章

推荐文章

最新文章

置顶文章