本文仅供娱乐，切莫当真 

感谢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必须实现高效率乘除法，这个细节就不在这里讨论了，呵呵