[SDOI2008] 仪仗队 题解

news/2024/11/8 3:05:18/

注:在洛谷同时发布。

题目链接

解题思路

首先观察样例。似乎什么也观察不出来?

那就根据题目描述中所给的图表做。首先找到对角线,将图形沿着对角线一分为二。注意对角线上可以看到一个人,所以答案要加 1 1 1

图1

其次逐个分析。可以发现,两部分是对称的。设每两个人之间的距离为 1 1 1 ,样例就简化为一个直角边长 ( n − 1 ) (n-1) (n1) 等腰直角三角形(不算左下角)。

图2

建立笛卡尔坐标系。将左下角设为 ( 0 , 0 ) (0,0) (0,0) ,这样就可以将图中的每个与 ( 0 , 0 ) (0,0) (0,0) 有边连接的点表示出来。

图4

不难发现,除 ( 1 , 0 ) (1,0) (1,0) 外,剩下的每个与 ( 0 , 0 ) (0,0) (0,0) 有边相连的点的横坐标与纵坐标所对应的值互质。

观察每一行。可以发现,每行与 ( 0 , 0 ) (0,0) (0,0) 有边相连的点的个数正好是与横坐标相互质的数的个数,也就是 φ \varphi φ ( i ) (i) (i)

所以该题目就可以转化为求 2 ∑ n − 1 i = 1 2\sum_{n-1}^{i=1} 2n1i=1 φ \varphi φ ( i ) + 1 (i)+1 (i)+1

但为了保证严谨,第 1 1 1 行的 ( 1 , 0 ) (1,0) (1,0) 一般单独处理。

则该题目被转化为求 2 ∑ n − 1 i = 2 2\sum_{n-1}^{i=2} 2n1i=2 φ \varphi φ ( i ) + 3 (i)+3 (i)+3

代码实现

前置知识:试除法求 φ \varphi φ ( i ) (i) (i)

inline int phi(int x)
{int ret=x;for(int i=2;i*i<=x;++i){if(x%i==0){ret=ret/i*(i-1);while(x%i==0)x/=i;}}if(x>1)ret=ret/x*(x-1);return ret;
}

首先 1 → \rightarrow n-1 (或 2 → \rightarrow n-1) 扫一遍。然后再用试除法(时间复杂度 n \sqrt n n ) 求出 φ \varphi φ ( i ) (i) (i) ,将其累加起来就解决了。

最后注意要加上对角线一行的 1 (或 3)!

但是当 n = 1 n=1 n=1 时,由于 ( 0 , 0 ) (0,0) (0,0) 无法被看到(自己不能看到自己),所以答案是 0 0 0

时间复杂度 O ( n n ) O(n \sqrt n) O(nn ) ,可以轻而易举的通过测试。

AC代码

当求 2 ∑ n − 1 i = 2 2\sum_{n-1}^{i=2} 2n1i=2 φ \varphi φ ( i ) + 3 (i)+3 (i)+3

#include<bits/stdc++.h>
using namespace std;
int n,ans=0;
inline int phi(int x)//试除法求欧拉函数
{int ret=x;for(int i=2;i*i<=x;++i){if(x%i==0){if(x%i==0){while(x%i==0)x/=i;ret=ret/i*(i-1);}}}if(x>1)ret=ret/x*(x-1);return ret;
}
signed main()
{cin>>n;if(n==1)puts("0"),exit(0);//特判,也可写作N<2for(int i=2;i<n;++i)ans+=phi(i);//统计答案cout<<ans*2+3;return 0;
}

当求 2 ∑ n − 1 i = 1 2\sum_{n-1}^{i=1} 2n1i=1 φ \varphi φ ( i ) + 1 (i)+1 (i)+1

#include<bits/stdc++.h>
using namespace std;
int n,ans=0;
inline int phi(int x)//试除法
{int ret=x;for(int i=2;i*i<=x;++i){if(x%i==0){if(x%i==0){while(x%i==0)x/=i;ret=ret/i*(i-1);}}}if(x>1)ret=ret/x*(x-1);return ret;
}
signed main()
{cin>>n;if(n==1)puts("0"),exit(0);//特判for(int i=1;i<=n-1;++i)ans+=phi(i);//统计答案cout<<ans*2+1;return 0;
}

拓展题目

如果你通过了这道题,你还可以试试这些题目:

[SDOI2012] Longge 的问题

[SDOI2008] 沙拉公主的困惑


http://www.ppmy.cn/news/814102.html

相关文章

linux使用scp命令,涉及权限赋予

1、参考Linux scp命令 | 菜鸟教程 2、实际使用&#xff0c;希望将文件传到目标机器的目标目录。 sudo scp -r /home/lighthouse/eladmin/eladmin-system-2.7.jar ubuntu140.143.163.109:/home/lighthouse/eladmin 执行时报错&#xff0c;目标机器上的ubuntu用户没有lighthou…

微星 b650m 迫击炮 WiFi + 7950x + 金百达内存32g 6000 装机 主板dram 灯和CPU灯长亮,无CPU更新bios教程

很明显&#xff0c;微星主板自检没通过。确认主板cpu处没有断针脚&#xff0c;基本确定是bios问题。 第一步 去微星官网搜索对应型号的主板 找到并点击download 下载最新的bios即可 第二步 准备一个U盘&#xff0c;需要格式化&#xff0c;注意提前保存相关文件&#xff…

T100新程序的开发【完整步骤】

简易程序的开发 记录T100中一个简易程序的开发完整步骤。 一、程序基本数据设置作业 打开作业 azzi900,弹出作业详情。 新增一个程序编号。 一些属性概念 程序编号:手动输入你建立的新程序。程序名称:手动输入你建立的名称。归属模块:取决于你程序编号的第一个字母。归属…

eclipse安装

下载 https://www.eclipse.org/ 安装 选择web开发 启动项目&#xff0c;让选择工作地址 创建java web项目 选择一下运行时 选择好tomcat服务器finish即可 创建maven项目

【玩转嵌入式屏幕显示】(一)显示器概述(常见显示器及其显示原理)

什么是显示器 显示器是计算机的I/O设备,是一种将特定电子信息输出到屏幕上再反射到人眼的显示工具。 常见显示器及其显示原理 CRT显示器LCD显示器(液晶)LED点阵显示器OLED显示器CRT显示器 CRT显示器即使用阴极射线显像管(Cathode Ray Tube)的显示器,体积过大,非常笨重…

中景园0.96寸 OLED 显示屏 学习笔记

中景园0.96寸 OLED 显示屏 学习笔记 一、OLED简介 OLED&#xff0c;即有机发光二极管( Organic Light Emitting Diode )。OLED由于同时具备自发光&#xff0c;不需背光源、对比度高、厚度薄、视角广、反应速度快、可用于挠曲性面板、使用温度范围广、构造及制程较简单等优异之…

2022年遭“挤爆”的三款透明LED显示屏

2017年是透明LED显示屏爆发元年&#xff0c;一直到2019年&#xff0c;市场都呈现40%以上高态势增长.收到疫情影响&#xff0c;这两年态势有所回落&#xff0c;但整体上还是顺势增长。2022年市场呈现快速增长&#xff0c;一方面得益于项目推迟延续到今年开工&#xff0c;另一方面…

嵌入式设备显示屏相关概念汇总

嵌入式设备常用的显示屏接口 LCD 接口&#xff1a;是一种常见的数字电路接口&#xff0c;支持多种显示器件&#xff0c;如字符型液晶显示器和点阵型液晶显示器等。 VGA 接口&#xff1a;是一种视频接口标准&#xff0c;用于连接显示器和计算机。该接口提供模拟 RGB 信号&#…