P2158 仪仗队

Myth丶恋晨 2021-10-26 12:34 243阅读 0赞

欧拉筛，题解来自：[https://www.luogu.org/space/show?uid=34195][https_www.luogu.org_space_show_uid_34195]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <cstdio>
     3 #include <algorithm>
     4 #include <vector>
     5 #include <cmath>
     6 #include <string>
     7 #include <cstring>
     8 #include <set>
     9 #include <map>
    10 using namespace std;
    11 const int maxn=40001;
    12 int n,cnt,num,m[maxn],phi[maxn],p[maxn];
    13 
    14 void olershai()
    15 {
    16     phi[1]=1;
    17     for(int i=2;i<=n;++i){
    18         if(!m[i]){
    19             p[++num]=i;
    20             phi[i]=i-1;
    21         }
    22         for(int j=1;j<=num&&p[j]*i<n;++j){
    23             m[p[j]*i]=1;
    24             if(i%p[j]==0){
    25                 phi[p[j]*i]=phi[i]*p[j];
    26                 break;
    27             }else{
    28                 phi[p[j]*i]=phi[i]*(p[j]-1);
    29             }
    30         }
    31     }
    32 }
    33 
    34 int main()
    35 {
    36     scanf("%d",&n);
    37     if(n==1){
    38         printf("0");
    39         return 0;
    40     }
    41     
    42     olershai();
    43     for(int i=2;i<n;++i){
    44         cnt+=phi[i];
    45     }
    46     cnt*=2;
    47     cnt+=3;
    48     printf("%d",cnt);
    49     return 0;
    50 }

。。

转载于:https://www.cnblogs.com/greenaway07/p/11277049.html

[https_www.luogu.org_space_show_uid_34195]: https://www.luogu.org/space/show?uid=34195
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211026/489e48153eea4178b7131ec1a984cefb.png

发表评论取消回复

表情：

评论列表（有 0 条评论，243人围观）

还没有评论，来说两句吧...

相关阅读

相关【C++】*P、P 、&P的区别

在刚开始接触到C++的时候一提到指针P就会联想到一个箭头指向了一个地址，这是一个最为基础而且不算全面的理解，在后面的学习过程中总是能遇到类似指针的知识点，发现一个简单...

刺骨的言语ヽ痛彻心扉/ 2024年04月20日 00:16/ 0 赞/ 125 阅读

相关 p++与(p++) (p)++ ++p *(++p)

<pre name="code" class="cpp">include <stdio.h> int main(void) { in

浅浅的花香味﹌/ 2022年08月27日 15:56/ 0 赞/ 223 阅读

相关【日常学习】【欧拉函数】codevs2296 仪仗队题解

转载请注明出处 \[ametake版权所有\][http://blog.csdn.net/ametake][http_blog.csdn.net_ametake]欢迎

绝地灬酷狼/ 2022年08月05日 04:18/ 0 赞/ 103 阅读

相关 ♥BZOJ 2190: [SDOI2008]仪仗队【欧拉函数】

2190: \[SDOI2008\]仪仗队 Time Limit: 10 Sec Memory Limit: 259 MB Submit: 2298 Solved:

淩亂°似流年/ 2022年07月29日 08:48/ 0 赞/ 137 阅读

相关 P3P

P3P是万维网联盟（W3C）公布的一项隐私保护推荐标准，旨在为网上冲浪的 Internet用户提供隐私保护。现在有越来越多的网站在消费者访问时，都会收集一些用户信息。制定P3P

冷不防/ 2022年07月10日 05:28/ 0 赞/ 191 阅读

相关【C语言】++p，p++，++p，++++p，++*p++

部分运算符优先级和结合方向表 ![这里写图片描述][SouthEast] 首先我们在优先级及结合方向表中可以看到++运算符和\运算符是同属于一级

桃扇骨/ 2022年06月17日 00:50/ 0 赞/ 245 阅读

相关洛谷P2158 [SDOI2008]仪仗队

题目描述作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N \ N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生

傷城~/ 2022年05月25日 01:28/ 0 赞/ 144 阅读

相关 p *p **p

include<iostream> using namespace std; void test01(){ int a=10; int

布满荆棘的人生/ 2022年04月05日 13:23/ 0 赞/ 247 阅读

相关【c语言】p++、++p、(p)++、++p 的区别学习

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xicWx6

不念不忘少年蓝@/ 2022年04月04日 06:22/ 0 赞/ 299 阅读

相关 P2158 仪仗队

欧拉筛，题解来自：[https://www.luogu.org/space/show?uid=34195][https_www.luogu.org_space_sh

Myth丶恋晨/ 2021年10月26日 12:34/ 0 赞/ 244 阅读