前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法模板——单个值欧拉函数

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

作者头像
HansBug
发布2018-04-10 17:22:34
6230
发布2018-04-10 17:22:34
举报
文章被收录于专栏:HansBug's Lab

输入N,输出phi(N)

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

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

代码语言:javascript
复制
 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.      
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015-04-03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档