Color the necklace

时间限制：2000 ms | 内存限制：65535 KB

难度：0

描述: As we all know, girls love necklaces, especially nice necklaces. Recently, huicpc229 has fallen in love with a girl; he wants to bring her a necklace as a gift. Now he has n colors, and the necklace is circular and it has n beads, huicpc229 can use his colors to color the necklace. he wants to know how many different kinds of necklaces he can make，he may not use all the n colors. In this problem, the necklace is same when you rotate it around the center of the necklace or turn it over.

输入

First line is the testcase T.
Following T lines, each line is an integer n ( 1≤n ≤ 10^9 )

输出

Output the answer mod 20090531

样例输入

4	1234

样例输出

13  10   55

欧拉定理

欧拉定理、快速幂与逆元

1.代码：

#include <cstdio>

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const LL mod = 20090531;
LL x,y;
LL euler(LL p)//欧拉定理
{
LL res = p;
for(LL i = 2; i <= sqrt(p); i++)
{
if(p%i==0)
{
while(p%i==0) p/=i;
res = res/i*(i-1);
}
}
if(p > 1) res = res / p * (p-1);
return res%mod;
}
LL fast_pow(LL a,LL b)//快速幂
{
LL res = 1;
while(b)
{
if(b&1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
void edgcd(LL a,LL b)//求逆元
{
if(b == 0)
{
x = 1;
y = 0;
return;
}
edgcd(b,a%b);
LL temp = x;
x = y;
y = temp - a/b*y;
}
void solve(LL m)
{
LL res = 0;
for(LL i = 1; i <= sqrt(m); i++)
{
if(m%i==0)
{
if(m/i != i) res = (res + euler(i)*fast_pow(m,m/i-1))%mod;
res = (res + euler(m/i)*fast_pow(m,i-1))%mod;
}
}
if(m&1)
{
res = (fast_pow(m,(m+1)/2) + res) % mod;
edgcd(2,mod);
}
else
{
res = (fast_pow(m,m/2+1) + fast_pow(m,m/2) + 2 * res) % mod;
edgcd(4,mod);
}
while(x < 0) x = (x + mod) % mod;
printf("%lld\n",x * res % mod);
}
int main(int argc, char** argv)
{
int n;
LL m;
scanf("%d",&n);
while(n--)
{
scanf("%lld",&m);
solve(m);
}
return 0;

}

2.欧拉定理

在数学及许多分支中都可以见到很多以欧拉命名的常数、公式和定理。在数论中，欧拉定理(Euler Theorem，也称费马-欧拉定理或欧拉函数定理)是一个关于同余的性质。欧拉定理得名于瑞士数学家莱昂哈德·欧拉，该定理被认为是数学世界中最美妙的定理之一。欧拉定理实际上是费马小定理的推广。此外还有平面几何中的欧拉定理、多面体欧拉定理(在一凸多面体中，顶点数-棱边数+面数=2)。西方经济学中欧拉定理又称为产量分配净尽定理，指在完全竞争的条件下，假设长期中规模收益不变，则全部产品正好足够分配给各个要素。另有欧拉公式。

数论定理

折叠内容

在数论中，欧拉定理,(也称费马-欧拉定理)是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互质，则:

欧拉定理

折叠证明

将1~n中与n互质的数按顺序排布:x1,x2……xφ(n) (显然，共有φ(n)个数)

我们考虑这么一些数:

m1=a*x1;m2=a*x2;m3=a*x3……mφ(n)=a*xφ(n)

1)这些数中的任意两个都不模n同余，因为如果有mS≡mR (mod n) (这里假定mS更大一些)，就有:

mS-mR=a(xS-xR)=qn，即n能整除a(xS-xR)。但是a与n互质，a与n的最大公因子是1，而xS-xR<n，因而左式不可能被n整除。也就是说这些数中的任意两个都不模n同余，φ(n)个数有φ(n)种余数。

2)这些数除n的余数都与n互质，因为如果余数与n有公因子r，那么a*xi=pn+qr=r(……)，a*xi与n不互质，而这是不可能的。那么这些数除n的余数，都在x1,x2,x3……xφ(n)中，因为这是1~n中与n互质的所有数，而余数又小于n.

由1)和2)可知，数m1,m2,m3……mφ(n)(如果将其次序重新排列)必须相应地同余于x1,x2,x3……xφ(n).

故得出:m1*m2*m3……mφ(n)≡x1*x2*x3……xφ(n) (mod n)

或者说a^[φ(n)]*(x1*x2*x3……xφ(n))≡x1*x2*x3……xφ(n)

或者为了方便:K{a^[φ(n)]-1}≡0 ( mod n ) 这里K=x1*x2*x3……xφ(n)。

可知K{a^[φ(n)]-1}被n整除。但K中的因子x1,x2……都与n互质，所以K与n互质。那么a^[φ(n)]-1必须能被n整除，即a^[φ(n)]-1≡0 (mod n)，即a^[φ(n)]≡1 (mod n)，得证。

费马小定理:

a是不能被质数p整除的正整数，则有a^(p-1) ≡ 1 (mod p)

证明这个定理非常简单，由于p是质数，所以有φ(p) = p-1，代入欧拉定理即可证明。推论:对于任意正整数a，有a^p ≡ a (mod p)，因为a能被p整除时结论显然成立。

折叠应用

首先看一个基本的例子。令a = 3，n = 5，这两个数是互素的。比5小的正整数中与5互素的数有1、2、3和4，所以φ(5)=4(详情见[欧拉函数])。计算:a^{φ(n)} = 3^4 =81，而81= 80 + 1 Ξ 1 (mod 5)。与定理结果相符。

这个定理可以用来简化幂的模运算。比如计算7^{222}的个位数，实际是求7^{222}被10除的余数。7和10[[互素]]，且φ(10)=4。由欧拉定理知7^4Ξ1(mod 10)。所以7^{222}=(7^4)^55*(7^2)Ξ1^{55}*7^2Ξ49Ξ9 (mod 10)

几何定理

折叠内容

1)设三角形的外接圆半径为R，内切圆半径为r，外心与内心的距离为d，则d^2=R^2-2Rr.

2)三角形ABC的垂心H，九点圆圆心V,重心G,外心O共线，称为欧拉线

折叠证明

1)证明过程见下图:

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的拓扑不变量，是拓扑学研究的范围。

经济学

欧拉定理指出:如果产品市场和要素市场都是完全竞争的，而且厂商生产的规模报酬不变，那么在市场均衡的条件下，所有生产要素实际所取得的报酬总量正好等于社会所生产的总产品。该定理又叫做边际生产力分配理论，还被称为产品分配净尽定理。如上所述，要素的价格是由于要素的市场供给和市场需求共同决定。在完全竞争的条件下，厂商和消费者都被动地接受市场形成的价格。

折叠定理推导

在完全竞争的条件下，厂商使用要素的原则是:要素的边际产品价值等于要素价格。即:

P*MPL=W (1)

P*MPK=r (2)

由式1和2可得:

MPL=W/P (3)

MPK=r/p(4

P为产品的价格，W/P和r/P分别表示了劳动和资本的实际报酬。因为在完全竞争的条件下，单位劳动、单位资本的实际报酬分别等于劳动、资本的边际产量。假定整个社会的劳动总量和资本总量为L和K，而社会总产品为Q,由在市场均衡的条件下，所有生产要素实际所取得的报酬总量正好等于社会所生产的总产品,得:

Q=L*MPL+K*MPK(5)

式5称为欧拉分配定理。它是由于该定理的证明使用了数学上的欧拉定理而得名。

折叠定理证明

假设生产函数为:Q=f(L.K)(即Q为齐次生产函数),定义人均资本k=K/L

方法1:根据齐次生产函数中不同类型的生产函数进行分类讨论

(1)线性齐次生产函数

n=1,规模报酬不变,因此有:

Q/L=f(L/L,K/L)=f(1,k)=g(k)

k为人均资本，Q/L为人均产量，人均产量是人均资本k的函数。

让Q对L和K求偏导数,有:

∂Q/∂L=∂[L*g(k)]/∂L=g(k)+L*[dg(k)/dk]*[dk/dL]=g(k)+L*g'(k)*(-K/L)=g(k)-k*g'(k)

∂Q/∂K=∂[L*g(k)]/ ∂K=L*[∂g(k)/∂k]=L*[dg(k)/dk]*[∂k/∂K]=L*g'(k)*(1/L)=g'(k)

由上面两式，即可得欧拉分配定理:

L*[∂Q/∂L]+K*[∂Q/∂K]=L*[g(k)-k*g'(k)]+K*g'(k)=L*g(k)-K*g'(k)+K*g'(k)=L*g(k)=Q

(2)非线性齐次生产函数

1.当n〉1时，规模报酬递增，如果按照边际生产力分配，则产品不够分配给各个生产要素，即:

L*[∂Q/∂L]+K*[∂Q/∂K]>Q

2.当n<1时，规模报酬递减，如果按边际生产力进行分配，则产品在分配给各个生产要素之后还有剩余，即:

L*[∂Q/∂L]+K*[∂Q/∂K]<Q

方法2:设一个一般的齐次生产函数Q=f(L,K)为n齐次(即n任意的齐次生产函数，既可以是线性的，也可以是非线性的)，则有:

Q=L *g(k)

将该函数对K，对L求偏导数，得:

∂Q/∂K=g'(k)

∂Q/∂L=ng(k)-kg'(k)

综合上述两式，有:

L*(∂Q/∂L)+K*(∂Q/∂K)=nL*g(k)=nQ

当n=1时，规模报酬不变，该式即为欧拉分配定理

当n〉1时，规模报酬递增，故有:

L*[∂Q/∂L]+K*[∂Q/∂K]>Q

当n<1时，规模报酬递减，故有:

L*[∂Q/∂L]+K*[∂Q/∂K]<Q

折叠实例

在技术经济学中，欧拉定理属于一次齐次函数的一个重要性质，它是说一次齐次函数的数值都可以表示为各自变量和因变量对相应自变量一阶偏导的乘积之和。在理论上，这句话显得很晦涩，可以用一个很形象的例子来解释。

假设有两个人，他们一个有十个胡萝卜的种子，另外一个有种胡萝卜的经验，他们打算合作，前者出种子，后者出劳力，用十天的时间来种植胡萝卜。在这过程中，风调雨顺，没有什么意外，种子全部茁壮成长，拥有种植经验的人也尽职尽责，最后得到的胡萝卜的产量是最大化的，有十公斤。而每个种子的在自然状态下能产出0.5公斤的胡萝卜，劳动者每一天能辛劳能使胡萝卜在最终增加0.5公斤，所以最后的产量也是10=0.5*10+0.5*10，即种子(资本)的边际产出乘以资本量加上劳动的边际产出乘以劳动量等于总产出。

上边是对欧拉定理在经济学中一次齐次生产函数的解释。但是它又有什么深刻地含义呢?在宏观经济中，上述的欧拉定理可以被解释为收入的分配，也就是在胡萝卜的例子中，前五公斤的萝卜是由资本所作出的贡献，后五公斤是由劳动所作出的贡献，如果社会这种很理想量化的贡献来分配产出，那么社会的分配时公平也富有效率的，也是能够自动将产出出清的。

这样看来，一个社会的产出如果能用欧拉定理将各种生产要素的贡献清晰量化，按贡献分配产出，那么这个社会是如此的美好啊，至少每个劳动者，每个资本拥有者用了生产的动力，不会像人民公社中的按需分配的成员那样随处搭便车，产生囚徒困境的窘境，也不会像如今这样劳动者到处诉苦说自己的贡献在社会分配中被低估，而国家有制定最低工资制度，结果造成在位者的得利，失业者的痛苦。

也有人一定会指责欧拉定理的理想状态，肯定会说，这样的话整个社会的产出就被当期消费掉了，没有留下盈余成为资本来在将来扩大再生产，我们的后代怎么办?饿肚子么?其实这个问题也是值得考虑的，吃光了的，甚至把种子都吃了，将来当然会一命呜呼，但是盈余让劳动者，资本所有者们在当期享乐，总比把当期的盈余变成各种"白宫"好吧

复变函数

定理内容

欧拉定理

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。数学家们评价它是"上帝创造的公式"，我们只能看它而不能理解它。

意义

1.数学规律:公式描述了简单多面体中顶点数、面数、棱数之间特有的规律

2.思想方法创新:定理发现证明过程中，观念上，假设它的表面是橡皮薄膜制成的，可随意拉伸;方法上将底面剪掉，化为平面图形(立体图→平面拉开图)。

3.引入拓扑学:从立体图到拉开图，各面的形状、长度、距离、面积等与度量有关的量发生了变化，而顶点数，面数，棱数等不变。

定理引导我们进入一个新几何学领域:拓扑学。我们用一种可随意变形但不得撕破或粘连的材料(如橡皮波)做成的图形，拓扑学就是研究图形在这种变形过程中的不变的性质。

4.提出多面体分类方法:

在欧拉公式中， f (p)=V+F-E 叫做欧拉示性数。欧拉定理告诉我们，简单多面体f (p)=2。

除简单多面体外，还有非简单多面体。例如，将长方体挖去一个洞，连结底面相应顶点得到的多面体。它的表面不能经过连续变形变为一个球面，而能变为一个环面。其欧拉示性数f (p)=16+16-32=0，即带一个洞的多面体的欧拉示性数为0。

5.利用欧拉定理可解决一些实际问题

如:为什么正多面体只有5种? 足球与C60的关系?否有棱数为7的正多面体?等

证明应用

折叠利用几何画板

逐步减少多面体的棱数，分析V+F-E

先以简单的四面体ABCD为例分析证法。

去掉一个面，使它变为平面图形，四面体顶点数V、棱数E与剩下的面数F1变形后都没有变。因此，要研究V、E和F关系，只需去掉一个面变为平面图形，证V+F1-E=1

1.去掉一条棱，就减少一个面，V+F1-E不变。依次去掉所有的面，变为"树枝形"。

2.从剩下的树枝形中，每去掉一条棱，就减少一个顶点，V+F1-E不变，直至只剩下一个点。

以上过程V+F1-E不变，V+F1-E=1，所以加上去掉的一个面，V+F-E =2。

对任意的简单多面体，运用这样的方法，都是只剩下一条线段。因此公式对任意简单多面体都是正确的。

计算多面体各面内角和

设多面体顶点数V，面数F，棱数E。剪掉一个面，使它变为平面图形(拉开图)，求所有面内角总和Σα

一方面，在原图中利用各面求内角总和。

设有F个面，各面的边数为n1,n2，…，nF，各面内角总和为:

Σα = [(n1-2)·180度+(n2-2)·180度+…+(nF-2) ·180度]

= (n1+n2+…+nF -2F) ·180度

=(2E-2F) ·180度 = (E-F) ·360度 (1)

另一方面，在拉开图中利用顶点求内角总和。

设剪去的一个面为n边形，其内角和为(n-2)·180角，则所有V个顶点中，有n个顶点在边上，V-n个顶点在中间。中间V-n个顶点处的内角和为(V-n)·360度，边上的n个顶点处的内角和(n-2)·180度。

所以，多面体各面的内角总和:

Σα = (V-n)·360度+(n-2)·180度+(n-2)·180度

=(V-2)·360度(2)

由(1)(2)得:(E-F) ·360度=(V-2)·360度

所以 V+F-E=2.

用拓扑学方法证明

欧拉定理尝试一下用拓扑学方法证明关于多面体的面、棱、顶点数的欧拉公式。

欧拉公式:对于任意多面体(即各面都是平面多边形并且没有洞的立体)，假设F，E和V分别表示面，棱(或边)，角(或顶)的个数，那末

F-E+V=2。

证明如图(图是立方体，但证明是一般的，是"拓朴"的):

1.把多面体(图中①)看成表面是薄橡皮的中空立体。

2.去掉多面体的一个面，就可以完全拉开铺在平面上而得到一个平面中的直线形，像图中②的样子。假设F′，E′和V′分别表示这个平面图形的(简单)多边形、边和顶点的个数，我们只须证明F′-E′+V′=1。

3.对于这个平面图形，进行三角形分割，也就是说，对于还不是三角形的多边形陆续引进对角线，一直到成为一些三角形为止，像图中③的样子。每引进一条对角线，F′和E′各增加1，而V′却不变，所以F′-E′+V′不变。因此当完全分割成三角形的时候，F′-E′+V′的值仍然没有变。有些三角形有一边或两边在平面图形的边界上。

4.如果某一个三角形有一边在边界上，例如图④中的△ABC，去掉这个三角形的不属于其他三角形的边，即AC，这样也就去掉了△ABC。这样F′和E′各减去1而V′不变，所以F′-E′+V′也没有变。

5.如果某一个三角形有二边在边界上，例如图⑤中的△DEF，去掉这个三角形的不属于其他三角形的边，即DF和EF，这样就去掉△DEF。这样F′减去1，E′减去2，V′减去1，因此F′-E′+V′仍没有变。

6.这样继续进行，直到只剩下一个三角形为止，像图中⑥的样子。这时F′=1，E′=3，V′=3，因此F′-E′+V′=1-3+3=1。

7.因为原来图形是连在一起的，中间引进的各种变化也不破坏这事实，因此最后图形还是连在一起的，所以最后不会是分散在向外的几个三角形，像图中⑦那样。

8.如果最后是像图中⑧的样子，我们可以去掉其中的一个三角形，也就是去掉1个三角形，3个边和2个顶点。因此F′-E′+V′仍然没有变。

即F′-E′+V′=1

成立，于是欧拉公式:F-E+V=2 得证。

折叠公式应用

例:足球表面由五边形和六边形的皮革拼成，计算一共有多少个这样的五边形和六边形?

答:足球是多面体，满足欧拉公式F-E+V=2，其中F,E,V分别表示面，棱，顶点的个数

设足球表面正五边形(黑皮子)和正六边形(白皮子)的面各有x个和y个，那么

面数F=x+y

棱数E=(5x+6y)/2(每条棱由两块皮子共用)

顶点数V=(5x+6y)/3(每个顶点由三块皮子共用)

由欧拉公式，x+y-(5x+6y)/2+(5x+6y)/3=2，

解得x=12。所以，共有12块黑皮子

所以，黑皮子一共有12×5=60条棱，这60条棱都是与白皮子缝合在一起的

对于白皮子来说:每块白色皮子的6条边中，有3条边与黑色皮子的边缝在一起，另3条边则与其它白色皮子的边缝在一起。

所以白皮子所有边的一半是与黑皮子缝合在一起的

那么白皮子就应该一共有60×2=120条边，120÷6=20

所以共有20块白皮子

(或者，每一个六边形的六条边都与其它的三个六边形的三条边和三个五边形的三条边连接;每一个五边形的五条边都与其它的五个六边形的五条边连接

所以，五边形的个数x=3y/5。

之前求得x=12，所以y=20

运用方法

折叠分式

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

当r=4时值为a^2+b^2+c^2+ab+bc+ca

r=5时值为a^3+b^3+c^3+ab(a+b)+bc(b+c)+ca(c+a)+abc

一般的，当r取正整数n时，有a^n/(a-b)(a-c)+b^n/(b-c)(b-a)+c^n/(c-a)(c-b) =∑ (a^i)*(b^j)*(c^k)，

其中i，j，k是非负整数，且i+j+k=n。

折叠复数

由e^iθ=cosθ+isinθ，得到:

sinθ=(e^iθ-e^-iθ)/2i

cosθ=(e^iθ+e^-iθ)/2

折叠三角形

设R为三角形外接圆半径，r为内切圆半径，d为外心到内心的距离，则:

d^2=R^2-2Rr

折叠多面体

设v为顶点数，e为棱数，f是面数，则

v-e+f=2-2p

p为欧拉示性数，例如

p=0 的多面体叫第零类多面体

p=1 的多面体叫第一类多面体

折叠多边形

设一个二维几何图形的顶点数为V，划分区域数为Ar，一笔画笔数为B,则有:V+Ar-B=1(如:矩形加上两条对角线所组成的图形，V=5,Ar=4,B=8)定理内容在同一个三角形中，它的外心Circumcenter、重心Gravity、九点圆圆心Nine-point-center、垂心Orthocenter共线。其实欧拉公式是有很多的，上面仅是几个常用的。

欧拉定理若(a,n)=1，则aφ(n)≡1 (mod n) 其中n是正整数，φ(n)是小于n且与n互素的正整数的个数,称欧拉函数。证:设R={x1,x2,...,xφ(n)}是由小于n且与n互素的全体数组成的集合，a╳R={ax1 mod n,ax2 mod n,...,axφ(n) mod n}},对a╳R中任一元素axi mod n，因a与n互素，xi与n互素，所以axi与n互素①②，又axi mod n<n，因而axi mod n∈R，所以a╳RÍR。又a╳R中任意两个元素不相同，否则从axi mod n=axj mod n，由a与n互素知，a在mod n下有乘法逆元，故xi=xj③，与假设矛盾。因此，|a╳R|=|R|，a╳R=R。而

所以aφ(n)≡1 (mod n)。 ①(A)设a,b和c是正整数，(a,b)=1，a|bc，则a|c。(涉最小公倍数证明从略) (B)设a,b和c是正整数，(a,b)=1，c|a，则(b,c)=1。证:设(b,c)=d且d>1，则有d|b，d|c。由d|c，c|a，⇒d|a。由于d|a，d|b，所以d是a和b的公因数，而a,b的最大公因数(a,b)=1，与定义矛盾，因此(b,c)=1。 (C)设a,b和c是正整数，(a,b)=1，则(a,bc)=(a,c)。证:设(a,c)=d1，(a,bc)=d2，一方面d1|a,d1|c，d2|a,d2|bc，⇒d1|a,d1|bc，⇒d1是a和bc的公因数，依定义:d1≤d2 另方面由d2|a,(a,b)=1及性质(7)得(d2,b)=1。从(d2,b)=1，d2|bc，由性质(6)得d2|c，⇒d2是a和c的公因数，依定义:d2≤d1 从而d2=d1，故(a,c)=(a,bc)。推论:若(a,b)=(a,c)=1，则(a,bc)=1。 ②根据性质gad(a,b)=gad(b，r)，有(a,n)=(axi mod n,n)=1。 ③设axi mod n=axj mod n，1≢xi，xj≢n.⇔axi≡axj(mod n)，由a与n互素知，a在mod n下有乘法逆元或消去律，⇔xi≡xj(mod n)，⇔xi mod n≡xj mod n，记xi=nq1+r,xj=nq2+r,⇒xi-xj=n(q2-q1)⇒xi=xj+n(q2-q1)，若q2≠q1⇒xi>n,所以xi=xj。 ④[(a mod m)╳(b mod m)]mod m=(a╳b) mod m ∏(axi mod n)=∏xi，∏axi≡∏xi( mod n)，aφ(n) ∏xi≡∏xi( mod n)。④ i=1 φ(n) i=1 i=1 i=1 i=1 i=1 φ(n) φ(n) φ(n) φ(n) φ(n) 由每一xi与n互素，知∏xi与n互素，∏xi在mod n下有乘法逆元。 i=1 i=1 φ(n) φ(n)

《现代密码学》，杨波，清华大学出版社，2007年4月第4章公钥密码-欧拉定理证 (a╳b) mod m=(jm+ra)╳(km+rb)mod m=((jkm+kra+jrb)m+rarb) mod m=(rarb) mod m=[(a mod m)╳(b mod m)]mod m。费尔玛定理若p是素数，a正整数，且(a,p)=1，则ap-1≡1(mod n) 证:欧拉定理取n为素数p，欧拉函数φ(p)=p-1，即得费尔玛定理。

证明如图(图是立方体，但证明是一般的，是"拓朴"的):

1.把多面体(图中①)看成表面是薄橡皮的中空立体。

6.这样继续进行，直到只剩下一个三角形为止，像图中⑥的样子。这时F′=1，E′=3，V′=3，因此F′-E′+V′=1-3+3=1。

8.如果最后是像图中⑧的样子，我们可以去掉其中的一个三角形，也就是去掉1个三角形，3个边和2个顶点。因此F′-E′+V′仍然没有变。

即F′-E′+V′=1

成立，于是欧拉公式:F-E+V=2 得证。

折叠公式应用

例:足球表面由五边形和六边形的皮革拼成，计算一共有多少个这样的五边形和六边形?

答:足球是多面体，满足欧拉公式F-E+V=2，其中F,E,V分别表示面，棱，顶点的个数

设足球表面正五边形(黑皮子)和正六边形(白皮子)的面各有x个和y个，那么

面数F=x+y

棱数E=(5x+6y)/2(每条棱由两块皮子共用)

顶点数V=(5x+6y)/3(每个顶点由三块皮子共用)

由欧拉公式，x+y-(5x+6y)/2+(5x+6y)/3=2，

解得x=12。所以，共有12块黑皮子

所以，黑皮子一共有12×5=60条棱，这60条棱都是与白皮子缝合在一起的

对于白皮子来说:每块白色皮子的6条边中，有3条边与黑色皮子的边缝在一起，另3条边则与其它白色皮子的边缝在一起。

所以白皮子所有边的一半是与黑皮子缝合在一起的

那么白皮子就应该一共有60×2=120条边，120÷6=20

所以共有20块白皮子

(或者，每一个六边形的六条边都与其它的三个六边形的三条边和三个五边形的三条边连接;每一个五边形的五条边都与其它的五个六边形的五条边连接

所以，五边形的个数x=3y/5。

之前求得x=12，所以y=20

运用方法

折叠分式

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

当r=4时值为a^2+b^2+c^2+ab+bc+ca

r=5时值为a^3+b^3+c^3+ab(a+b)+bc(b+c)+ca(c+a)+abc

一般的，当r取正整数n时，有a^n/(a-b)(a-c)+b^n/(b-c)(b-a)+c^n/(c-a)(c-b) =∑ (a^i)*(b^j)*(c^k)，

其中i，j，k是非负整数，且i+j+k=n。

折叠复数

由e^iθ=cosθ+isinθ，得到:

sinθ=(e^iθ-e^-iθ)/2i

cosθ=(e^iθ+e^-iθ)/2

折叠三角形

设R为三角形外接圆半径，r为内切圆半径，d为外心到内心的距离，则:

d^2=R^2-2Rr

折叠多面体

设v为顶点数，e为棱数，f是面数，则

v-e+f=2-2p

p为欧拉示性数，例如

p=0 的多面体叫第零类多面体

p=1 的多面体叫第一类多面体

折叠多边形

证明如图(图是立方体，但证明是一般的，是"拓朴"的):

1.把多面体(图中①)看成表面是薄橡皮的中空立体。

6.这样继续进行，直到只剩下一个三角形为止，像图中⑥的样子。这时F′=1，E′=3，V′=3，因此F′-E′+V′=1-3+3=1。

8.如果最后是像图中⑧的样子，我们可以去掉其中的一个三角形，也就是去掉1个三角形，3个边和2个顶点。因此F′-E′+V′仍然没有变。

即F′-E′+V′=1

成立，于是欧拉公式:F-E+V=2 得证。

折叠公式应用

例:足球表面由五边形和六边形的皮革拼成，计算一共有多少个这样的五边形和六边形?

答:足球是多面体，满足欧拉公式F-E+V=2，其中F,E,V分别表示面，棱，顶点的个数

设足球表面正五边形(黑皮子)和正六边形(白皮子)的面各有x个和y个，那么

面数F=x+y

棱数E=(5x+6y)/2(每条棱由两块皮子共用)

顶点数V=(5x+6y)/3(每个顶点由三块皮子共用)

由欧拉公式，x+y-(5x+6y)/2+(5x+6y)/3=2，

解得x=12。所以，共有12块黑皮子

所以，黑皮子一共有12×5=60条棱，这60条棱都是与白皮子缝合在一起的

对于白皮子来说:每块白色皮子的6条边中，有3条边与黑色皮子的边缝在一起，另3条边则与其它白色皮子的边缝在一起。

所以白皮子所有边的一半是与黑皮子缝合在一起的

那么白皮子就应该一共有60×2=120条边，120÷6=20

所以共有20块白皮子

(或者，每一个六边形的六条边都与其它的三个六边形的三条边和三个五边形的三条边连接;每一个五边形的五条边都与其它的五个六边形的五条边连接

所以，五边形的个数x=3y/5。

之前求得x=12，所以y=20

运用方法

折叠分式

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

当r=4时值为a^2+b^2+c^2+ab+bc+ca

r=5时值为a^3+b^3+c^3+ab(a+b)+bc(b+c)+ca(c+a)+abc

一般的，当r取正整数n时，有a^n/(a-b)(a-c)+b^n/(b-c)(b-a)+c^n/(c-a)(c-b) =∑ (a^i)*(b^j)*(c^k)，

其中i，j，k是非负整数，且i+j+k=n。

折叠复数

由e^iθ=cosθ+isinθ，得到:

sinθ=(e^iθ-e^-iθ)/2i

cosθ=(e^iθ+e^-iθ)/2

折叠三角形

设R为三角形外接圆半径，r为内切圆半径，d为外心到内心的距离，则:

d^2=R^2-2Rr

折叠多面体

设v为顶点数，e为棱数，f是面数，则

v-e+f=2-2p

p为欧拉示性数，例如

p=0 的多面体叫第零类多面体

p=1 的多面体叫第一类多面体

折叠多边形

证明如图(图是立方体，但证明是一般的，是"拓朴"的):

1.把多面体(图中①)看成表面是薄橡皮的中空立体。

6.这样继续进行，直到只剩下一个三角形为止，像图中⑥的样子。这时F′=1，E′=3，V′=3，因此F′-E′+V′=1-3+3=1。

8.如果最后是像图中⑧的样子，我们可以去掉其中的一个三角形，也就是去掉1个三角形，3个边和2个顶点。因此F′-E′+V′仍然没有变。

即F′-E′+V′=1

成立，于是欧拉公式:F-E+V=2 得证。

折叠公式应用

例:足球表面由五边形和六边形的皮革拼成，计算一共有多少个这样的五边形和六边形?

答:足球是多面体，满足欧拉公式F-E+V=2，其中F,E,V分别表示面，棱，顶点的个数

设足球表面正五边形(黑皮子)和正六边形(白皮子)的面各有x个和y个，那么

面数F=x+y

棱数E=(5x+6y)/2(每条棱由两块皮子共用)

顶点数V=(5x+6y)/3(每个顶点由三块皮子共用)

由欧拉公式，x+y-(5x+6y)/2+(5x+6y)/3=2，

解得x=12。所以，共有12块黑皮子

所以，黑皮子一共有12×5=60条棱，这60条棱都是与白皮子缝合在一起的

对于白皮子来说:每块白色皮子的6条边中，有3条边与黑色皮子的边缝在一起，另3条边则与其它白色皮子的边缝在一起。

所以白皮子所有边的一半是与黑皮子缝合在一起的

那么白皮子就应该一共有60×2=120条边，120÷6=20

所以共有20块白皮子

(或者，每一个六边形的六条边都与其它的三个六边形的三条边和三个五边形的三条边连接;每一个五边形的五条边都与其它的五个六边形的五条边连接

所以，五边形的个数x=3y/5。

之前求得x=12，所以y=20

运用方法

折叠分式

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

当r=4时值为a^2+b^2+c^2+ab+bc+ca

r=5时值为a^3+b^3+c^3+ab(a+b)+bc(b+c)+ca(c+a)+abc

一般的，当r取正整数n时，有a^n/(a-b)(a-c)+b^n/(b-c)(b-a)+c^n/(c-a)(c-b) =∑ (a^i)*(b^j)*(c^k)，

其中i，j，k是非负整数，且i+j+k=n。

折叠复数

由e^iθ=cosθ+isinθ，得到:

sinθ=(e^iθ-e^-iθ)/2i

cosθ=(e^iθ+e^-iθ)/2

折叠三角形

设R为三角形外接圆半径，r为内切圆半径，d为外心到内心的距离，则:

d^2=R^2-2Rr

折叠多面体

设v为顶点数，e为棱数，f是面数，则

v-e+f=2-2p

p为欧拉示性数，例如

p=0 的多面体叫第零类多面体

p=1 的多面体叫第一类多面体

折叠多边形

3.快速幂

快速幂算法，顾名思义就是求幂时速度很快
比如求3的20次幂，一般我们会用循环乘法来求，也就是需要循环20次。
但是再想想，3^20 = 9^10，这样只需要循环10次了。继续，9^10 = 81^5。
这里似乎进行不下去了，其实还可以继续，81^5 = 81*81^4 = 81*6561^2 = 81*43046721
数一下，这个步骤只有五步。DEC(20)=BIN(10100)，即：幂(BIN)有几位，循环次数就是几。

另外，判断一个数的奇偶性，不但可以使用mod 2，也可以使用 &1。他们只是在负整数部分略有不同罢了，一般求正整数幂 &1 的效率可以更高。

4.逆元（inv）

1>.什么是逆元
当求解公式：(a/b)%m 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法：
设c是b的逆元，则有b*c≡1(mod m)；
则(a/b)%m = (a/b)*1%m = (a/b)*b*c%m = a*c(mod m);
即a/b的模等于a*b的逆元的模；

逆元就是这样应用的；

2>.求逆元的方法

(1).费马小定理在是素数的情况下，对任意整数都有。如果无法被整除，则有。可以在为素数的情况下求出一个数的逆元，，即为逆元。题目中的数据范围1<=x<=10^9，p=1000000007，p是素数；所以x肯定就无法被p整除啊，所以最后就得出x^(p-2)为x的逆元啦。复杂度O(logn)；

代码：

[cpp] view plaincopy

const int mod = 1000000009;

long long quickpow(long long a, long long b) {

if (b < 0) return 0;

long long ret = 1;

a %= mod;

while(b) {

if (b & 1) ret = (ret * a) % mod;

b >>= 1;

a = (a * a) % mod;

}

return ret;

}

long long inv(long long a) {

return quickpow(a, mod - 2);

}
(2)扩展欧几里得算法求逆元
例如：4关于1模7的乘法逆元为多少？
4X≡1 mod 7
这个方程等价于求一个X和K，满足
4X=7K+1 其中X和K都是整数。求x，k就是扩展欧几里得算法了吧~
可扩展欧几里得求逆元ax≡1(mod n)其中a，n互质；
复杂度：O(logn)；
代码：

[cpp] view plaincopy

ll extend_gcd(ll a, ll b, ll &x, ll &y) {

if (b == 0) {

x = 1, y = 0;

return a;

}

else {

ll r = extend_gcd(b, a % b, y, x);

y -= x * (a / b);

return r;

}

}

ll inv(ll a, ll n) {

ll x, y;

extend_gcd(a, n, x, y);

x = (x % n + n) % n;

return x;

}

(3) 逆元线性筛 ( P为质数 )

求1,2,...,N关于P的逆元（P为质数）

复杂度：O(N)

代码：

[cpp] view plaincopy

const int mod = 1000000009;

const int maxn = 10005;

int inv[maxn];

inv[1] = 1;

for(int i = 2; i < 10000; i++)

inv[i] = inv[mod % i] * (mod - mod / i) % mod;

如果是求阶乘的逆元呢？（阶乘数组：fac[ ]）

代码：

[cpp] view plaincopy

inv[maxn]=mod_pow(fac[maxn],mod-2);

for(ll i=maxn-1;i>=0;i--)

inv[i]=(inv[i+1]*(i+1))%mod;

欧拉定理、快速幂与逆元

Color the necklace

2.欧拉定理

折叠内容

折叠证明

折叠应用

折叠内容

折叠证明

折叠定理推导

折叠定理证明

折叠实例

折叠利用几何画板

折叠公式应用

折叠分式

折叠复数

折叠三角形

折叠多面体

折叠公式应用

折叠分式

折叠复数

折叠三角形

折叠多面体

折叠多边形

折叠公式应用

折叠分式

折叠复数

折叠三角形

折叠多面体

折叠多边形

折叠公式应用

折叠分式

折叠复数

折叠三角形

折叠多面体

折叠多边形

3.快速幂

4.逆元（inv）

相关推荐