View difference between Paste ID: 4itQpvfz and TeAgBTMc
SHOW: | | - or go back to the newest paste.
1-
string operator+(string a, string b) {
1+
int sot(string s){
2
	int ans = 0;
3
	Fora(v, s){
4
		ans *= 10;
5
		ans += (v - '0');
6
	}
7
	return ans;
8
}
9
10
string tos(int x){
11
	if (x == 0) return "0";
12
	string s = "";
13
	while (x){
14
		s += (char)(x % 10 + '0');
15-
string operator-(string a, string b) {
15+
		x /= 10;
16
	}
17
	reverse(bend(s));
18
	return s;
19
}
20
21
bool cmp(string a, string b){
22
	if (a.length() != b.length()) return a.length() < b.length();
23
	return strcmp(a.c_str(), b.c_str()) < 0;
24
}
25
26
string add(string a, string b){
27
    string ans = "";
28
    while (a.length() < b.length()) a = "0" + a;
29
    while (b.length() < a.length()) b = "0" + b;
30
    int carry = 0, rem;
31
    for (int i = a.length() - 1; i >= 0; --i) {
32
        rem = (a[i] - '0' + b[i] - '0') + carry;
33
        ans = (char(rem % 10 + '0')) + ans;
34
        carry = rem / 10;
35
    }
36-
string operator* (string a, string b) {
36+
37
    return ans;
38
}
39
40
string sub(string a, string b){
41
    string ans = "";
42
    bool neg = 0;
43
    while (a.length() < b.length()) a = "0" + a;
44
    while (b.length() < a.length()) b = "0" + b;
45-
        for (int j = b.length() - 1; j >= 0; -- j)
45+
46
    int carry = 0, rem;
47-
    for (int i = a.length() + b.length() - 2; i >= 0; --i) {
47+
48
        rem = a[i] - b[i] - carry;
49
        carry = 0;
50
        while (rem < 0) {
51
            ++ carry;
52
            rem += 10;
53
        }
54
        ans = (char(rem % 10 + '0')) + ans;
55
    }
56
    while (ans.length() > 1 && ans[0] == '0') ans.erase(0, 1);
57
    if (neg) ans = "-" + ans;
58
    return ans;
59
}
60
61
string mul(string a, string b){
62
    long long sav[2050];
63
    for (int i = 0; i < 2050; i++)
64
        sav[i] = 0;
65
    string ans = "";
66
    int carry = 0, rem;
67
    a = "0" + a;
68
    b = "0" + b;
69
    for (int i = a.length() - 1; i >= 0; --i)
70
        for (int j = b.length() - 1; j >= 0; --j)
71
            sav[i + j] += ((a[i] - '0') * (b[j] - '0'));
72
    for (int i = a.length() + b.length() - 2; i >= 0; --i){
73
        rem = sav[i] + carry;
74
        carry = rem / 10;
75
        ans = char(rem % 10 + '0') + ans;
76
    }
77
    while (ans.length() > 1 && ans[0] == '0') ans.erase(0, 1);
78
    return ans;
79
}
80
81
string divnum(string a, int b){
82
    string ans;
83
    int idx = 0; 
84
    int tmp = a[idx] - '0'; 
85
    while (tmp < b){
86
       tmp = tmp * 10 + (a[++idx] - '0');
87
   }
88
    while (a.size() > idx){
89
        ans += (tmp / b) + '0';
90
        tmp = (tmp % b) * 10 + a[++idx] - '0'; 
91
    }
92
    if (ans.length() == 0){
93
        return "0";
94
    }
95
    return ans; 
96
}
97
98
int modnum(string a, int b){
99
	string c = divnum(a, b), d = mul(c, tos(b));
100
	return sot(sub(a, d));
101
}
102
103
int strgcd(string a, int b){
104
	return __gcd(modnum(a, b), b);
105
}
106
107
string lcm(string x, int y){
108
	return mul(divnum(x, strgcd(x, y)), tos(y));
109
}