高精度取余 lightoj 1214 Large Division

缘起

学习高精度取余

分析

题意很裸

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
给定两个整数a和b，你应该检查a是否可以被b整除。 我们知道，当且仅当存在整数c使得a = b * c时，整数a才能
被整数b整除。

【输入】
输入以整数T（≤525）开始，表示测试用例的数量。

每个案例都以包含两个整数a（-10^200≤a≤10^200）和b（| b |> 0，b符合32位有符号整数）的行开头。 数字不
包含前导零。

【输出】
对于每种情况，首先打印案例编号。 如果a可被b整除，则打印'divisible'。 否则打印'not divisible'。

【样例输入】
6
101 101
0 67
-101 101
7678123668327637674887634 101
11010000000000000000 256
-202202202202000202202202 -101

【样例输出】
Case 1: divisible
Case 2: divisible
Case 3: divisible
Case 4: not divisible
Case 5: divisible
Case 6: divisible

【限制】
Time limit 1000 ms
Memory limit 32768 kB

显然, -a能被b整除当前仅当 |a| 能整除 |b|. 所以首先将两个整数变成其绝对值，然后套高精度模板即可.

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
//#include "stdafx.h"

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>

//#define LOCAL
typedef long long LL;

using namespace std;

class bigint // 大整数类
{
public:
	bigint(LL a) // 用long long新建bigint, 注意, long long 的范围是 10^19, 而且科学计数法的最高位还是9, 这就是为什么我们要选择long long 作为大整数的一节的原因. 因为做大整数乘法的时候 10^9*10^9=10^18 也不会超出long long 的范围
	{
		while(a) num.push_back(a%BASE),a/=BASE;
	}

	bigint(){};

	bigint(string s) // 用 字符串 构造大整数, 例如输入的字符串是 "1034004543543", 我们要将其存储为  004543543-->1034, 其中num[0]=004543543, num[1] = 1034
	{
		int n = s.length();
		for (int i = n-1; i>=0; i-=BASE_LEN) // 从高位开始构建
		{
			int j = max(0, i-BASE_LEN+1); // 则参与本次vector节点构建的字符是[j,...,i]
			LL t = 0;
			while(j<=i)
			{
				t = t*10+s[j]-'0'; // 洪特规则, 求出[j,...,i]表示的long long
				j++;
			}
			num.push_back(t);
		}
	}

	string toString() // 将大整数转为字符串输出(方便结果输出)
	{
		stringstream ss;
		bool flag = true; // 是否在输出vector的栈顶元素? (它是大整数的最高位部分)， 之所以要区分是因为栈顶元素是不能补0的
		while(!num.empty())
		{
			if (flag)
			{
				ss << num.back();
				flag = false;
			}
			else
			{
				ss << setw(BASE_LEN) << setfill('0') <<num.back(); // 熟练使用STL 能极大减少编码的复杂度(而且看上去会很优雅)
			}
			num.pop_back();
		}
		return ss.str();
	}

	static bigint add(const bigint &a, const bigint &b) // 大整数加法 a+b(a,b皆非负), 其实就是小学生加法, 复杂度是O(n)的, 比字符串版本的大整数加法要快, 因为这里使用BASE_LEN作为一节, 所以其实一次做9位数加法（而且long long相加很快）, 即常数优化的.效率更高
	{
		bigint ans;
		for (LL i =0, carry=0; ; i++) // 注意, 大整数的结构是 num 的栈顶元素存储高位, 所以要从低位相加, carry 是上一步相加结果的进位(即i-1)
		{
			if (!carry && i>=a.num.size() && i >= b.num.size()) break; // 如果a和b都没有弹药了, 而且上一步并没有发生进位
			if (i<a.num.size()) // 如果a还有弹药
			{
				carry += a.num[i];
			}
			if (i<b.num.size()) // 如果b还有弹药
			{
				carry += b.num[i];
			}
			ans.num.push_back(carry%BASE);
			carry /= BASE; // 作为a.num[i+1]和b.num[i+1]的进位
		}
		return ans;
	}

	static bigint substract(bigint &a, bigint &b) // 高精度减法 a-b, 这里假设 a>=b, 复杂度是 O(N)
	{
		bigint ans;
		unsigned int i; // 注意, 因为size() 返回的是无符号整数, 所以这里最好使用unsigned int
		for (i = 0; i<b.num.size();i++)
		{
			ans.num.push_back(a.num[i]-b.num[i]); // 可能为负值
		}
		for (; i<a.num.size();i++)
		{
			ans.num.push_back(a.num[i]); // 把a剩下的塞进去
		}
		for (i = 0; i<ans.num.size()-1;i++) // 从ans的低位开始扫描负值, 即处理小学生减法之借位
		{
			if (ans.num[i]<0)
			{
				ans.num[i]+=BASE;
				ans.num[i+1]--; // 借位
			}
		}
		while(!ans.num.empty()&&!ans.num.back()) // 删除无意义的前导0
		{
			ans.num.pop_back();
		}
		return ans;
	}

	static int cmp(const bigint &a, const bigint &b) // 大于b返回1, 等于b返回0,小于b返回-1
	{
		if (a.num.size() != b.num.size())
		{
			return a.num.size()< b.num.size()?-1:1;
		}
		for (int i = a.num.size()-1; ~i; i--)
		{
			if (a.num[i]!=b.num[i])
			{
				return a.num[i]<b.num[i]?-1:1;
			}
		}
		return 0;
	}

	static bigint multiply(const bigint &a, const bigint &b) // 非负大整数乘法 a*b 复杂度 O(n^2)
	{
		bigint ans(vector<LL>(a.num.size()+b.num.size(),0)); // m位*n位最多m+n位,最少m+n-1位
		for (unsigned int i = 0; i< a.num.size(); i++)
		{
			for (unsigned int j =0; j<b.num.size();j++)
			{
				ans.num[i+j]+=a.num[i]*b.num[j];  // ans[i+j]的来源不止一个, 例如 ans[3]可以是 a[1]*b[2]也可以是a[2]*b[1]
				ans.num[i+j+1]+=ans.num[i+j]/BASE; // 进位
				ans.num[i+j]%=BASE;
			}
		}
		while(!ans.num.empty() && !ans.num.back()) // 去掉无意义的前导0
		{
			ans.num.pop_back();
		}
		return ans;
	}

	static bigint pow(bigint &a, int &b) // 求a^b, b是整型(已经够大了)
	{
		bigint ans(vector<LL>(1,1)); // ans=1
		while(b) // 快速幂
		{
			if (b&1)
			{
				ans = multiply(ans, a);
			}
			if (b>1)
			{
				a = multiply(a,a);
			}
			b>>=1;
		}
		return ans;
	}

	static bigint div(bigint &a,bigint &b)//非负大数相除a/b
	{
		int tmp;
		if ((tmp=cmp(a,b))!=1)
		{
			if (!tmp) // 如果a==b, 则 a 减去b变成0
			{
				a = bigint(vector<LL>(1,0));
			}
			bigint ans(vector<LL>(1,tmp?0:1));
			return ans;
		}
		int size_a=a.num.size(),size_b=b.num.size();//注意,此时a>b
		bigint ans;//m位除以n位(m>=n)最多m-n+1位,最少m-n位,但是这里不能预设多少位,因为除法与加减乘都不一样,它是从高位开始算的而其它三种是从低位开始算的
		for (int i = size_a-size_b; ~i; i--)
		{
			LL q=0;//每次除得的商
			ok(a,b,i,q);
			ans.num.push_back(q);			
		}
		reverse(ans.num.begin(),ans.num.end());//必须倒序存储
		while(!ans.num.empty() && !ans.num.back()) // 去掉无意义的前导0
		{
			ans.num.pop_back();
		}
		return ans;
	}

	static bigint res(bigint &a, bigint &b) // 高精度计算a%b
	{
		div(a,b);
		return a;
	}
	
	bool iszero()
	{
		bigint zero("0");
		return !num.size() || !cmp(*this, zero);
	}

private:
	const static int BASE_LEN=9,BASE=1000000000;// 10亿为基数
	vector<LL> num; // 构建大整数是这样的, 比如1034004543543, 在我们的bigint类中存储为  004543543-->1034, num[0]=004543543, num[1] = 1034
	bigint(vector<LL> num):num(num){} //使用一个vector构建大整数
	static void ok(bigint &a,bigint b,int i,LL &q)
	{			
		for (int j = 0; j < i; j++)	b.num.insert(b.num.begin(),0);//首先要给b补i个段的0
		int t = cmp(a,b);
		if (!~t) return; // 如果 a<b 则返回(q就是0)
		if (!t) // 如果 a==b
		{
			a = bigint(vector<LL>(1,0));
			q = 1;
			return;
		}
		LL k;
		bigint tmp_b;
		while(~t) // 只要 a >=b
		{
			for (k = 1, tmp_b = b; ~cmp(a, tmp_b); k*=10, tmp_b=multiply(tmp_b, bigint(vector<LL>(1,10)))) // 这里可以考虑 a=999减去b=10, 减去tmp_b=10(初始化为b),tmp_b=100,得到a=889，而再减tmp_b=1000的时候减不动了, 但是889依旧大于b, 所以要再来一轮——减去10,减去100, 得779. 这样比999每次减去10快多了,这可以看做是一个优化
			{
				q+=k;
				a = substract(a, tmp_b);
			}
			t = cmp(a,b);
		} // 最后 a<b
	}
};


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t;
	cin >> t;
	string a,b;
	for (int i = 1; i<=t; i++)
	{
		cin >> a>> b;
		if (a[0]=='-')
		{
			a = a.substr(1);
		}
		if (b[0]=='-')
		{
			b = b.substr(1);
		}
		bigint A(a), B(b);
		bigint::res(A,B);
		printf("Case %d: %s\n", i, A.iszero()?"divisible":"not divisible");
	}
	return 0;
}

ac情况

Status Accepted
Length 5642
Lang C++
Submitted 2019-08-08 16:39:41
Shared
RemoteRunId 1545429