百度二面经历，与大家分享
面试开始，问了些无关痛痒的话，然后面试官说了句，你数学怎么样。我说还行，然后就说了句：“我最喜欢数学题，我们来做几个数学题吧”，然后我就开始悲剧了。
第一题，任意给一个数，试证明这个数的某个倍数的十进制表示是01串，比如3的倍数111是二进制表示，5的倍数10是二进制表示，等等。
第二题，素数有无穷多个，请问是怎么证明的。
第三题，给一个很大的数组，里面有两个数只出现过一次，其他数都出现过两次，把这两个数找出来。
我开始说了排序和哈希表，他问我还有没有更好的方法，然后我说用异或，异或了半天没弄出来。
第四题，把一个链表逆过来，要求空间复杂度O(1)，这个算简单的。
至此我的二面就此结束，数学题惨不忍睹，没思及此，伤心欲绝。
各位有什么好的方法请不吝指教。

[解决办法]
第三题很简单的，解法如下：
假设这两个数为a，b，将数组中所有元素异或结果是x=a^b，判断x中位为1的位数（注：因为a！=b，所以x！=0，我们只需知道某一个位为1的位数k，例如0010 1100，我们可取k=2或者3，或者5），然后将x与数组中第k位为1的数进行异或，异或结果就是a，b中一个，然后用x异或，就可以求出另外一个。
为什么呢？因为x中第k位为1表示a或b中有一个数的第k位也为1，假设为a，我们将x与数组中第k位为1的数进行异或时，也就是将x与a外加上其他第k位为1的出现过偶数次的数进行异或，化简即为x与a异或，结果是b。
代码如下：

C/C++ code

void getNum(int a[],int length){    int s = 0;//保存异或结果    for(int i=0;i<length;i++)    {        s=s^a[i];    }    int temp1 = s;     //临时保存异或结果    int temp2 = s;     //临时保存异或结果    int k=0;    while((temp1&1) == 0)        //求异或结果中位为1的位数    {        temp1 = temp1>>1;        k++;    }    for(int i=0;i<length;i++)    {        if((a[i]>>k)&1)          //将s与数组中第k位为1的数进行异或，求得其中一个数        {            //cout<<a[i]<<" ";            s=s^a[i];        }    }    cout<<s<<" "<<(s^temp2)<<endl;             //(s^temp2)用来求另外一个数}
[解决办法]
探讨


第二个数学题很难啊

[解决办法]
晕第一题也不算特别难，抽屉原则就可以了，不过面试估计还是想不出
对一个数X，那么从1，10，100，......10^(x*x+1）取模，必然会有x个相同的值，将这x值相加就可以了

[解决办法]
探讨


晕第一题也不算特别难，抽屉原则就可以了，不过面试估计还是想不出
对一个数X，那么从1，10，100，......10^(x*x+1）取模，必然会有x个相同的值，将这x值相加就可以了