以及这2个系列：数据挖掘十大算法系列，程序员编程艺术。

    当然，还有很多文章或系列自己也比较喜欢（如微软面试100题系列，经典算法研究系列等等），只是上面的文章或系列更具代表性。

    但若论在上述文章或系列中，哪篇文章或系列对人找工作的帮助最大，则应该是：

• 程序员编程艺术http://blog.csdn.net/column/details/taopp.html，
• 秒杀99%的海量数据处理面试题http://blog.csdn.net/v_july_v/article/details/7382693，
• 微软面试100题系列http://blog.csdn.net/column/details/ms100.html，

    其中，尤以编程艺术系列更佳。

    OK，话休絮烦，本文讲解此文http://blog.csdn.net/v_july_v/article/details/7974418中的第75题、第79题：

• 第三十四章：格子取数问题；
• 第三十五章：完美洗牌算法的变形

    题目详情：有n*n个格子，每个格子里有正数或者0，从最左上角往最右下角走，只能向下和向右，一共走两次（即从左上角走到右下角走两趟），把所有经过的格子的数加起来，求最大值SUM，且两次如果经过同一个格子，则最后总和SUM中该格子的计数只加一次。

    题目分析：此题是去年2013年搜狗的校招笔试题。初看到此题，因为要让两次走下来的路径总和最大，读者可能最初想到的思路可能是让每一次的路径都是最优的，即不顾全局，只看局部，让第一次和第二次的路径都是最优。

    但问题马上就来了，虽然这一算法保证了连续的两次走法都是最优的，但却不能保证总体最优，相应的反例也不难给出，请看下图：

    上图中，图一是原始图，那么我们有以下两种走法可供我们选择：

• 如果按照上面的局部贪优走法，那么第一次势必会如图二那样走，导致的结果是第二次要么取到2，要么取到3，
• 但若不按照上面的局部贪优走法，那么第一次可以如图三那样走，从而第二次走的时候能取到2 4 4，很显然，这种走法求得的最终SUM值更大；

    也就是说，上面图二中的走法太追求每一次最优，所以第一次最优，导致第二次将是很差；而图三第一次虽然不是最优，但保证了第二次不差，所以图三的结果优于图二。由此可知不要只顾局部而贪图一时最优，而丧失了全局最优。

    局部贪优不行，我们可以考虑穷举，但最终将导致复杂度过高，所以咱们得另寻良策。

    @西芹_new，针对此题，可以使用直接搜索法，一共搜（2n-2）步，每一步有四种走法，考虑不相交等条件可以剪去很多枝，代码如下：

//copyright@西芹_new 2013
#include "stdafx.h"  
#include <iostream>  
using namespace std;  
  
#define N 5  
int map[5][5]={  
    {2,0,8,0,2},  
    {0,0,0,0,0},  
    {0,3,2,0,0},  
    {0,0,0,0,0},  
    {2,0,8,0,2}};  
int sumMax=0;  
int p1x=0;  
int p1y=0;  
int p2x=0;  
int p2y=0;  
int curMax=0;  
  
void dfs( int index){  
    if( index == 2*N-2){  
        if( curMax>sumMax)  
            sumMax = curMax;  
        return;  
    }  
  
    if( !(p1x==0 && p1y==0) && !(p2x==N-1 && p2y==N-1))  
    {  
        if( p1x>= p2x && p1y >= p2y )  
            return;  
    }  
  
    //right right  
    if( p1x+1<N && p2x+1<N ){  
        p1x++;p2x++;  
        int sum = map[p1x][p1y]+map[p2x][p2y];  
        curMax += sum;  
        dfs(index+1);  
        curMax -= sum;  
        p1x--;p2x--;  
    }  
  
    //down down  
    if( p1y+1<N && p2y+1<N ){  
        p1y++;p2y++;  
        int sum = map[p1x][p1y]+map[p2x][p2y];  
        curMax += sum;  
        dfs(index+1);  
        curMax -= sum;  
        p1y--;p2y--;  
    }  
  
    //rd  
    if( p1x+1<N && p2y+1<N ) {  
        p1x++;p2y++;  
        int sum = map[p1x][p1y]+map[p2x][p2y];  
        curMax += sum;  
        dfs(index+1);  
        curMax -= sum;  
        p1x--;p2y--;  
    }  
  
    //dr  
    if( p1y+1<N && p2x+1<N ) {  
        p1y++;p2x++;  
        int sum = map[p1x][p1y]+map[p2x][p2y];  
        curMax += sum;  
        dfs(index+1);  
        curMax -= sum;  
        p1y--;p2x--;  
    }  
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    curMax = map[0][0];  
    dfs(0);  
    cout <<sumMax-map[N-1][N-1]<<endl;  
    return 0;  
}  

    为了便于实现，我们认为所有不能达到的状态的得分都是负无穷，参考代码如下：

//copyright@caopengcs 2013
const int N = 202;
const int inf = 1000000000;  //无穷大
int dp[N * 2][N][N];  
bool isValid(int step,int x1,int x2,int n) { //判断状态是否合法
int y1 = step - x1, y2 = step - x2;
    return ((x1 >= 0) && (x1 < n) && (x2 >= 0) && (x2 < n) && (y1 >= 0) && (y1 < n) && (y2 >= 0) && (y2 < n));
}

int getValue(int step, int x1,int x2,int n) {  //处理越界 不存在的位置 给负无穷的值
    return isValid(step, x1, x2, n)?dp[step][x1][x2]:(-inf);
}

//状态表示dp[step][i][j] 并且i <= j, 第step步  两个人分别在第i行和第j行的最大得分 时间复杂度O(n^3) 空间复杂度O(n^3) 
int getAnswer(int a[N][N],int n) {
int P = n * 2 - 2; //最终的步数
int i,j,step;
    
    //不能到达的位置 设置为负无穷大
    for (i = 0; i < n; ++i) {
        for (j = i; j < n; ++j) {
            dp[0][i][j] = -inf;
        }
    
    }
    dp[0][0][0] = a[0][0];

      for (step = 1; step <= P; ++step) {
        for (i = 0; i < n; ++i) {
            for (j = i; j < n; ++j) {
                dp[step][i][j] = -inf;
                if (!isValid(step, i, j, n)) { //非法位置
                    continue;
                }
                //对于合法的位置进行dp
                if (i != j) {
                    dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j - 1, n));
                    dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j, n));
                    dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i, j - 1, n));
                    dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i, j,n));
                    dp[step][i][j] += a[i][step - i] + a[j][step - j];  //不在同一个格子，加两个数
                }
                else {
                    dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j - 1, n));
                    dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j,  n));
                    dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i, j,  n));
                    dp[step][i][j] += a[i][step - i]; // 在同一个格子里，只能加一次
                }
                
            }
        }
    }
    return dp[P][n - 1][n- 1];
}

    复杂度分析：状态转移最多需要统计4个变量的情况，看做是O(1)的，共有O(n^3)个状态，所以总的时间复杂度是O(n^3)的，且dp数组开了N^3大小，故其空间复杂度亦为O(n^3)。

2.3、DP实现优化版

    如上节末所说，2.2节实现的代码的复杂度空间复杂度是O(n^3)，事实上，空间上可以利用滚动数组优化，由于每一步的递推只跟上1步的情况有关，因此可以循环利用数组，将空间复杂度降为O(n^2)。
    即我们在推算dp[step]的时候，只依靠它上一次的状态dp[step – 1]，所以dp数组的第一维，我们只开到2就可以了。即step为奇数时，我们用dp[1][i][j]表示状态，step为偶数我们用dp[0][i][j]表示状态，这样我们只需要O(n^2)的空间，这就是滚动数组的方法。滚动数组写起来并不复杂，只需要对上面的代码稍作修改即可，优化后的代码如下：

//copyright@caopengcs 8/24/2013
int dp[2][N][N];

bool isValid(int step,int x1,int x2,int n) { //判断状态是否合法
int y1 = step - x1, y2 = step - x2;
    return ((x1 >= 0) && (x1 < n) && (x2 >= 0) && (x2 < n) && (y1 >= 0) && (y1 < n) && (y2 >= 0) && (y2 < n));
}

int getValue(int step, int x1,int x2,int n) {  //处理越界 不存在的位置 给负无穷的值
    return isValid(step, x1, x2, n)?dp[step % 2][x1][x2]:(-inf);
}

//状态表示dp[step][i][j] 并且i <= j, 第step步  两个人分别在第i行和第j行的最大得分 时间复杂度O(n^3) 使用滚动数组 空间复杂度O(n^2) 
int getAnswer(int a[N][N],int n) {
int P = n * 2 - 2; //最终的步数
int i,j,step,s;
    
    //不能到达的位置 设置为负无穷大
    for (i = 0; i < n; ++i) {
        for (j = i; j < n; ++j) {
            dp[0][i][j] = -inf;
        }
    
    }
    dp[0][0][0] = a[0][0];

      for (step = 1; step <= P; ++step) {
        for (i = 0; i < n; ++i) {
            for (j = i; j < n; ++j) {
                dp[step][i][j] = -inf;
                if (!isValid(step, i, j, n)) { //非法位置
                    continue;
                }
                s = step % 2;  //状态下表标
                //对于合法的位置进行dp
                if (i != j) {
                    dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j - 1, n));
                    dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j, n));
                    dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i, j - 1, n));
                    dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i, j,n));
                    dp[s][i][j] += a[i][step - i] + a[j][step - j];  //不在同一个格子，加两个数
                }
                else {
                    dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j - 1, n));
                    dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j,  n));
                    dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i, j,  n));
                    dp[s][i][j] += a[i][step - i]; // 在同一个格子里，只能加一次
                }
                
            }
        }
    }
    return dp[P % 2][n - 1][n- 1];
}

    本第34章分析完毕。

    题目详情：有个长度为2n的数组{a1,a2,a3,…,an,b1,b2,b3,…,bn}，希望排序后{a1,b1,a2,b2,….,an,bn}，请考虑有无时间复杂度o(n)，空间复杂度0(1)的解法。

    题目来源：此题是去年2013年UC的校招笔试题，看似简单，按照题目所要排序后的字符串蛮力变化即可，但若要完美的达到题目所要求的时空复杂度，则需要我们花费不小的精力。OK，请看下文详解，一步步优化。

    题目要我们怎么变换，咱们就怎么变换。此题@陈利人也分析过，在此，引用他的思路进行说明。为了便于分析，我们取n=4，那么题目要求我们把

变成

仔细观察变换前后两个序列的特点，我们可做如下一系列操作：

  第①步、确定b1的位置，即让b1跟它前面的a2，a3，a4交换：

  第②步、接着确定b2的位置，即让b2跟它前面的a3，a4交换：

  第③步、b3跟它前面的a4交换位置：

   b4已在最后的位置，不需要再交换。如此，经过上述3个步骤后，得到我们最后想要的序列。但此方法的时间复杂度为O（N^2），我们得继续寻找其它方法，看看有无办法能达到题目所预期的O（N）的时间复杂度。

当然，除了如上面所述的让b1，b2，b3，b4步步前移跟它们各自前面的元素进行交换外，我们还可以每次让序列中最中间的元素进行交换达到目的。还是用上面的例子，针对a1，a2，a3，a4，b1，b2，b3，b4

  第①步：交换最中间的两个元素a4，b1，序列变成（待交换的元素用粗体表示）：

  第②步，让最中间的两对元素各自交换：

  第③步，交换最中间的三对元素，序列变成：

    玩过扑克牌的朋友都知道，在一局完了之后洗牌，洗牌人会习惯性的把整副牌大致分为两半，两手各拿一半对着对着交叉洗牌，如下图所示：

    如果这副牌用a1 a2 a3 a4 b1 b2 b3 b4表示（为简化问题，假设这副牌只有8张牌），然后一分为二之后，左手上的牌可能是a1 a2 a3 a4，右手上的牌是b1 b2 b3 b4，那么在如上图那样的洗牌之后，得到的牌就可能是b1 a1 b2 a2 b3 a3 b4 a4。

    技术来源于生活，2004年，microsoft的Peiyush Jain在他发表一篇名为：“A Simple In-Place Algorithm for In-Shuffle”的论文中提出了完美洗牌算法。

    这个算法解决一个什么问题呢？跟本题有什么联系呢？

   Yeah，顾名思义，完美洗牌算法解决的就是一个完美洗牌问题。什么是完美洗牌问题呢？即给定一个数组a1,a2,a3,…an,b1,b2,b3..bn,最终把它置换成b1,a1,b2,a2,…bn,an。读者可以看到，这个完美洗牌问题本质上与本题完全一致，只要在完美洗牌问题的基础上对它最后的序列swap两两相邻元素即可。

   即：

通过完美洗牌问题，得到：

再让上面相邻的元素两两swap，即可达到本题的要求：

    也就是说，如果我们能通过完美洗牌算法（时间复杂度O(N)，空间复杂度O(1)）解决了完美洗牌问题，也就间接解决了本题。

    虽然网上已有不少文章对上篇论文或翻译或做解释说明，但对于初学者来说，理解难度实在太大，再者，若直接翻译原文，根本无法看出这个算法怎么一步步得来的，故下文将从完美洗牌算法的最基本的原型开始说起，以让读者能对此算法一目了然。

   为方便讨论，我们设定数组的下标从1开始，下标范围是[1..2n]。 还是通过之前n=4的例子，来看下每个元素最终去了什么地方。

起始序列：a1 a2 a3 a4 b1 b2 b3 b4
数组下标：1    2   3   4   5   6   7    8
最终序列：b1 a1 b2 a2 b3 a3 b4 a4
  从上面的例子我们能看到，前n个元素中，

• 第1个元素a1到了原第2个元素a2的位置，即1->2；
• 第2个元素a2到了原第4个元素a4的位置，即2->4；
• 第3个元素a3到了原第6个元素b2的位置，即3->6；
• 第4个元素a4到了原第8个元素b4的位置，即4->8；

  那么推广到一般情况即是：前n个元素中，第i个元素去了 第（2 * i）的位置。

  上面是针对前n个元素，那么针对后n个元素，可以看出：

• 第5个元素b1到了原第1个元素a1的位置，即5->1；
• 第6个元素b2到了原第3个元素a3的位置，即6->3；
• 第7个元素b3到了原第5个元素b1的位置，即7->5；
• 第8个元素b4到了原第7个元素b3的位置，即8->7；

    推广到一般情况是，后n个元素，第i个元素去了第  (2 * (i – n) ) – 1 =  2 * i – (2 * n + 1)  = (2 * i) % (2 * n + 1) 个位置。

   再综合到任意情况，任意的第i个元素，我们最终换到了 (2 * i) % (2 * n + 1)的位置。为何呢？因为：

1. 当0< i <n时， 原式= (2i) % (2 * n + 1)  = 2i；
2. 当i>n时，原式(2 * i) % (2 * n + 1)保持不变。

  因此，如果题目允许我们再用一个数组的话，我们直接把每个元素放到该放得位置就好了。也就产生了最简单的方法pefect_shuffle1，参考代码如下：

// 时间O(n)，空间O(n) 数组下标从1开始
void pefect_shuffle1(int *a,int n) {
int n2 = n * 2, i, b[N];
    for (i = 1; i <= n2; ++i) {
        b[(i * 2) % (n2 + 1)] = a[i];
    }
    for (i = 1; i <= n2; ++i) {
        a[i] = b[i];
    }
}

但很明显，它的时间复杂度虽然是O(n)，但其空间复杂度却是O(n)，仍不符合本题所期待的时间O(n)，空间O(1)。我们继续寻找更优的解法。

    熟悉分治法的朋友，包括若看了此文的读者肯定知道，当一个问题规模比较大时，则大而化小，分而治之。对于本题，假设n是偶数，我们试着把数组从中间拆分成两半(为了方便描述，只看数组下标就够了)：

  接下来，我们把前半段的后n/2个元素（n/2+1  ..  n）和后半段的前n/2个元素（n+1..n+n/2）交换，得到

  换言之，当n是偶数的时候，我们把原问题拆分成了A，B两个子问题，继而原n的求解转换成了n‘ = n/2 的求解。

  可当n是奇数的时候呢？我们可以把前半段多出来的那个元素a先拿出来放到末尾，后面所有元素前移，于此，新数列的最后两个元素满足已满足要求，只需考虑前2*(n-1)个元素即可，继而转换成了n-1的问题。

  针对上述n分别为偶数和奇数的情况，下面举n=4和n=5两个例子来说明下。

  ①n=4时，原始数组即为

    按照之前n为偶数时的思路，把前半段的后2个元素a3 a4同后半段的前2个元素b1 b2交换，可得：

  因此，我们只要用pefect_shuffle1算法继续求解A（a1 a2 b1 b2）和B（a3 a4 b3 b4）两个子问题就可以了。

  ②当n=5时，原始数组则为

   还是按照之前n为奇数时的思路，先把a5先单独拎出来放在最后，然后所有剩下的元素全部前移，变为：

  此时，最后的两个元素b5 a5已经是我们想要的结果，只要跟之前n=4的情况一样考虑即可。

  参考代码如下：

//copyright@caopengcs 8/23/2013
//时间O(nlogn) 空间O(1) 数组下标从1开始  
void perfect_shuffle2(int *a,int n) {  
int t,i;  
    if (n == 1) {  
        t = a[1];  
        a[1] = a[2];  
        a[2] = t;  
        return;  
    }  
    int n2 = n * 2, n3 = n / 2;  
    if (n % 2 == 1) {  //奇数的处理  
        t = a[n];  
        for (i = n + 1; i <= n2; ++i) {  
            a[i - 1] = a[i];  
        }  
        a[n2] = t;  
        --n;  
    }  
    //到此n是偶数  
      
    for (i = n3 + 1; i <= n; ++i) {  
        t = a[i];  
        a[i] = a[i + n3];  
        a[i + n3] = t;  
    }  
      
    // [1.. n /2]  
    perfect_shuffle2(a, n3);  
    perfect_shuffle2(a + n, n3);  
}  

    分析下此算法的复杂度： 每次，我们交换中间的n个元素，需要O(n)的时间，n是奇数的话，我们还需要O(n)的时间先把后两个元素调整好，但这不影响总体时间复杂度。

    故事实上，当我们采用分治算法的时候，其时间复杂度的计算公式为： T(n) = 2*T(n / 2) + O(n)  ，这个就是跟归并排序一样的复杂度式子，由《算法导论》中文第二版44页的主定理，可最终解得T(n) = O(nlogn)。至于空间，此算法在数组内部折腾的，所以是O(1)（在不考虑递归的栈的空间的前提下）。

  因为之前无论是perfect_shuffle1，还是perfect_shuffle2，这两个算法的均未达到时间复杂度O（N）并且空间复杂度O（1）的要求，所以我们必须得再找一种新的方法，以期能完美的解决本节开头提出的完美洗牌问题。

   让我们先来回顾一下2.1节位置置换perfect_shuffle1算法，还记得我之前提醒读者的关于当n=4时，通过位置置换让每一个元素到了最后的位置时，所形成的两个圈么？我引用下2.1节的相关内容：

    当n=4的情况：

起始序列：a1 a2 a3 a4 b1 b2 b3 b4
数组下标：1    2   3   4   5   6   7    8
最终序列：b1 a1 b2 a2 b3 a3 b4 a4

    即通过置换，我们得到如下结论：

    这两个圈可以表示为（1,2,4,8,7,5）和（3,6），且perfect_shuffle1算法也已经告诉了我们，不管你n是奇数还是偶数，每个位置的元素都将变为第（2*i） % （2n+1）个元素：

    因此我们只要知道圈里最小位置编号的元素即圈的头部，顺着圈走一遍就可以达到目的，且因为圈与圈是不想交的，所以这样下来，我们刚好走了O（N）步。

    还是举n=4的例子，且假定我们已经知道第一个圈和第二个圈的前提下，要让1 2 3 4 5 6 7 8变换成5 1  2 7 3 8 4：

    上面沿着圈走的算法我们给它取名为cycle_leader，这部分代码如下：

//数组下标从1开始，from是圈的头部，mod是要取模的数 mod 应该为 2 * n + 1，时间复杂度O(圈长）
void cycle_leader(int *a,int from, int mod) {
int last = a[from],t,i;
    
    for (i = from * 2 % mod;i != from; i = i * 2 % mod) {
        t = a[i];
        a[i] = last;
        last = t;
        
    }
    a[from] = last;
}

2.3.2、神级结论：若2*n=（3^k – 1），则可确定圈的个数及各自头部的起始位置

    下面我要引用此论文“A Simple In-Place Algorithm for In-Shuffle”的一个结论了，即

• 对于2*n = （3^k-1）这种长度的数组，恰好只有k个圈，且每个圈头部的起始位置分别是1,3,9，…3^(k-1)。

    论文原文部分为：

//翻转字符串时间复杂度O(to - from)
void reverse(int *a,int from,int to) {
int t;
    for (; from < to; ++from, --to) {
        t = a[from];
        a[from] = a[to];
        a[to] = t;
    }
    
}

//循环右移num位 时间复杂度O(n)
void right_rotate(int *a,int num,int n) {
    reverse(a, 1, n - num);
    reverse(a, n - num + 1,n);
    reverse(a, 1, n);
}

    上述算法流程对应的论文原文为：

//copyright@caopengcs 8/24/2013
//时间O(n)，空间O(1)
void perfect_shuffle3(int *a,int n) {
int n2, m, i, k,t;
    for (;n > 1;) {
        // step 1
        n2 = n * 2;
        for (k = 0, m = 1; n2 / m >= 3; ++k, m *= 3)
        ;
        m /= 2;
        // 2m = 3^k - 1 , 3^k <= 2n < 3^(k + 1)
        
        // step 2
        right_rotate(a + m, m, n);
        
        // step 3
        
        for (i = 0, t = 1; i < k; ++i, t *= 3) {
            cycle_leader(a , t, m * 2 + 1);
            
        }
        
        //step 4
        a += m * 2;
        n -= m;
    
    }
    // n = 1
    t = a[1];
    a[1] = a[2];
    a[2] = t;
}

//copyright@caopengcs 8/24/2013
//时间复杂度O(n)，空间复杂度O(1)，数组下标从1开始，调用perfect_shuffle3
void shuffle(int *a,int n) {
    int i,t,n2 = n * 2;
    perfect_shuffle3(a,n);
    for (i = 2; i <= n2; i += 2) {
        t = a[i - 1];
        a[i - 1] = a[i];
        a[i] = t;
        
    }
}

• 概念1    mod表示对一个数取余数，比如3 mod 5 =3，5 mod 3 =2；
• 定义1    欧拉函数ϕ(m) 表示为不超过m（即小于等于m）的数中，与m互素的正整数个数

    结合上述定义1、定义2可知，2是3的原根，因为2^0 mod 3 = 1, 2^1 mod 3 = 2, 2^2 mod 3 = 1, 2^3 mod 3 = 2，{a^0 mod m，a^1 mod m，a^2}得到集合S={1,2}，包含了所有和3互质的数，也即d=ϕ(2)=2，满足原根定义。

    而2不是7的原根，这是因为2^0 mod 7 = 1, 2^1 mod 7 = 2, 2^2 mod 7 = 4, 2^3 mod 7 = 1，2^4 mod 7 = 2，2^5 mod 7 = 4，2^6 mod 7 = 1，从而集合S={1,2,4}中始终只有1、2、4三种结果，而没包含全部与7互质的数（3、6、5便不包括）,，即d=3，但ϕ(7)=6，从而d != ϕ(7)，不满足原根定义。

    再者，如果说一个数a，是另外一个数m的原根，代表集合S = {a^0 mod m, a^1 mod m, a^2 mod m…… }，得到的集合包含了所有小于m并且与m互质的数，否则a便不是m的原根。而且集合S = {a^0 mod m, a^1 mod m, a^2 mod m…… }中可能会存在重复的余数，但当a与m互质的时候，得到的{a^0 mod m, a^1 mod m, a^2 mod m}集合中，保证了第一个数是a^0 mod m，故第一次发现重复的数时，这个重复的数一定是1，也就是说，出现余数循环一定是从开头开始循环的。

• 定义3    对模指数，a对模m的原根定义为 ,st:中最小的正整数d

    再比如，2是9的原根，因为，为了让除以9的余数恒等于1，可知最小的正整数d=6，而ϕ(m)=6，满足原根的定义。

• 定理1    同余定理：两个整数a，b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余，记作，读做a与b关于模m同余。

• 定理2    当p为奇素数且a是的原根时⇒ a也是的原根
• 定理3    费马小定理：如果a和m互质，那么a^ϕ(m) mod m = 1

• 定理4    若(a,m)=1 且a为m的原根，那么a是(Z/mZ)*的生成元。

    我们知道2是3的原根，2是9的原根，我们定义S(k)表示上述的集合S，并且x= 3^k。
    所以S(1) = {1, 2}
      S(2) = {1, 2, 4, 8, 7, 5}

    比如k = 3。 我们有：

1. S(3) = {1, 2 ,4 , 8, 16, 5, 10, 20, 13, 26, 25, 23, 19, 11, 22, 17, 7, 14} 包含了小于27且与27互质的所有数，圈的首部为1，这是原根定义决定的。
2. 那么与27最大公约数为3的数，我们用S(2)中的数乘以3得到。 S(2) * 3 = {3, 6, 12, 24, 21, 15}, 圈中元素的顺序没变化，圈的首部是3。
3. 与27最大公约数为9的数，我们用S(1)中的数乘以9得到。 S(1) * 9 = {9, 18}, 圈中得元素的顺序没变化，圈的首部是9。

    因为每个小于27的数和27的最大公约数只有1, 3, 9这3种情况，又由于前面所证的一一对应的关系，所以S(2) * 3包含了所有小于27且与27的最大公约数为3的数，S(1) * 9 包含了所有小于27且和27的最大公约数为9的数。”

     你会发现，小于27的所有自然数，要么在第一个圈里面，也就是那些和27互素的数；要么在第二个圈里面，也就是那些是3的倍数，但不是9的倍数的数；要么在第三个圈里面，也就是是9倍数的数，而之所以能够这么做，就是因为2是27的本原根。证明完毕。

    最后，咱们也再验证下上述过程：

    因为，故：

    由于n=13，2n+1 = 27，据此公式可知，上面第 i 位置的数将分别变成下述位置的：

    根据i 和 i‘ 前后位置的变动，我们将得到3个圈：

• 1248165102013262523191122177141；
• 36122421153
• 9189

    以上两个完美洗牌问题的几个扩展请读者思考，具体解答请参看参考链接第15条。

1. huangxy10，http://blog.csdn.net/huangxy10/article/details/8071242；
2. @绿色夹克衫，http://www.51nod.com/answer/index.html#!answerId=598；
3. 格子取数的蛮力穷举法：http://wenku.baidu.com/view/681c853b580216fc700afd9a.html；
4. @陈立人，http://mp.weixin.qq.com/mp/appmsg/show?__biz=MjM5ODIzNDQ3Mw==&appmsgid=10000141&itemidx=1&sign=4f1aa1a2269a1fac88be49c8cba21042；
5. caopengcs，http://blog.csdn.net/caopengcs/article/details/10196035；
6. 完美洗牌算法的原始论文“A Simple In-Place Algorithm for In-Shuffle”，http://att.newsmth.net/att.php?p.1032.47005.1743.pdf；
7. 原始根模：http://en.wikipedia.org/wiki/Primitive_root_modulo_n；
8. 洗牌的学问：http://www.thecodeway.com/blog/?p=680；
9. 关于完美洗牌算法：http://cs.stackexchange.com/questions/332/in-place-algorithm-for-interleaving-an-array/400#400；
10. 关于完美洗牌算法中圈的说明：http://www.emis.de/journals/DMTCS/pdfpapers/dm050111.pdf；
11. 关于神级结论的讨论：http://math.stackexchange.com/questions/477125/how-to-prove-algebraic-structure-of-the-perfect-shuffle（左边链接中的讨论中有错误，以在本文2.3.5节进行了相关修正）；
12. caopengcs关于神级结论的证明：http://blog.csdn.net/caopengcs/article/details/10429013；
13. 同余的概念：http://zh.wikipedia.org/wiki/%E5%90%8C%E9%A4%98；
14. 神奇的费马小定理：http://www.xieguofang.cn/Maths/Number_Theory/Fermat\’s_Little_Theorem_1.htm；
15. 完美洗牌问题的几个扩展：http://blog.csdn.net/caopengcs/article/details/10521603；
16. 原根与指数的介绍：http://wenku.baidu.com/view/bbb88ffc910ef12d2af9e738；
17. 《数论概论》Joseph H. Silverman著，推荐理由：因写上文中的完美洗牌算法遇到了一堆数论定理受了刺激，故推荐此书；

    以上第35章可能是整个系列迄今为止我最满意的一篇，不仅仅是因为此章思路清晰，过渡自然，代码风格良好，更因为有了@曹鹏博士 的加入，编程艺术如虎添翼，质量更上一层！

    :编程艺术通过解决一个个实际的编程面试题，让广大初学者一步步学会分析问题解决问题优化问题的能力，且每个问题的讲解足够通俗，希望后续我(们)做得越来越好！July、二零一三年八月二十四日凌晨零点三十七分。