初等数论中的欧拉公式
求小于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阅读全文
扩展欧几里得算法
摘要: 问题：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不为零，根据欧几里德定理，可以设...阅读全文
最优矩阵链乘
摘要: 一.问题描述 与分治法不同的是动归的子问题间不是相互独立的，前一个往往为后一个提供信息。 看下面一个例子，计算三个矩阵连乘{A1，A2，A3}；维数分别为10*100 , 100*5 , 5*50 按此顺序计算需要的次数（（A1*A2）*A3）:10X100X5+10X5X50=7500次 按此顺序计算需要的次数（A1*（A2*A3））:10X5X50+10X100X50=75000次 所以问题是：如何确定运算顺序，可以使计算量达到最小化。二.问题分析 枚举显然不可，如果枚举的话，相当于一个“完全加括号问题”，次数为卡特兰数,卡特兰数指数增长，必然不行。 令m[i][j...阅读全文
最大值最小化
摘要: 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 &阅读全文
埃及分数
摘要: 一.问题描述 在古埃及，人们使用单位分数的和(形如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. 最好的是最...阅读全文
欧拉回路
摘要: 欧拉回路：图G，若存在一条路，经过G中每条边有且仅有一次，称这条路为欧拉路，如果存在一条回路经过G每条边有且仅有一次，称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。判断欧拉路是否存在的方法 有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。 无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。 定理：无向图G具有一条欧拉路，当且仅当G是连通的，且有0个或者是两个奇数度得结点。 推论：无向图G具有一条欧拉回路，当且仅当G是连通的，并且所有结点的度数均为偶数。判断欧拉回路是否存在的方法 有向图：图连通，所有的顶点出度=入度。 无向图：...阅读全文
分类: Algorithm, Number Theory