欧拉公式
初等数论中的欧拉公式
求小于n的数里，与n互为素数的个数
一.
奇数和偶数是否一定互素（排除1）；1和不和任意数互素(比如6采用欧拉定理验证下)。
若n已经进行唯一分解，直接欧拉公式。
如果n的标准素因子分解式是p1^a1*p2^a2*……*pm^am，其中众pj(j=1,2,……,m)都是素数，而且两两不等。则有 φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm) 利用容斥原理可以证明它。
二.不知唯一分解
1 #include<iostream>
2 #include<stdio.h>
3 using namespace std;
4
5 int main()
6 {
7 int n,i;
8 double sum;
9 while (scanf( " %d " ,&n)&& n)
10 {
11 sum= n;
12 // 还是运用了欧拉公式
13 if (n% 2 == 0 ) // 2也是素数
14 {
15 sum*=( double )( 1 - 1.0 / 2 ); // 为了突出关系写成了 (1 - 1.0/2) ,里面一定是1.0
16 while (n% 2 == 0 )
17 n/= 2 ;
18 }
19
20 /* 类似筛法的思想，已经去掉了2及其倍数，下面找奇因子，必须从小到大枚举，
21 3枚举到的话立马除尽3及其倍数防止再次枚举9（这样就不对了）
22 */
23 for (i= 3 ;n> 1 ;i+= 2 )
24 {
25 if (n%i== 0 )
26 sum*=( 1 -( double ) 1 / i);
27 while (n%i== 0 )
28 n/= i;
29 }
30 printf( " %d\n " ,( int )sum);
31 }
32 // while(1);
33 return 0 ;
34 }
Algorithm
初等数论中的欧拉公式
摘要: 求小于n的数里，与n互为素数的个数一. 奇数和偶数是否一定互素（排除1）；1和不和任意数互素(比如6采用欧拉定理验证下)。 若n已经进行唯一分解，直接欧拉公式。 如果n的标准素因子分解式是p1^a1*p2^a2*……*pm^am，其中众pj(j=1,2,……,m)都是素数，而且两两不等。则有 φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm) 利用容斥原理可以证明它。二.不知唯一分解 1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 5 int main() 6 { 7 in 阅读全文
posted @ 2013-04-15 22:43 HPU-张朋飞 阅读(34) | 评论 (0) 编辑
扩展欧几里得算法
摘要: 问题：ax+by=c，已知a、b、c，求解使该等式成立的一组x，y。其中a、b、c、x、y均为整数 a,b的最大公约数为gcd(a,b)。如果c不是gcd(a,b)的倍数，则该等式无解，因为等式左边除以gcd(a,b)是整数，而等式右边除以gcd(a,b)后为小数。因此，只有当c是gcd(a,b)的倍数的时候，该等式有解。这样，可以通过计算使ax1+by1=gcd(a,b)成立的x1、y1，然后有x=(c/gcd(a,b))*x1，y=(c/gcd(a,b))*y1，得到x,y。 问题就被转换为求使ax+by=gcd(a,b)成立的一组x,y。 如果b不为零，根据欧几里德定理，可以设... 阅读全文
posted @ 2013-04-15 08:26 HPU-张朋飞 阅读(196) | 评论 (2) 编辑
最优矩阵链乘
摘要: 一.问题描述 与分治法不同的是动归的子问题间不是相互独立的，前一个往往为后一个提供信息。 看下面一个例子，计算三个矩阵连乘{A1，A2，A3}；维数分别为10*100 , 100*5 , 5*50 按此顺序计算需要的次数（（A1*A2）*A3）:10X100X5+10X5X50=7500次 按此顺序计算需要的次数（A1*（A2*A3））:10X5X50+10X100X50=75000次 所以问题是：如何确定运算顺序，可以使计算量达到最小化。二.问题分析 枚举显然不可，如果枚举的话，相当于一个“完全加括号问题”，次数为卡特兰数,卡特兰数指数增长，必然不行。 令m[i][j... 阅读全文
posted @ 2013-04-14 22:23 HPU-张朋飞 阅读(46) | 评论 (2) 编辑
最大值最小化
摘要: 1 //目标学会用猜数字（二分）的方法，换个角度来解决问题 2 #include<stdio.h> 3 #include<string.h> 4 #include<stdlib.h> 5 const int N = 100000; 6 7 int a[N],n,m,max; 8 9 void input()10 {11 scanf("%d%d",&n,&m);12 max=0;13 for(int i=0;i<n;i++) 14 {15 scanf("%d",&a[i]);16 max & 阅读全文
posted @ 2013-04-12 18:20 HPU-张朋飞 阅读(3) | 评论 (0) 编辑
埃及分数
摘要: 一.问题描述 在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。对于一个分数a/b,表示方法有很多种，但是哪种最好呢？ 首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。 如： 19/45=1/3 + 1/12 + 1/180 19/45=1/3 + 1/15 + 1/45 19/45=1/3 + 1/18 + 1/30, 19/45=1/4 + 1/6 + 1/180 19/45=1/5 + 1/6 + 1/18. 最好的是最... 阅读全文
posted @ 2013-04-11 13:13 HPU-张朋飞 阅读(3) | 评论 (0) 编辑
欧拉回路
摘要: 欧拉回路：图G，若存在一条路，经过G中每条边有且仅有一次，称这条路为欧拉路，如果存在一条回路经过G每条边有且仅有一次，称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。判断欧拉路是否存在的方法 有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。 无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。 定理：无向图G具有一条欧拉路，当且仅当G是连通的，且有0个或者是两个奇数度得结点。 推论：无向图G具有一条欧拉回路，当且仅当G是连通的，并且所有结点的度数均为偶数。判断欧拉回路是否存在的方法 有向图：图连通，所有的顶点出度=入度。 无向图：... 阅读全文
posted @ 2013-04-08 09:54 HPU-张朋飞 阅读(532) | 评论 (0) 编辑
拓扑排序
摘要: 一.概念 由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。二.拓扑排序方法如下: (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它. (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边. (3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.三.算法实现 1.普通实现 1 #include<iostream> 2 #include<stdlib.h> 3 #include<stdio.h> 4 #define MAX 100 5 using namespace std; 6 7 void toposort(i 阅读全文
posted @ 2013-04-07 12:57 HPU-张朋飞 阅读(20) | 评论 (0) 编辑
分类: Algorithm , Number Theory
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息