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