2010-02-06.sgu193
sgu193:就是求与n互质且不大于 ⌊
n/2 ⌋ 的一个数。
按照n的奇偶分别讨论，用上大数除2和减法
const int N = 2047;
int s[N];
int r[N], sl;
int main()
{
int i, j, k;
char t;
t = getchar();
while (t != 10) {
if (t >= '0' && t <= '9') {
s[sl++] = t - '0';
}
t = getchar();
}
int fac = 0;
for (i = 0; i < sl; i++) {
fac = fac * 10 + s[i];
if (fac >= 2) {
r[i] = fac / 2;
fac %= 2;
}
}
int beg = 0;
while (r[beg] == 0) { beg++; }
if (s[sl - 1] % 2 == 0) { //even
int flag = r[sl - 1] % 2 == 1;
for (i = sl - 1; i >= beg; i--) {
if (r[i] > 0) {
r[i]--;
break;
} else {
r[i] = 9;
}
}
if (flag) { //⌊n/2⌋ - 1
for (i = sl - 1; i >= beg; i--) {
if (r[i] > 0) {
r[i]--;
break;
} else {
r[i] = 9;
}
}
}
}
while (r[beg] == 0) { beg++; }
for (i = beg;i < sl;i++) {
printf("%d",r[i]);
}
printf("\n");
return 0;
}