二分+找规律 之 codevs 1083 Cantor表

//  [10/11/2014 Sjm]
/*
因为是 Z 字形，所以按斜着去看它，即：斜1:1/1;  斜2:1/2, 2/1; 斜3:1/3, 2/2, 3/1; …………
二分判断出第 N 项位于斜几，再找规律，即可求出第 N 项。。。
*/

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;
#define eps 1e-8
#define MAX_LEN 10000

int main() {
    int N;
    scanf("%d", &N);
    int myLeft = 1, myRight = 10000;
    while (myRight - myLeft >= 1) {
        int myMid = myLeft + ((myRight - myLeft) >> 1);
        int myVal = (((myMid + 1)* myMid) >> 1);
        if (myVal > N) myRight = myMid;
        else {
            if (myVal < N) myLeft = myMid + 1;
            else {
                myLeft = myMid;
                break;
            }
        }
    }
    --myLeft;
    int myCount = (((myLeft + 1)* myLeft) >> 1);
    if (myLeft & 1) {
        printf("%d/%d
", N - myCount, myLeft + 2 - (N - myCount));
    }
    else {
        printf("%d/%d
", myLeft + 2 - (N - myCount), N - myCount);
    }
    return 0;
}