实用工具小学数学练习字帖生成在线画板函数绘制拼音字母表在线词典黄历查询中国历史 Excel函数模拟请求 json格式化

栏目分类:

子分类:

名师互学网

名师互学网用户登录

快速导航

当前搜索

当前分类

前沿技术软件开发系统运维产品运营生活办公面试经验考试题库

实用工具

学习工具小学数学练习字帖生成在线画板函数绘制拼音字母表在线词典黄历查询亲戚关系计算安全期计算中国历史 Excel函数模拟请求 json格式化浏览器指纹

名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

220. 最大公约数欧拉函数公式化简

C/C++/C# 更新时间：2026-05-21 16:44:55 发布时间：1687天前 IT归档最新发布模块sitemap 名妆网法律咨询聚返吧英语巴士网伯小乐网商动力

题目

题解思路

首先化简成下面这样。

对于每个素数P都有一个1 N/P的区间让 a/p 和 b/p，我们只要算出区间内互质数的数对，枚举每个素数求和就是答案。
由欧拉函数可以求得1 到 N 中与N互质的数的个数对其求前缀和，就是数对的一半了，这里a b 是可以交换的。（当 a b 相等为 p 的时候就不能了）

参考文章

AC代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const  int  INF =  0x3f3f3f3f;
const  int  N = 1e7 + 10 ;

bool st [ N ] ;
int  prm[ N ] ;
int  hi[ N ] ;
long long  sum[ N ] ;
int cnt = 1 ;

void in (int  n )
{
    cnt = 1 ;
    st[1] = 1 ;
    hi[1] = 1 ;
    for (int i = 2 ; i <= n ; i++ )
    {
        if ( ! st[i] )
        {
            prm[cnt] = i ;
            cnt++ ;
            hi[i] = i - 1 ;
        }
        for (int j = 1 ; i*prm[j] <= n ; j++ )
        {
            st[i*prm[j]] = 1 ;
            if ( i % prm[j] == 0 )
            {
                hi[i*prm[j]] = hi[i] * prm[j] ;
                break;
            }
            hi[ i*prm[j] ]  = hi[i] * ( prm[j] - 1 ) ;
        }
    }
}


int main ()
{
    ios::sync_with_stdio(false);
    int n ;
    cin >> n ;
    in(n);
    long long re = 0 ;
    for (int i = 1 ; i <= n ; i++ )
    {
        sum[i] = sum[ i-1 ] + hi[i] ;
    }
    for (int i = 1 ; i < cnt ; i++ )
    {
        int p = prm[i] ;
        re += 2*sum[ n / p ] - 1 ;
    }
    cout << re << "n" ;
    return 0 ;
}

转载请注明：文章转载自 www.mshxw.com

本文地址：https://www.mshxw.com/it/298282.html

上一篇 leetcode 576. Out of Boundary Paths | 576. 出界的路径数（暴力递归-＞傻缓存-＞dp）

下一篇 2021-10-05

C/C++/C#相关栏目本月热门文章

热门相关搜索

路由器设置木托盘宝塔面板儿童python教程心情低落朋友圈 vim 双一流学科专升本我的学校日记学校西点培训学校汽修学校情书化妆学校塔沟武校异形模板西南大学排名最精辟人生短句 6步教你追回被骗的钱南昌大学排名清朝十二帝北京印刷学院排名北方工业大学排名北京航空航天大学排名首都经济贸易大学排名中国传媒大学排名首都师范大学排名中国地质大学(北京)排名北京信息科技大学排名中央民族大学排名北京舞蹈学院排名北京电影学院排名中国戏曲学院排名河北政法职业学院排名河北经贸大学排名天津中德应用技术大学排名天津医学高等专科学校排名天津美术学院排名天津音乐学院排名天津工业大学排名北京工业大学耿丹学院排名北京警察学院排名天津科技大学排名北京邮电大学(宏福校区)排名北京网络职业学院排名北京大学医学部排名河北科技大学排名河北地质大学排名河北体育学院排名

关于我们文章归档网站地图联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号：晋ICP备2021003244-6号