2010-02-06.sgu193 分類討論

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;
}

posted on 2010-02-06 16:23 schindlerlee 閱讀(162) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告