算法模板——单个值欧拉函数

输入N,输出phi(N)

这样的单个值欧拉函数程序一般见于部分数论题,以及有时候求逆元且取模的数不是质数的情况(逆元:A/B=A*Bphi(p)-1 (mod p),一般常见题中p是质数,phi(p)-1=p-2)

(Tip:我是来水经验的不解释,不过话说真的好久没写这个了TT)

 1 var i:int64;
 2 function Eula(x:int64):int64;
 3          var res:int64;i:longint;
 4          begin
 5               res:=x;
 6               for i:=2 to trunc(sqrt(x)) do
 7                   begin
 8                        if (x mod i)=0 then
 9                           begin
10                                res:=(res div i)*(i-1);
11                                while (x mod i)=0 do x:=x div i;
12                           end;
13                   end;
14               if x>1 then res:=(res div x)*(x-1);
15               exit(res);
16          end;
17 begin
18      readln(i);writeln(Eula(i));
19      readln;
20 end.      

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

Python-OpenCV 处理图像(二):滤镜和图像运算

喜欢自拍的人肯定都知道滤镜了,下面代码尝试使用一些简单的滤镜,包括图片的平滑处理、灰度化、二值化等:

28610
来自专栏数据结构与算法

洛谷P3356 火星探险问题(费用流)

题目描述 火星探险队的登陆舱将在火星表面着陆,登陆舱内有多部障碍物探测车。登陆舱着陆后,探测车将离开登陆舱向先期到达的传送器方向移动。探测车在移动中还必须采集岩...

27340
来自专栏机器之心

教程 | 如何将模型部署到安卓移动端,这里有一份简单教程

截至 2018 年,全球活跃的安卓设备已经超过了 20 亿部。安卓手机的迅速普及在很大程度上得益于各种各样的智能应用,从地图到图片编辑器无所不有。随着深度学习技...

42710
来自专栏蜕变

#哆啦A梦

write('by dongdong', font=("Bradley Hand ITC", 30, "bold"))

12000
来自专栏数据结构与算法

欧拉回路与欧拉路径

欧拉回路与欧拉路径 如果图G中的一个路径包括每个边恰好一次,则该路径称为欧拉路径(欧拉通路)。 如果一个回路是欧拉路径,则称为欧拉回路(Euler circui...

43890
来自专栏GIS讲堂

ArcGIS Image Server简介以及OL2中的加载

本文讲述Arcgis Image Server相关以及在OL2中如何加载Arcgis Server发布的影像服务。

13520
来自专栏和蔼的张星的图像处理专栏

8.SSD目标检测之二:制作自己的训练集

最近秋色甚好,一场大风刮散了雾霾,难得几天的好天气,周末回家在大巴上看着高速两旁夕阳照射下黄澄澄的树叶,晕车好像也好了很多。 特地周六赶回来为了周末去拍点素材...

17640
来自专栏Python数据科学

快速入门Matplotlib教程

Matplotlib 可能是 Python 2D-绘图领域使用最广泛的套件。它能让使用者很轻松地将数据图形化,并且提供多样化的输出格式。这里将会探索 matpl...

13110
来自专栏一棹烟波

OpenGL进行简单的通用计算实例

博主作为OpenGL新手,最近要用OpenGL进行并行的数据计算,突然发现这样的资料还是很少的,大部分资料和参考书都是讲用OpenGL进行渲染的。好不容易找到一...

32370
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

1.5K40

扫码关注云+社区

领取腾讯云代金券