数学:求欧拉函数算法模板-程序员宅基地

技术标签: 算法  C++  基础算法  数论  欧拉函数  数学  

数学:求欧拉函数算法模板


求欧拉函数

int phi(int x)
{
    
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
    
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

筛法求欧拉函数

int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


void get_eulers(int n)
{
    
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
    
        if (!st[i])
        {
    
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
    
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
    
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

本模板来自:AcWing算法基础课

相关博客:数学知识:欧拉函数


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_52156445/article/details/118887266

智能推荐

通用存储过程分页(top max模式)版本(性能相对之前的not in版本极大提高) _top 搭配not in 性能-程序员宅基地

文章浏览阅读1.3k次。 --/*-----存储过程 分页处理 孙伟 2005-03-28创建 -------*/--/*----- 对数据进行了2分处理使查询前半部分数据与查询后半部分数据性能相同 -------*/--/*-----存储过程 分页处理 孙伟 2005-04-21修改 添加Distinct查询功能-------*/--/*-----存储过程 分页处理 孙伟 2005-05-18修改 多字段排序规则问题-_top 搭配not in 性能

vue新玩法VueUse-工具库@vueuse/core-程序员宅基地

文章浏览阅读1.5w次,点赞3次,收藏10次。VueUse官方链接一、什么是VueUseVueUse不是Vue.use !!!它是一个基于 Composition API 的实用函数集合,下面是具体的一些用法二、如何引入import { 具体方法 } from ‘@vueuse/core’三、下面来看看一些具体的用法1、useMouse:监听当前鼠标坐标的一个方法,他会实时的获取鼠标的当前的位置2、usePreferredDark:判断用户是否喜欢深色的方法,他会实时的判断用户是否喜欢深色的主题3、useLocalStorage:数据_vueuse/core

统计学5大基本概念,建议收藏!(文末送书)-程序员宅基地

文章浏览阅读736次。转自:爱数据LoveD大家好,我是小z,也可以叫我阿粥~今天给大家分享一波统计学重要概念,顺便前排提示文末送书~从高的角度来看,统计学是一种利用数学理论来进行数据分析的技术。象柱状图这种基本的可视化形式,会给你更加全面的信息。但是,通过统计学我们可以以更富有信息驱动力和针对性的方式对数据进行操作。所涉及的数学理论帮助我们形成数据的具体结论,而不仅仅是猜测。利用统计学,我们可以更深入、更细致地观察数..._统计学五大基本原理

Java多线程4:synchronized的使用场景和原理简介_synchronized常见使用场景 threadsyntest.new myrunnable3-程序员宅基地

文章浏览阅读2.4k次,点赞3次,收藏9次。一、synchronized使用1.1 synchronized介绍在多线程并发编程中synchronized一直是元老级角色,很多人都会称呼它为重量级锁。但是,随着Java SE 1.6对synchronized进行了各种优化之后,有些情况下它就并不那么重了。synchronized可以修饰普通方法,静态方法和代码块。当synchronize..._synchronized常见使用场景 threadsyntest.new myrunnable3

Windows python用impyla连接远程Hive数据库_python impyla demo-程序员宅基地

文章浏览阅读260次。安装下述包:thirftpythirft-saslthirftpure-sasl(卸载sasl,若要用pyhive,sasl轮子安装路径Link)impyla# -*- coding:UTF-8 -*-from impala.dbapi import connect#下述host只是个demo,需填入真实ipconn = connect(host='11.22.33.44', port=21050, auth_mechanism='PLAIN',user='yourusername',pa_python impyla demo

php 编译 pdo_mysql_Linux正确编译pdo_mysql扩展-程序员宅基地

文章浏览阅读280次。错误编译pdo_mysqlphp扩展的操作流程,以及解决错误并成功完成编译pdo_mysql新编译的PHP环境运行项目时报错PHP Fatal error: Undefined class constant 'MYSQL_ATTR_INIT_COMMAND'原因是没有加载pdo_mysql扩展错误配置pdo_mysql及编译cd ext/pdo_mysqlphpize./configure --w..._/usr/local/php7.4.24/ext/pdo_mysql/php_pdo_mysql_int.h:29:11: fatal error: m

随便推点

CLion:使用CLion新建一个C语言项目_clion创建c语言项目-程序员宅基地

文章浏览阅读1.3w次,点赞12次,收藏85次。步骤1、2、3、我喜欢一个文件夹下存放多个项目,所以删掉生成的CMakeList.txt、main.c和cmake-build-debug文件。新建一个List目录,并在该目录下新建CMakeList.txt4、创建一个C文件进行测试5、创建好后,提示在List文件夹下的CMakeList.txt添加:include_directories(.)add_executable(List-List01 List01.c) //List是文件夹名称,List01.c是具体文件名称_clion创建c语言项目

鸟哥的 linux 的私房菜 基础学习篇,鸟哥的 Linux 私房菜 -- 基础学习篇-程序员宅基地

文章浏览阅读5k次。再次强调:底下的几篇短文是学习 Linux 的基础文件,这些文件是基础中的基础,如果您能将其中的文件都看完,并且消化过,那么未来在管理 Linux 主机以及架设网站方面,就能够达到『事半功倍』的成效,请不要忽略这部份了!否则,再怎么讨论都是枉然的啦! ^_^第一部份:Linux 的规划与安装Linux 本身虽然具有相当强大的功能,不过,如果不能理解 Linux 的工作能力,那么 Linux 能做的..._鸟哥linux基础篇

材质面向摄像机_ue5 通过材质使面片始终朝向摄像机-程序员宅基地

文章浏览阅读2.4k次,点赞2次,收藏10次。材质面向摄像机单贴图面向摄像机组合贴图面向摄像机单贴图面向摄像机主要是调用RotateAboutAxis这个材质函数输入旋转轴 001计算旋转角度去除camera的z轴影响算出物体到摄像机的向量归一化后算出夹角FVector::Rotation()函数的内部实现(局部)FRotator R; // Find yaw.R.Yaw = FMath::Atan2(Y,X) * (180.f / PI); // Find pitch.R.Pitch = FMath_ue5 通过材质使面片始终朝向摄像机

轻松搞定 android MVP 架构、okHttp 网络模块封装 的 项目_android mvp网络封装-程序员宅基地

文章浏览阅读373次。CommonMvp MVP 框架的 使用commonMvp 能做什么?1、mvp 实现 model view presenter 业务和界面解耦2、整合 网络 请求3、简化网络调用流程4、整合状态栏和标题栏 实现沉浸式 状态栏5、Activity 、Fragment 中 使用方法 一致 接口式封装 生命周期1、有问题请 提交 isuue/(QQ:194093798) 谢谢大家 持续更新2、为新手提供一个 可靠 可用的 mvp 框架结构集成allprojects { repos_android mvp网络封装

flash详解_read parameter page-程序员宅基地

文章浏览阅读2.5w次,点赞62次,收藏496次。1.2.1. 什么是FlashFlash全名叫做Flash Memory,从名字就能看出,是种数据存储设备,存储设备有很多类,Flash属于非易失性存储设备(Non-volatile Memory Device),与此相对应的是易失性存储设备(Volatile Memory Device)。关于什么是非易失性/易失性,从名字中就可以看出,非易失性就是不容易丢失,数据存储在这类设备中,即使断电了,..._read parameter page

杰里之AI SDK 自定义命令操作流程】【篇】_杰里sdk-程序员宅基地

文章浏览阅读328次。APP 异步发数据给固件的操作流程:使 用 杰 理 的 APP , 不 开 放 自 定 义 services , 需 要 添 加 自 定 义 操 作 , 只 能 通 过 自 定 义 命 令JL_OPCODE_CUSTOMER_USER,利用这个通道去封装自己需要的功能。类似于提供一个 BLE 的串口功能。固件异步发数据给 APP 流程:..._杰里sdk

推荐文章

热门文章

相关标签