Skip to content

14152: 【原4152】Cantor表

题目

题目描述

author: Online Judge 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4152

Description

集合论的创立人 Georg Cantor 曾给出一个表证明了有理数是可列的, 如下面所示:

1/1 1/2 1/3 1/4 1/5 ...
2/1 2/2 2/3 2/4 ...
3/1 3/2 3/3 ... 
4/1 4/2 ...
5/1 ...

按顺序列出来就是 1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, 2/3, ..., 现在给你一个正整数 n, 求第 n 项.

Input Format

一行一个正整数 n, 表示所求的项数.

Output Format

一个 a/b 式的正有理数, 表示表中的第 n 项.

Sample Input

11

Sample Output

5/1

Hint

对 40% 的数据, 1<=n<=10^6;

对 70% 的数据, 1<=n<=10^18;

对 90% 的数据, 1<=n<=10^100;

对 100% 的数据,1<=n<=10^1000.

ligongzzz's solution

#include "iostream"
#include "cstring"
#include "algorithm"
using namespace std;

//常数
constexpr auto maxNum = 10000;
constexpr auto intMax = 20;

//新无符号大整数类

class unsignedBigInt {
private:
    bool del = false;
public:
    char *ch;
    int startNum = 0;
    int len = 0;

    //初始化
    unsignedBigInt(const char *input) {
        if (del)
            delete[] ch;

        len = (strlen(input) + 1) * 2;
        startNum = strlen(input);
        ch = new char[len];
        memset(ch, 0, len);
        for (int i = 0; i < strlen(input); i++)
            ch[i + startNum] = input[i];

        del = true;
    }
    unsignedBigInt(int num) {
        if (del)
            delete[] ch;

        //临时数组
        int n = 0, temp[intMax];
        if (num == 0) {
            n = 1;
            temp[0] = 0;
        }
        else
            for (; num > 0; num /= 10)
                temp[n++] = num % 10;


        len = (n + 1) * 2;
        startNum = n;
        ch = new char[len];
        memset(ch, 0, len);

        for (int i = 0; i < n; i++)
            ch[startNum + i] = temp[n - i - 1] + '0';

        del = true;
    }
    unsignedBigInt(void) {
        if (del)
            delete[] ch;

        len = 1;
        startNum = 0;
        ch = new char[len];
        memset(ch, 0, len);

        del = true;
    }
    unsignedBigInt(int num, int sizen) {
        if (del)
            delete[] ch;

        len = (sizen + 1) * 2;
        startNum = sizen;
        ch = new char[len];
        memset(ch, 0, len);

        if (num >= 0) {
            int n = 0, temp[intMax];
            if (num == 0) {
                n = 1;
                temp[0] = 0;
            }
            else
                for (; num > 0; num /= 10)
                    temp[n++] = num % 10;

            for (int i = 0; i < n; i++)
                ch[startNum + i] = temp[n - i - 1] + '0';
        }

        del = true;
    }

    //析构
    ~unsignedBigInt() {
        if (del)
            delete[] ch;
    }

    //计算真实长度
    int realLength(const unsignedBigInt &b) {
        return strlen(b.ch + b.startNum);
    }

    //复制构造函数
    unsignedBigInt(const unsignedBigInt& b) {
        if (del)
            delete[] ch;

        len = b.len;
        startNum = b.startNum;
        ch = new char[len];
        for (int i = 0; i < len; i++)
            ch[i] = b.ch[i];

        del = true;
    }

    //输入输出
    friend ostream &operator<<(ostream &output, const unsignedBigInt &bi);
    friend istream &operator>>(istream &input, unsignedBigInt &bi);

    //赋值
    unsignedBigInt &operator=(const unsignedBigInt &b) {
        //检查自身赋值
        if (this == &b)
            return *this;

        if (del)
            delete[] ch;

        len = b.len;
        startNum = b.startNum;
        ch = new char[len];
        for (int i = 0; i < len; i++)
            ch[i] = b.ch[i];

        del = true;
        return *this;
    }
    unsignedBigInt &operator=(const char* b) {
        if (del)
            delete[] ch;

        len = (strlen(b) + 1) * 2;
        startNum = strlen(b);
        memset(ch, 0, len);

        for (int i = 0; i < strlen(b); i++)
            ch[i + startNum] = b[i];

        del = true;
        return *this;
    }
    unsignedBigInt &operator=(int num) {
        if (del)
            delete[] ch;

        //临时数组
        int n = 0, temp[intMax];
        if (num == 0) {
            n = 1;
            temp[0] = 0;
        }
        else
            for (; num > 0; num /= 10)
                temp[n++] = num % 10;


        len = (n + 1) * 2;
        startNum = n;
        ch = new char[len];
        memset(ch, 0, len);

        for (int i = 0; i < n; i++)
            ch[startNum + i] = temp[n - i - 1] + '0';

        del = true;
        return *this;
    }

    //比较符
    //小于
    bool operator<(const unsignedBigInt &b) {
        return (strcmp(ch + startNum, b.ch + b.startNum) < 0 && strlen(ch + startNum) == strlen(b.ch + b.startNum)) || strlen(ch + startNum) < strlen(b.ch + b.startNum) ? true : false;
    }

    //大于
    bool operator>(const unsignedBigInt &b) {
        return (strcmp(ch + startNum, b.ch + b.startNum) > 0 && strlen(ch + startNum) == strlen(b.ch + b.startNum)) || strlen(ch + startNum) > strlen(b.ch + b.startNum) ? true : false;
    }

    //小于等于
    bool operator<=(const unsignedBigInt &b) {
        return (strcmp(ch + startNum, b.ch + b.startNum) <= 0 && strlen(ch + startNum) == strlen(b.ch + b.startNum)) || strlen(ch + startNum) < strlen(b.ch + b.startNum) ? true : false;
    }

    //大于等于
    bool operator>=(const unsignedBigInt &b) {
        return (strcmp(ch + startNum, b.ch + b.startNum) >= 0 && strlen(ch + startNum) == strlen(b.ch + b.startNum)) || strlen(ch + startNum) > strlen(b.ch + b.startNum) ? true : false;
    }

    //等于等于
    bool operator==(const unsignedBigInt &b) {
        return strcmp(ch + startNum, b.ch + b.startNum) == 0 ? true : false;
    }

    //运算符
    //加号
    unsignedBigInt operator+(const unsignedBigInt &b) {
        unsignedBigInt temp(-1, max(realLength(*this), realLength(b)) + 2);
        int jw = 0;
        int test = realLength(*this);

        for (int i = 0; realLength(*this) > i || realLength(b) > i || jw != 0; i++) {
            //判断加数
            int j1 = realLength(*this) <= i ? 0 : ch[startNum + strlen(ch + startNum) - i - 1] - '0';
            int j2 = realLength(b) <= i ? 0 : b.ch[b.startNum + strlen(b.ch + b.startNum) - i - 1] - '0';

            //运算
            temp.ch[--temp.startNum] = (j1 + j2 + jw) % 10 + '0';
            jw = (j1 + j2 + jw) / 10;
        }

        //返回
        return temp;
    }

    //++c
    unsignedBigInt operator++() {
        *this = *this + unsignedBigInt("1");
        return *this;
    }

    //c++
    unsignedBigInt operator++(int i) {
        unsignedBigInt temp = *this;
        *this = temp + unsignedBigInt("1");
        return temp;
    }

    //减号
    unsignedBigInt operator-(const unsignedBigInt &b) {
        if (*this == b)
            return unsignedBigInt(0);

        unsignedBigInt temp(-1, max(realLength(*this), realLength(b)) + 2);
        int jw = 0;

        for (int i = 0; realLength(*this) > i || realLength(b) > i; i++) {
            //判断被减数与减数
            int j1 = realLength(*this) <= i ? 0 : ch[startNum + strlen(ch + startNum) - i - 1] - '0';
            int j2 = realLength(b) <= i ? 0 : b.ch[b.startNum + strlen(b.ch + b.startNum) - i - 1] - '0';

            //运算
            if (j1 - jw - j2 < 0) {
                temp.ch[--temp.startNum] = 10 + j1 - jw - j2 + '0';
                jw = 1;
            }
            else {
                temp.ch[--temp.startNum] = j1 - jw - j2 + '0';
                jw = 0;
            }
        }

        //修正
        for (; temp.ch[temp.startNum] == '0';)
            temp.ch[temp.startNum++] = 0;

        //返回
        return temp;
    }

    //--c
    unsignedBigInt operator--() {
        *this = *this - unsignedBigInt("1");
        return *this;
    }

    //c--
    unsignedBigInt operator--(int i) {
        unsignedBigInt temp = *this;
        *this = temp - unsignedBigInt("1");
        return temp;
    }

    //乘号
    unsignedBigInt operator*(const unsignedBigInt &b) {
        unsignedBigInt temp(0, realLength(*this) + realLength(b) + 2);
        for (int i = 0; i < strlen(b.ch + b.startNum); i++) {
            int curPos = b.startNum + strlen(b.ch + b.startNum) - 1 - i;
            unsignedBigInt addNum(-1, realLength(*this) + realLength(b) + 2);
            if (b.ch[curPos] != '0') {
                //Accelerate
                int jw = 0;
                for (int j = startNum + strlen(ch + startNum) - 1; j >= startNum || jw != 0; j--) {
                    int c1 = ch[j] == 0 ? 0 : ch[j] - '0';
                    int c2 = b.ch[curPos] == 0 ? 0 : b.ch[curPos] - '0';

                    if (c1*c2 + jw < 10) {
                        addNum.ch[--addNum.startNum] = c1 * c2 + jw + '0';
                        jw = 0;
                    }
                    else {
                        addNum.ch[--addNum.startNum] = (c1*c2 + jw) % 10 + '0';
                        jw = (c1*c2 + jw) / 10;
                    }
                }
                //Calculate
                for (int j = 0; j < i; j++)
                    addNum.ch[addNum.startNum + strlen(addNum.ch + addNum.startNum)] = '0';

                temp = temp + addNum;
            }
        }
        return temp;
    }

    //除号
    unsignedBigInt operator/(const unsignedBigInt &b) {
        //排除异常
        if (unsignedBigInt("0") == b) {
            throw "NaN";
        }

        //临时被除数
        unsignedBigInt temp(-1, max(realLength(*this), realLength(b)) + 2);
        //最终结果
        unsignedBigInt result(-1, max(realLength(*this), realLength(b)) + 2);

        for (int i = startNum; i < startNum + strlen(ch + startNum); i++) {
            //下移一位
            temp.ch[temp.startNum + strlen(temp.ch + temp.startNum)] = ch[i];
            //开始计算
            unsignedBigInt tempResult = b;
            int wr = 0;
            for (; tempResult <= temp; wr++) {
                tempResult = tempResult + b;
            }
            result.ch[result.startNum + strlen(result.ch + result.startNum)] = wr + '0';
            //计算差值
            tempResult = tempResult - b;
            if (tempResult == temp) {
                temp = unsignedBigInt(-1, max(realLength(*this), realLength(b)) + 2);
            }
            else {
                temp = temp - tempResult;
            }
        }

        //去0
        for (; strlen(result.ch + result.startNum) > 1 && result.ch[result.startNum] == '0';)
            result.ch[result.startNum++] = 0;

        return result;
    }

    //%
    unsignedBigInt operator%(const unsignedBigInt &b) {
        return *this - *this / b * b;
    }

    //+=
    void operator+=(const unsignedBigInt &b) {
        *this = *this + b;
    }

    //-=
    void operator-=(const unsignedBigInt &b) {
        *this = *this - b;
    }

    //*=
    void operator*=(const unsignedBigInt &b) {
        *this = *this * b;
    }

    // /=
    void operator/=(const unsignedBigInt &b) {
        *this = *this / b;
    }

    //%=
    void operator%=(const unsignedBigInt &b) {
        *this = *this% b;
    }
};

//输入输出流重载
//无符号大整数
ostream &operator<<(ostream &output, const unsignedBigInt &bi) {
    output << bi.ch + bi.startNum;
    return output;
}
istream &operator>>(istream &input, unsignedBigInt &bi) {
    char ch[maxNum];
    input >> ch;
    bi = unsignedBigInt(ch);
    return input;
}

int main() {

    char ch[2000] = { 0 };
    cin >> ch;

    unsignedBigInt input(ch);
    //cout << "输入的数据是:" << endl<<input << endl;

    //开根号
    int cnt = 0;
    ch[strlen(ch) / 2] = 0;
    unsignedBigInt temp1 = input * 2, temp = ch, y, jd("999999");

    for (; cnt < 1000; cnt++) {
        if (y < temp&&temp - y < jd)
            break;
        else if (y >= temp && y - temp < jd)
            break;
        y=temp;
        temp = (temp + temp1 / temp) / 2;
    }
    //cout << "循环了" << cnt << "次" << endl;
    unsignedBigInt i = temp, j = (temp+1)*temp/2;
    //cout << i << endl << j << endl;
    if (j < input)
        for (; j < input; j += i)
            ++i;
    else {
        for (; j >= input; i--)
            j -= i;
        ++i;
        j += i;
    }

    if (i % 2 == 1)
        cout << j + 1 - input << "/" << input + i - j;
    else
        cout << input + i - j << "/" << j + 1 - input;

    return 0;
}

Neight99's solution

#include <cstring>
#include <iomanip>
#include <iostream>
using namespace std;

class bigint {
   private:
    static const int base = 1e8, pow = 8;
    long long data[1000];
    int length;

   public:
    bigint();
    bigint(const char *);
    bigint(const bigint &);
    void operator+=(const long long &);
    bigint operator+(const bigint &) const;
    void operator+=(const bigint &);
    bigint operator-(const bigint &) const;
    void operator-=(const bigint &);
    void operator*=(const bigint &);
    bigint operator*(const bigint &)const;
    void operator*=(const long long &);
    bigint operator*(const long long &)const;
    void operator/=(const long long &);
    bigint operator/(const long long &) const;
    bigint operator=(const bigint &);
    bool operator<(const bigint &) const;
    bool operator<=(const bigint &) const;
    bool operator==(const bigint &) const;
    bool operator>(const bigint &) const;
    int mod2() const;
    void output() const;
};

bigint::bigint() : length(0) { memset(data, 0, sizeof(data)); }

bigint::bigint(const char *str) {
    memset(data, 0, sizeof(data));
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        data[(len - i - 1) / 8] = data[(len - i - 1) / 8] * 10 + str[i] - '0';
    }
    length = (len - 1) / 8 + 1;
}

bigint::bigint(const bigint &right) {
    if (this != &right) {
        memset(data, 0, sizeof(data));
        length = right.length;
        for (int i = 0; i < length; i++) {
            data[i] = right.data[i];
        }
    }
}

bigint bigint::operator=(const bigint &right) {
    if (this != &right) {
        memset(data, 0, sizeof(data));
        length = right.length;
        for (int i = 0; i < length; i++) {
            data[i] = right.data[i];
        }
    }

    return *this;
}

void bigint::operator+=(const long long &right) {
    data[0] += right;
    for (int i = 0; i < length; i++) {
        data[i + 1] += data[i] / base;
        data[i] %= base;
    }
    while (data[length] > 0) {
        length++;
    }
}

void bigint::operator+=(const bigint &right) {
    length = (length > right.length) ? length : right.length;
    for (int i = 0; i < length; i++) {
        data[i] += right.data[i];
        data[i + 1] += data[i] / base;
        data[i] %= base;
    }

    while (data[length] > 0) {
        length++;
    }
}

bigint bigint::operator+(const bigint &right) const {
    bigint temp = *this;
    temp += right;

    return temp;
}

void bigint::operator-=(const bigint &right) {
    for (int i = 0; i < length; i++) {
        data[i] -= right.data[i];
        while (data[i] < 0) {
            data[i] += base;
            data[i + 1]--;
        }
    }

    while (data[length - 1] <= 0 && length > 0) {
        --length;
    }
}

bigint bigint::operator-(const bigint &right) const {
    bigint temp = *this;
    temp -= right;
    return temp;
}

bigint bigint::operator*(const bigint &right) const {
    bigint temp;
    temp.length = length + right.length - 1;

    for (int i = 0; i < length; i++) {
        for (int j = 0; j < right.length; j++) {
            temp.data[i + j] += data[i] * right.data[j];
        }
    }
    for (int i = 0; i < temp.length; i++) {
        temp.data[i + 1] += temp.data[i] / base;
        temp.data[i] %= base;
    }

    while (temp.data[temp.length] > 0) {
        temp.length++;
        temp.data[temp.length] += temp.data[temp.length - 1] / base;
        temp.data[temp.length - 1] %= base;
    }

    return temp;
}

void bigint::operator*=(const bigint &right) {
    bigint temp = *this;
    temp = temp * right;
    *this = temp;
}

void bigint::operator*=(const long long &right) {
    for (int i = 0; i < length; i++) {
        data[i] *= right;
    }
    for (int i = 1; i < length; i++) {
        data[i + 1] += data[i] / base;
        data[i] %= base;
    }
}

bigint bigint::operator*(const long long &right) const {
    bigint temp = *this;
    temp *= right;
    return temp;
}

void bigint::operator/=(const long long &right) {
    bigint base1("100000000");
    for (int i = length - 1; i > 0; i--) {
        data[i - 1] += (data[i] % right * base);
        data[i] /= right;
    }
    data[0] /= right;

    while (length > 0 && data[length - 1] <= 0) {
        length--;
    }
}

bigint bigint::operator/(const long long &right) const {
    bigint temp = *this;
    temp /= right;

    return temp;
}

int bigint::mod2() const { return data[0] % 2; }

bool bigint::operator<(const bigint &right) const {
    if (length != right.length) {
        return length < right.length;
    }

    for (int i = length - 1; i >= 0; i--) {
        if (data[i] != right.data[i]) {
            return data[i] < right.data[i];
        }
    }
    return 0;
}

bool bigint::operator<=(const bigint &right) const {
    return (*this < right) || (*this == right);
}

bool bigint::operator==(const bigint &right) const {
    if (length != right.length) {
        return 0;
    } else {
        for (int i = 0; i < length; i++) {
            if (data[i] != right.data[i]) {
                return 0;
            }
        }
        return 1;
    }
}

bool bigint::operator>(const bigint &right) const {
    return (!(*this < right)) && (!(*this == right));
}

void bigint::output() const {
    printf("%lld", data[length - 1]);
    for (int i = length - 2; i >= 0; i--) {
        printf("%08lld", data[i]);
    }
}

bool check(bigint &N, bigint &mid) {
    bigint one("1");
    if (mid * (mid + one) / 2 < N) {
        return 1;
    } else {
        return 0;
    }
}

int main() {
    char n[10000];
    scanf("%s", n);
    bigint N(n), N1 = N, one("1"), zero("0"), line;

    while (zero <= N1) {
        bigint mid = (zero + N1) / 2;
        if (check(N, mid)) {
            zero = mid + one;
            line = mid;
        } else {
            N1 = mid - one;
        }
    }
    line += one;

    if (line.mod2() != 0) {
        bigint temp1 = (line * (line + one)) / 2,
               temp2 = (((line - one) * line) / 2);
        bigint temp3 = N - temp2, temp4 = line + one - temp3;
        temp4.output();
        printf("%c", '/');
        temp3.output();
    } else {
        bigint temp1 = (line * (line + one)) / 2,
               temp2 = (((line - one) * line) / 2);
        bigint temp3 = N - temp2, temp4 = line + one - temp3;
        temp3.output();
        printf("%c", '/');
        temp4.output();
    }

    return 0;
}

WashSwang's solution

#include <iostream>
#include <cstring>
#include <iomanip>

using namespace std;
const int p=1000000000;
//Attention! This class is not complete (It may make mistakes if you apply it in other problems).
class longint{

    long long num[3000];
    int len;
public:
    longint(){
        memset(num,0,sizeof(num));
        len=1;
    };

    longint(const char *s){
        memset(num,0,sizeof(num));
        int l=(strlen(s)-1)/9+1,length=strlen(s);
        for (int i=0;i<l;++i){
            for (int j=length-9*i-9;j<length-9*i;++j)
            if (j>=0)
                num[i]=num[i]*10+s[j]-48;
        }
        len=l;
    }

    longint(int x){
        memset(num,0,sizeof(num));
        len=0;
        while (x!=0)
        {
            num[len++]=x%p;
            x/=p;
        }
    }

    longint(const longint &a):len(a.len){
        memset(num,0,sizeof(num));
        for (int i=0;i<a.len;++i)
            num[i]=a.num[i];
    }

    longint &operator=(const longint& a){
        memset(num,0,sizeof(num));
        len=a.len;
        for (int i=0;i<a.len;++i)
            num[i]=a.num[i];
        return *this;
    }

    friend longint operator+(const longint& a,const longint& b){
        long long c=0;
        longint r;
        r.len=max(a.len,b.len);
        for (int i=0;i<r.len;++i){
            r.num[i]=a.num[i]+b.num[i]+c;
            c=r.num[i]/p;
            r.num[i]%=p;
        }
        if (c>0) r.num[r.len++]=c;
        return r;
    }

    friend longint operator-(const longint& a,const longint& b){
        int c=0;
        longint r;
        r.len=max(a.len,b.len);
        for (int i=0;i<max(a.len,b.len);++i){
            r.num[i]=a.num[i]-b.num[i]-c;
            c=0;
            if (r.num[i]<0){
                r.num[i]+=p;
                c=1;
            }
        }
        while (r.len>1&&!r.num[r.len-1]) r.len--;
        return r;
    }

    friend longint operator*(const longint& a,const longint& b){
        long long c=0,pos;
        int x=0;
        longint r;
        for (int i=0;i<b.len;++i){
            x=i;
            c=0;
            longint tmp;
            for (int j=0;j<a.len;++j){
                pos=a.num[j]*b.num[i]+c;
                c=pos/p;
                tmp.num[x]=pos%p;
                x++;
            }
            tmp.len=x;
            if (c>0) tmp.num[tmp.len++]=c;
            r=r+tmp;
        }
        return r;
    }

    friend longint div(const longint& a){
        longint r;
        long long x=0;
        for (int i=a.len-1;i>=0;i--){
            x=x*p+a.num[i];
            r.num[i]=x/2;
            x%=2;
        }
        r.len=a.len;
        if (!r.num[r.len-1]) r.len--;
        return r;
    }

    friend bool operator>(const longint& a,const longint& b){
        if (a.len>b.len) return true;
        if (a.len<b.len) return false;
        for (int i=a.len-1;i>=0;--i){
            if (a.num[i]>b.num[i]) return true;
            if (a.num[i]<b.num[i]) return false;
        }
        return false;
    }

    friend ostream& operator<<(ostream& os,const longint &a){
        os.fill('0');
        os<<a.num[a.len-1];
        for (int i=a.len-2;i>=0;--i) {
            os<<setw(9)<<a.num[i];
        }
        return os;
    }

    friend bool odd(longint &a){
        return a.num[0]%2!=0;
    }
};
char s[2000];
int main() {
    cin>>s;
    longint l,r(s),t(s),n(s),mid;
    r=(r-1)*2;
    t=(t-1)*2;
    while (!(l>r)){
        mid=div(l+r);
        if (mid*(mid+1)>t) r=mid-1;
        else l=mid+1;
    }
    l=l-1;
    n=n-div(l*(l+1));
    if (odd(l))
        cout<<n<<"/"<<l+2-n;
    else
        cout<<l+2-n<<"/"<<n;
    return 0;
}