Large Division(大整数取模)

87 阅读 0 评论 58 点赞

我是靠谱客的博主小巧鸡翅，这篇文章主要介绍Large Division(大整数取模)，现在分享给大家，希望可以做个参考。

Large Division LightOJ - 1214

Given two integers, a andb, you should check whether a is divisible by b or not. We know that an integer a is divisible by an integerb if and only if there exists an integer c such thata = b * c.

Input

Input starts with an integer T (≤ 525), denoting the number of test cases.

Each case starts with a line containing two integersa (-10²⁰⁰ ≤ a ≤ 10²⁰⁰) and b (|b| > 0, b fits into a 32 bit signed integer). Numbers will not contain leading zeroes.

Output

For each case, print the case number first. Then print'divisible' if a is divisible by b. Otherwise print'not divisible'.

Sample Input

101 101

0 67

-101 101

7678123668327637674887634 101

11010000000000000000 256

-202202202202000202202202 -101

Sample Output

Case 1: divisible

Case 2: divisible

Case 3: divisible

Case 4: not divisible

Case 5: divisible

Case 6: divisible

用到公式：例如：1234%b=(((1%b*10+2)%b*10+3)%b*10+4)%b,该公式是由同余定理推导而来。

1234可化成（（1*10+2）*10+3）*10+4

1234%b=（（（1*10+2）*10+3）*10+4）%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
#include<stdio.h>
#include<string.h>

char a[205];

int main()
{
	int t,l,bi,e;
	long long b,sum;
	char q;
	while(~scanf("%d",&t))
	{	
		e=1;
		while(t--)
		{
			scanf("%s",a);
			if(a[0]=='-') bi=1;  //该题只需判断能不能整除，不用考虑符号
			else bi=0;			 //将负号都变为正号
			l=strlen(a);		 //我的办法是改变起始位置，若有负号，则从a[1]开始
			scanf("%lld",&b);
			if(b<0) b=-b;
		
			sum=0;
			for(int i=bi;i<l;i++) 
			{
		
				sum=(sum*10+(a[i]-'0'))%b;//应用公式
		
			}
			printf("Case %d: ",e++);
			if(sum==0) printf("divisiblen");
			else printf("not divisiblen");
		}
	}
	return 0;
 }