1、 数论初步1、快速幂2、约瑟夫环3、欧几里德扩展4、中国剩余定理5、欧拉函数 快速幂基于二分的原理，递归实现很简单 int exp(int x,int k) if(k = 0) return 1; int tp = exp(x,k/2); if(k return tp*tp*x; 快速幂思想 int exp(int m,int k) int b = 1; while (k 0) if (k k = k 1 ; m = (m*m); return b; 矩阵幂的思想和上边是一样的非递归实现斐波纳楔的矩阵求法：fn = fn-1 + fn-2;利用矩阵快速幂所形成的矩阵为 1,1 1,0 约瑟夫环
2、问题一： 问题描述：编号从 1到 n的 n个人站成一个环，从第一个人开始，每数到 2的时候，去除该位置上的人，直到只剩下一个人，求剩下的这个人的编号。 我们用 J(n)表示人数为 n的时候的解。约瑟夫环约瑟夫环问题一 去掉的人的编号依次为 2,4,6,8,10,3,7,1,9,最后只剩下 5，所以 J(10)=5。约瑟夫环问题一 当有偶数个人的时候，我们假设为 2n个人，经过第一圈之后还剩下 n个人。 剩下的 n个人又是一个新的约瑟夫环问题。 1 2 3 4 n-1 n 1 3 5 7 2n-3 2n-1 J(2n)=2*J(n)-1.约瑟夫环问题一 当有奇数个人的时候，我们假设为 2n+1个人，经过第一圈之后还剩下 n+1个人。去掉 2n之后，下一个要去掉的就是 1，最后还是剩下 n个人。约瑟夫环问题一 剩下的 n个人还是一个新的约瑟夫环问题。 1 2 3 4 n-1 n 3 5 7 9 2n-1 2n+1 J(2n+1)=2*J(n)+1约瑟夫环问题一
