专栏首页HansBug's Lab算法模板——线性欧拉函数

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

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

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

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

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.

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 3389: [Usaco2004 Dec]Cleaning Shifts安排值班

    3389: [Usaco2004 Dec]Cleaning Shifts安排值班 Time Limit: 1 Sec  Memory Limit: 128 MB...

    HansBug
  • Codevs3278[NOIP2013]货车运输

    3287 货车运输 2013年NOIP全国联赛提高组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题目描述...

    HansBug
  • 1935: [Shoi2007]Tree 园丁的烦恼

    1935: [Shoi2007]Tree 园丁的烦恼 Time Limit: 15 Sec  Memory Limit: 357 MB Submit: 648 ...

    HansBug
  • Codevs3278[NOIP2013]货车运输

    3287 货车运输 2013年NOIP全国联赛提高组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题目描述...

    HansBug
  • 3389: [Usaco2004 Dec]Cleaning Shifts安排值班

    3389: [Usaco2004 Dec]Cleaning Shifts安排值班 Time Limit: 1 Sec  Memory Limit: 128 MB...

    HansBug
  • 1935: [Shoi2007]Tree 园丁的烦恼

    1935: [Shoi2007]Tree 园丁的烦恼 Time Limit: 15 Sec  Memory Limit: 357 MB Submit: 648 ...

    HansBug
  • 3223: Tyvj 1729 文艺平衡树

    3223: Tyvj 1729 文艺平衡树 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 1347  Sol...

    HansBug
  • 算法模板——splay区间反转 1

    实现的功能:将序列区间反转,并维护 详见BZOJ3223 1 var 2 i,j,k,l,m,n,head,a1,a2:longint; 3 ...

    HansBug
  • 基于FPGA的内存128M flash芯片控制器设计

    大侠好,欢迎来到FPGA技术江湖,江湖偌大,相见即是缘分。大侠可以关注FPGA技术江湖,在“闯荡江湖”、"行侠仗义"栏里获取其他感兴趣的资源,或者一起煮酒言欢。...

    FPGA技术江湖
  • 3359: [Usaco2004 Jan]矩形

    3359: [Usaco2004 Jan]矩形 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 8  Solv...

    HansBug

扫码关注云+社区

领取腾讯云代金券