light oj 1214 Large Division

题目：

Given two integers, a and b, you should check whether a is divisible by b or not. We know that an integer a is divisible by an integer b if and only if there exists an integer c 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 (-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

题意描述：

大整数取模。

解题思路：

1、模拟大整数除法。2、从低位到高位每次乘以位权对除数取模。

AC代码：

比赛时候写的比较仓促，使用了第一种较笨的方法。

  1 #include<stdio.h>
  2 #include<string.h>
  3 int f(char s1[],char s2[]);
  4 int sub(int *p1,int *p2,int l1,int l2);
  5 char s1[300],s2[300];
  6 int an1[300],an2[300];
  7 int main()
  8 {
  9     int T,flag,t=1,l1,l2;
 10     scanf("%d",&T);
 11     while(T--)
 12     {
 13         memset(s1,0,sizeof(s1));//注意重置字符数组
 14         memset(s2,0,sizeof(s2));//注意重置字符数组
 15         scanf("%s%s",s1,s2);
 16         flag=0;
 17         if(s1[0]=='-' || s2[0]=='-')
 18         {
 19             if(s1[0]=='-'&&s2[0]=='-')
 20             flag=f(s1+1,s2+1);
 21             else
 22             {
 23                 if(s1[0]=='-')
 24                 flag=f(s1+1,s2);
 25                 else
 26                 flag=f(s1,s2+1);
 27             }
 28         }
 29         else
 30         flag=f(s1,s2);
 31         
 32         //printf("%d
",flag);
 33         if(flag)//1能整除，0不能整除 
 34         printf("Case %d: divisible
",t++);
 35         else
 36         printf("Case %d: not divisible
",t++);    
 37     }
 38 }
 39 
 40 int f(char s1[],char s2[])
 41 {
 42     int l1,l2,b,i,j;
 43     l1=strlen(s1);
 44     l2=strlen(s2);
 45     if(l1==1&&s1[0]=='0')
 46     return 1;
 47     
 48     if(l1<l2)
 49     return 0;
 50     memset(an1,0,sizeof(an1));
 51     memset(an2,0,sizeof(an2));
 52     j=0;
 53     for(i=l1-1;i>=0;i--)
 54         an1[j++]=s1[i]-'0';
 55     j=0;
 56     for(i=l2-1;i>=0;i--)
 57         an2[j++]=s2[i]-'0';
 58         
 59     l1=sub(an1,an2,l1,l2);
 60     if(l1 < 0)
 61     return 0;
 62     else if(l1==0)
 63     return 1;
 64     
 65     int nt=l1-l2;
 66     if(nt < 0)
 67     return 0;
 68     else if(nt > 0)
 69     {
 70         for(i=l1-1;i>=0;i--)
 71         {
 72             if(i >= nt)
 73             an2[i]=an2[i-nt];
 74             else
 75             an2[i]=0;
 76         }
 77     }
 78     l2=l1;
 79     for(j=0;j<=nt;j++)
 80     {
 81         int tem;
 82         while( (tem=sub(an1,an2+j,l1,l2-j)) >= 0)
 83         {
 84             l1=tem;
 85         }
 86     }
 87     
 88     if(l1==0)
 89     return 1;
 90     else
 91     return 0;
 92 }
 93 int sub(int *p1,int *p2,int l1,int l2)
 94 {
 95     
 96     int i;
 97     if(l1 < l2)
 98     return -1;
 99 
100     bool bl=false;
101     if(l1 == l2)
102     {
103         for(i=l1-1;i>=0;i--)
104         {
105             if(p1[i] > p2[i])
106             bl=true;
107             else
108             if(p1[i] < p2[i])
109             {
110                 if(!bl)
111                 return -1;
112             } 
113         }
114     }
115     for(i=0;i<l1;i++)
116     {
117         p1[i] -= p2[i];
118         if(p1[i] < 0)
119         {
120             p1[i] += 10;
121             p1[i + 1]--;
122         }
123     }
124     for(i=l1-1;i>=0;i--)
125     {
126         if(p1[i])
127         return i+1;
128     }
129     return 0;
130 }