庞大的数字，从更加庞大的视角来看呢？—— 高精度

总体思想

因为数据结构的局限性，int 可以存下 $9$ 位数，long long 可以存下 $20$ 位数，__int128 可以存下 $39$ 位数 ，之后我们就只能使用更大的存储方式，高精度就是使用数组存储的数据结构。

其实现方式就是，使用字符串输入，数组模拟计算方式。

实现

输入

由于没有足够大的数据类型去装下及其大的整数，所以，我们可以使用字符串读入。由于数字比较大，使用 string 可能会出现问题，所以使用 char 数组。（高精乘复杂度 $O(n^2)$ ，所以涉及到高精乘的 $n$ 不会特别大）

1
2
3
4
5
6
7
int a[2010];

string s;
cin>>s;
for(int i=0, len=s.length(); i<len; i++){
	a[i]=s[len-i-1];//为了方便进位，我们把数字倒着存储
}

计算

接下来，我们预处理好两个参与运算的数字的数组后，我们要开始模拟运算。

我们来思考，在我们小学刚刚学加减乘除时，使用的方法是什么（（

  1. 加法：按位加法，然后处理进位，进一位代表 $10$ 。
  2. 减法：按位减法，减不下时从前接一位，退一位代表 $10$ 。
  3. 乘法：一开始时我们学的是一个一个加，但显而易见是会超时的。我们通过观察竖式的乘法发现，第 $i$ 位乘上第 $j$ 位的数值会贡献给 $i+j$ 位，所以只需要 $O(n^2)$ 枚举每一位相乘就可以了
  4. 除法：同乘法一样，一个一个减是会超时的，所以我们观察竖式，从高位往低位减就可以了。

代码在之后的模板处会有讲解

输出

计算完成，我们要开始输出了。我们发现，在运算过程中进位的数量是不确定的，所以我们可以直接从数组的最后一个位置开始往前枚举。

1
2
3
4
5
int len=2000;
while(len>1&&a[len]==0) len--;
for(int i=len; i>=1; i--){
	cout<<a[i];
}

模板

这边直接给出一个封装完的大模板（随手一写，并无测试完整请看 [Bigint-高精度](云剪贴板 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;

int mod=1e8;

struct Bigint{
    int a[2010];
    int L;
    Bigint(){
        L=0;
        memset(a, 0, sizeof(a));
    }
    int &operator[](int i){
        return a[i];
    }
    
    void input(){
        string s;
        cin>>s;
        L=s.length();
        for(int i=1; i<=L; i++){
            a[i]=s[L-i]-'0';
        }
    }
    
    void print(){
        L=2000;
        while(L>1&&a[L]==0) L--;
        for(int i=L; i>=1; i--){
            printf("%d", a[i]);
        }
    }
};

Bigint operator + (Bigint a, Bigint b){
    Bigint c;
    for(int i=1; i<=max(a.L, b.L); i++){
        c[i]=a[i]+b[i];
        c[i+1]=c[i]/10;
        c[i]%=10;
    }
    return c;
}
Bigint operator - (Bigint a, Bigint b){
    Bigint c;
    for(int i=1; i<=max(a.L, b.L); i++){
        c[i]+=a[i]-b[i];
        if(c[i]<0){
            c[i+1]--;
            c[i]+=10;
        }
    }
    return c;
}
Bigint operator * (Bigint a, Bigint b){
    Bigint c;
    for(int i=1; i<=a.L; i++){
        for(int j=1; j<=b.L; j++){
            c[i+j-1]=a[i]*b[i];
        }
    }
    for(int i=1; i<=2000; i++){
        c[i+1]+=c[i]/10;
        c[i]=c[i]%10;
    }
    return c;
}
Bigint operator / (Bigint a, long long b){
    Bigint c;
    long long x=0;
    for(int i=a.L; i>=1; i--){
        x=x*10+a[i];
        c[i]=x/b;
        x=x%b;
    }
    return c;
}

Bigint a, c;
long long b;

void Input(){
    a.input();
    scanf("%lld", &b);
}

void Work(){
    c=a/(b-1);
    c.print();
}

int main(){
    Input();
    Work();
    return 0;
}