『ACM C++』HDU杭电OJ | 1418 - 抱歉 （拓扑学：多面体欧拉定理引申）
呕，大一下学期的第一周结束啦，一周过的挺快也挺多出乎意料的事情的~ 随之而来各种各样的任务也来了，嘛毕竟是大学嘛，有点上进心的人多多少少都会接到不少任务的，忙也正常啦~端正心态 开心面对就好啦~
今天突然回顾了一下《从你的全世界路过》这本书和电影，莫名的感悟涌上心头，收集到了一些走入人心的一些语句：
1、在季节的车上，如果你要提前下车，请别推醒装睡的我，这样我可以沉睡到终点，假装不知道你已经离开。
2、世事如书，我偏爱你这一句，愿做个逗号，待在你脚边。但你有自己的朗读者，而我只是个摆渡人。
3、我淋过的最大的雨，是那一天你在烈日下的不回头。
4、这世界是你的遗嘱，而我是你唯一的遗物。
5、我希望有个如你一般的人，如山间清爽的风，如古城温暖的光，从清晨到夜晚，由山野到书房，只要最后是你，就好。
今日兴趣新闻：
mwc 2019 新品汇总：5g+ 折叠屏开启的新时代？
链接：https://mbd.baidu.com/newspage/data/landingsuper?context=%7b"nid"%3a"news_11274128788158220226"%7d&n_type=0&p_from=1
------------------------------------------------题目----------------------------------------------------------
抱歉
time limit: 2000/1000 ms (java/others) memory limit: 65536/32768 k (java/others)
total submission(s): 6147 accepted submission(s):
2891
problem description
前几天在网上查找acm资料的时候，看到一个中学的奥数题目，就是不相交的曲线段分割平面的问题，我已经发到论坛，并且lxj 已经得到一个结论，这里就不
多讲了，下面有一个类似的并且更简单的问题：
如果平面上有n个点，并且每个点至少有2条曲线段和它相连，就是说，每条曲线都是封闭的，同时，我们规定：
1）所有的曲线段都不相交；
2）但是任意两点之间可以有多条曲线段。
如果我们知道这些线段把平面分割成了m份，你能知道一共有多少条曲线段吗？
input
所有输入数据都在32位整数范围内。
output
sample input
3 2 0 0
sample output
3
（一） 题目分析：
题目一上来懵了，很短的题目，也很容易读懂什么意思，但就是没有思路下手，对数学背景也不太清楚，还是一道中学奥数题，ac率还很高，我居然还不会做，去看了一下杭电的discuss之后才发现，这其实就是多面体欧拉定理的输出结果而已。
后面会引申多面体欧拉定理。
（二）ac代码：
#include<stdio.h>
using namespace std;
long long int n,m;
int main()
{
while(scanf("%d%d",&n,&m) && (n||m))
printf("%d\n",n+m-2);
return 0;
}
注：因为代码太简单就不分块了，主要是引出多面体欧拉定理。
（三）ac截图：
（四）解后分析：
多面体欧拉定理：
多面体欧拉定理是指对于简单多面体，其顶点数v、棱数e及面数f间有著名的欧拉公式：v-e+f=2。简单多面体即表面经过连续变形可以变为球面的多面体。
v+f-e=x(p)，v是多面体p的顶点个数，f是多面体p的面数，e是多面体p的棱的条数，x(p)是多面体p的欧拉示性数。 如果p可以同胚于一个球面（可以通俗地理解为能吹胀成一个球面），那么x(p)=2，如果p同胚于一个接有h个环柄的球面，那么x(p)=2-2h。 x(p)叫做p的拓扑不变量，是拓扑学研究的范围。
引申其他的欧拉公式：
分式里的欧拉公式：
a^r/(a-b)(a-c)+b^r/(b-c)(b-a)+c^r/(c-a)(c-b)
当r=0,1时式子的值为0 当r=2时值为1
当r=3时值为a+b+c
复变函数论里的欧拉公式：
e^ix=cosx+isinx，
e是自然对数的底，i是虚数单位。它将三角函数的定义域扩大到复数，建立了三角函数和指数函数的关系，它在复变函数论里占有非常重要的地位.
将公式里的x换成-x，得到：
e^-ix=cosx-isinx，然后采用两式相加减的方法得到：
sinx=(e^ix-e^-ix)/(2i)，cosx=(e^ix+e^-ix)/2.这两个也叫做欧拉公式。将e^ix=cosx+isinx中的x取作∏就得到：
e^i∏+1=0. 这个恒等式也叫做欧拉公式，它是数学里最令人着迷的一个公式，它将数学里最重要的几个数学联系到了一起：两个超数：自然对数的底e，圆周率∏，两个单位：虚数单位i和自然数的单位1，以及数学里常见的0。数学家们评价它是“上帝创造的公式”，我们只能看它而不能理解它。
三角形中的欧拉公式：
设r为三角形外接圆半径，r为内切圆半径，d为外心到内心的距离，则： d^2=r^2-2rr
拓扑学里的欧拉公式：（多面体欧拉公式）
v+f-e=x(p)，v是多面体p的顶点个数，f是多面体p的面数，e是多面体p的棱的条数,x(p)是多面体p的欧拉示性数。
如果p可以同胚于一个球面(可以通俗地理解为能吹胀而绷在一个球面上)，那么x(p)=2，如果p同胚于一个接有h个环柄的球面，那么x(p)=2-2h。
x(p)叫做p的欧拉示性数，是拓扑不变量，就是无论再怎么经过拓扑变形也不会改变的量，是拓扑学研究的范围。
在多面体中的运用:
简单多面体的顶点数v、面数f及棱数e间有关系
v+f-e=2
这个公式叫欧拉公式。公式描述了简单多面体顶点数、面数、棱数特有的规律。
初等数论里的欧拉公式：
欧拉φ函数：φ(n)是所有小于n的正整数里，和n互素的整数的个数。n是一个正整数。
欧拉证明了下面这个式子：
如果n的标准素因子分解式是p1^a1*p2^a2*……*pm^am，其中众pj(j=1,2,……,m)都是素数，而且两两不等。则有
φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm)
利用容斥原理可以证明它。
参考：https://www.phb123.com/shijiezhizui/renlei/20095_2.html
注：我还是个渣渣辉，代码可能写得不够高效不够好，我也会努力优化，如果有更好的解法，真心希望您能够评论留言贴上您的代码呢~互相帮助互相鼓励才能成长鸭~~