题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1313
题目意思：有 N 个人（编号依次为1~N）围成一个圆圈，要求求出最大的 K （1 ≤ K ≤ N/2），表示从编号为1的人开始，将球传递给他后一个人数起的第K个人，第K个人又传递给往后数的第K个人......要求这样传递下去，且每个人都有机会接到球。也就是不存在当未使得全部人都接到一次球的情况下，某个人接收到两次以上的球。
详细的解题报告在这里：
http://blog.watashi.ws/623/andrew-stankevich-1-solutio/
而参考了这个人的写法，我也写出了属于自己的，happy ^_^~~~
http://www.xuebuyuan.com/1552889.html
比赛的时候，通过枚举小例子，只推出这个公式：
(1) N 为奇数的时候：
K = N / 2
(2) N 为偶数的时候
算出 (N-2)/2，分两种情况讨论。
(i) (N-2)/2 是奇数，K 就为 (N-2)/2
(ii) (N-2)/2 是偶数，K 就为 (N-2)/2 - 1。
例如：N = 16，K = (16-2)/2 = 7
N = 18，K = （18-2) / 2 - 1 = 7
因为 N 十分大，需要用到高精度处理。
其实我找出的规律也是正确的，只是不同表示而已~~~
对于代码中偶数需要分情况讨论，除了都需要将N/2 算完之后还需要减1操作，还要进一步讨论的原因。还是拿回16 和 18 来讲。16/2 - 1 之后是一个奇数，也就是结果啦，但是对于18，18/2 -1 = 8，正确结果应该是7，所以如果操作完第一次的除以2再减1之后发现最后那位是偶数，还需要继续执行多一步的减1操作。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; const int maxn = + ;
int num[maxn];
char str[maxn]; inline int CharToInt(char i)
{
return (i - '');
} void Div(int num[], int len)
{
int i = , f = ;
while (i < len)
{
if (num[i] & )
num[i+] += ;
num[i++] = (num[i] == && f ? : num[i]>>); // 第一位有可能是1
f = ;
}
} void Minus(int num[], int len)
{
int i = len-;
while (i >= && num[i] == ) // 防止类似100000的情况
num[i--] = ;
num[i] -= ; // 末尾不是0的话，直接从最后一位减1即可。
} inline void Print(int num[], int len)
{
int i = ;
if (num[i] == ) // 过滤前导零
i++;
for ( ; i < len; i++)
printf("%d", num[i]);
printf("\n");
} int main()
{
int T;
while (scanf("%d", &T) != EOF)
{
while (T--)
{
memset(num, , sizeof(num));
scanf("%s", str); // 如果前面用getchar()再用gets(str)会OutputlimitExceeded
int len = strlen(str);
for (int i = ; i < len; i++)
num[i] = CharToInt(str[i]);
if (num[len-]&) // 奇数直接等于n/2;
{
Div(num, len);
Print(num, len);
}
else
{
Div(num, len);
Minus(num, len); // 偶数分情况讨论
if (num[len-] & )
Print(num, len);
else
{
Minus(num, len);
Print(num, len);
}
}
if (T)
puts("");
}
}
return ;
}
对于 http://blog.watashi.ws/623/andrew-stankevich-1-solutio/ 这个人的写法中
int *Mul(int *num)
{
for(int i=0;i<n;i++){
if(num[i]&1) num[i+1]+=10;
num[i]>>=1;
}
num[n]=0; /* 这部分写得很妙，应该就是为了处理前导0的情况， 简洁方便 */
while(*num==0){
++num;
n--;
}
return num;
}