【Lightoj】1214 - 能否整除（同余定理）
【Lightoj】1214 - 能否整除（同余定理）
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Submit Status Practice LightOJ 1214
Description
Given two integers, a and b, you should check whethera is divisible by b or not. We know that an integera is divisible by an integer b if and only if there exists an integerc such that a = b * c.
Input
Input starts with an integer T (≤ 525), denoting the number of test cases.
Each case starts with a line containing two integers a (-10200 ≤ a ≤ 10200) andb (|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' ifa is divisible by b. Otherwise print 'not divisible'.
Sample Input
6
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
简单同余定理。
代码如下（这是初学的代码，比较繁琐，不推荐，建议看下面的）：
#include <stdio.h>
#include <string.h>
int main()
{
int u;
char t[222];
int a[222];
long int b;
int l; //数字总位数
long int y; //余数
long int ty; //临时存放余数
int i,j;
scanf ("%d",&u);
getchar();
for (int p=1;p<=u;p++)
{
memset (a,0,sizeof (a));
memset (t,'0',sizeof (t));
scanf ("%s",t);
scanf ("%ld",&b);
printf ("Case %d: ",p);
if (b<0) b=-b;
l=strlen(t);
if (t[0]=='-')
{
l--;
for (i=1,j=l;i<=l;i++,j--)
{
a[i]=t[j]-48;
}
}
else
{
for (i=1,j=l-1;i<=l;i++,j--)
{
a[i]=t[j]-48;
}
}
y=a[1]%b;
for (i=2;i<=l;i++)
{
if (a[i]==0) continue;
ty=a[i]%b;
for (j=2;j<=i;j++)
{
ty=(ty*10)%b;
}
y=(y+ty)%b;
}
if (y==0)
{
printf ("divisible\n");
}
else
{
printf ("not divisible\n");
}
}
return 0;
}改进的代码（注意取余的时候用longlong型）：
#include <cstdio>
#include <cstring>
int main()
{
int u;
int num = 1;
char a[222];
long long b;
int l;
long long ans; // __int64
scanf ("%d",&u);
while (u--)
{
scanf ("%s %lld",a,&b);
l = strlen(a);
// if (b < 0) //不取绝对值也能AC，为什么？
// b = -b;
ans = 0;
for (int i = 0 ; i < l ; i++)
{
if (a[i] == '-')
continue;
ans = (ans * 10 + (a[i] - '0')) % b;
}
if (ans == 0)
printf ("Case %d: divisible\n",num++);
else
printf ("Case %d: not divisible\n",num++);
}
return 0;
}腾讯云开发者
