# 14152: 【原4152】Cantor表

### 题目描述

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

## Description

``````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 ...
``````

## Sample Input

``````11
``````

## Sample Output

``````5/1
``````

## 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) {
jw = 0;
}
else {
jw = (c1*c2 + jw) / 10;
}
}
//Calculate
for (int j = 0; j < i; j++)

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