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

算法模板——线性欧拉函数

作者头像
HansBug
发布2018-04-11 10:48:00
5540
发布2018-04-11 10:48:00
举报
文章被收录于专栏:HansBug's Lab

实现功能:求出1-N的欧拉函数,然后应对若干个询问操作

其实就是个素数判定+欧拉函数性质的二合一

代码如下,我觉得应高不难懂,只要你知道欧拉函数的性质

代码语言:javascript
复制
var
   i,j,k,l,m,n:longint;
   a,b:array[0..10000005] of longint;
procedure phi;
          var i,j:longint;
          begin
               m:=0;a[1]:=1;
               for i:=2 to n do
                   begin
                        if a[i]=0 then
                           begin
                                inc(m);
                                b[m]:=i;
                                a[i]:=i-1;
                           end;
                        for j:=1 to m do
                            begin
                                 if (i*b[j])>n then break;
                                 if (i mod b[j])=0 then
                                    a[i*b[j]]:=a[i]*b[j]
                                 else
                                     a[i*b[j]]:=a[i]*(b[j]-1);
                            end
                   end;
          end;
begin
     readln(n);phi;
     while true do
           begin
                readln(j);
                writeln(a[j]);
           end;
end.
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015-05-06 ,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

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