本文仅供娱乐，切莫当真 

感谢grant, liu, molly。 没有你们的帮忙我不可能完成这篇文章，谢谢大家

原题：5个水手在岛上发现一堆椰子， 夜晚睡觉后，第一名水手把椰子分为等量的5堆，还剩下一个给了猴子，自己藏起一堆。第二个水手把剩下的4堆混合后重新分为 等量的5堆，剩下一个给了猴子；自己藏起一堆。第三第四第五位水手依此办理。天亮以后，大家把剩下的椰子分为等量的5堆，剩下一个给了猴子。问原来这堆椰子最少为多少个。

for(i=0;i<=10000;i++){
    check(i);
}

printf("Please enter the number of pirates\n");
scanf("%d",&x);
for(i=0;i<=1000000;i++){  
    check(i,x);
}

#define NUM 5
//i是最后一次剩下的椰子个数
for(i=NUM-1;i<=INT_MAX;i+=NUM-1){
    check(i,NUM);
}

#define NUM_PIRATE 5
#define NUM_MONKEY 1

LARGEINT a,b,c,x,y;

//from last pirate to first, recursively solve (n-1)x=ny+1
a=NUM_PIRATE-1;
b=-NUM_PIRATE;
c=NUM_MONKEY;
for(i=0;i<NUM_PIRATES;i++){
//this function solves ax+by=c by extended-euclid algorithm
    extended_euclid(a, b, c, &x, &y); 
    b=b*NUM_PIRATE;
    c=NUM_MONKEY+NUM_PIRATE*x;
}
return NUM_PIRATE*x+NUM_MONKEY;

数学家

他们不写程序，他们发现椰子的数量是下面这个方程的正整数解：

接着他们手算欧几里得算法来解这个方程

#define NUM_PIRATE 5
#define NUM_MONKEY 1

LARGEINT a,b,c,x,y;

//这式子是不是很眼熟？
a=pow(NUM_PIRATE-1,NUM_PIRATE);
b=-pow(NUM_PIRATE,NUM_PIRATE+1);
c=(-b-a*(NUM_PIRATE-1))*NUM_MONKEY;
extended_euclid(a,b,c,&x,&y）;
return x;

echo 15621

P.S. 本文的代码简化了很多细节，譬如说求解ax+by=c的时候，欧几里得算法只应用于c=gcd(a,b)的情况，但本题中c=k*gcd(a,b)。而且，我们需要求的是最小正整数解，而不是任意一组解。还有一个就是LARGEINT必须实现高效率乘除法，这个细节就不在这里讨论了，呵呵

本文写于2011-03-08

感谢mike，雪瑶姐，utd帮助我完成了这篇文章

题目：有n个数，其中绝大部分数出现了正好3次，只有一个数只出现了1次，请写一段程序把这个数找出来

解法1： 建一个hash table，把number作为key，遍历数组一遍，对出现过的数进行计数，最后再遍历一遍找到只出现一次的数。

空间复杂度:length(为了时间上高效，一般length要取到Theta(n))

时间复杂度： n^2/length+0.5n（n时间遍历一遍，每次要查找n/length的hash table,最后再遍历一遍）

解法2：对数组进行select，对小于pivot与大于pivot的数分别计数，对不能被3整除的一边进行递归调用。

 空间复杂度：如果不在乎源数据被改变是可以仅用O(1)的空间的，但通常来讲需要O(n)空间来备份

 时间复杂度：O(n)

解法3（感谢雪瑶姐提供）:

public static int findSpecial(int[] array){
int ones = 0;  //出现1次的1
int twos = 0; //出现2次的1
int not_threes;  //出现3次的1取反

for(int i :array){
twos |= ones & i; 
ones ^= i;
not_threes = ~(ones&twos);
ones &= not_threes;
twos &= not_threes;
}
return ones;
}
} 
 空间复杂度O(1),时间复杂度也是O(n),不会改变原数组，应该是最好的算法了

但是，这道题的讨论还没有完。假如把题目改成“有n个数，其中绝大部分数出现了正好2次，只有一个数出现了1次，请把这个数找出来” 有一个只需遍历一遍且不用额外空间的算法：把所有数字异或一遍，最后结果就是只出现1次的那个数。 那么，可能有人会想，在这道题的条件下，是不是也存在一个类似于异或的运算符#，可以仅把所有数#一遍以后就得到结果呢？、

答案是否定的。假如存在这个运算符#，那它必须满足下面这些条件：

 A={所有32位2进制数}  #:A->A
交换律 a#b=b#a
结合律 a#b#c=a#(b#c)
存在e 对于任意a a#e=a
对于任意a a#a#a=e

我们可以证明满足上面条件的运算符不存在：

首先我们定义一个负元-a：a#-a=e
由a#a#a=e 可知-a存在,根据结合律，-a=a#a (1)
假设-a不唯一,-a=b或c, 那么a#b#c=(a#b)#c=c=(a#c)#b=b（交换律&结合律）矛盾 (2)
由（1）（2）可知，-a存在且唯一。显然，-e=e
由交换律可知，如果a#b=e=>b#a=e，所以负元这个relation是可逆的, -a=b => -b=a
因为-e=e并且A是一个有限偶数项集合
所以必定还有一个数x，-x=x
那么x#x#x=e#x=x与题设里x#x#x=e矛盾

综上所述，这个运算符并不存在

感谢UTD同学在证明上的帮助