LightOJ 1214 - Large Division【同余定理】

我会带着你远行 2022-08-18 02:35 197阅读 0赞

1214 - Large Division

<table> 
 <tbody> 
  <tr> 
   <td title="normal judge" style="color:rgb(79,107,114)"><a href="http://www.lightoj.com/volume_submit.php?problem=1214" style="color:rgb(79,107,114)" rel="nofollow"><img src="http://www.lightoj.com/images/submit1.png" alt=""></a></td> 
   <td style="color:rgb(79,107,114)"><a href="http://www.lightoj.com/volume_showproblem.php?problem=1214&amp;language=english&amp;type=pdf" style="color:rgb(79,107,114)" rel="nofollow">PDF (English)</a></td> 
   <td style="color:rgb(79,107,114)"><a href="http://www.lightoj.com/volume_problemstat.php?problem=1214" style="color:rgb(79,107,114)" rel="nofollow">Statistics</a></td> 
   <td style="color:rgb(79,107,114)"><a href="http://www.lightoj.com/forum_showproblem.php?problem=1214" style="color:rgb(79,107,114)" rel="nofollow">Forum</a></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td style="color:rgb(121,114,104); background:rgb(245,250,250)">Time Limit:&nbsp;<span style="color:rgb(180,95,4)">1 second(s)</span></td> 
   <td style="color:rgb(121,114,104); background:rgb(245,250,250)">Memory Limit:&nbsp;<span style="color:rgb(180,95,4)">32 MB</span></td> 
  </tr> 
 </tbody> 
</table>

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 (-10200 ≤ a ≤ 10200)** 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'**.

<table> 
 <tbody> 
  <tr> 
   <td> <h1 style="color:green">Sample Input</h1> </td> 
   <td> <h1 style="color:green">Output for Sample Input</h1> </td> 
  </tr> 
  <tr> 
   <td> <p>6</p> <p>101 101</p> <p>0 67</p> <p>-101 101</p> <p>7678123668327637674887634 101</p> <p>11010000000000000000 256</p> <p>-202202202202000202202202 -101</p> </td> 
   <td> <p>Case 1: divisible</p> <p>Case 2: divisible</p> <p>Case 3: divisible</p> <p>Case 4: not divisible</p> <p>Case 5: divisible</p> <p>Case 6: divisible</p> </td> 
  </tr> 
 </tbody> 
</table>

--------------------

PROBLEM SETTER: JANE ALAM JAN

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    char map[10000];
    int main()
    {
    	int t;
    	int uu=0;
    	scanf("%d",&t);
    	while(t--)
    	{
    		uu++;
    		int nn;
    		scanf("%s",map);
    		int len=strlen(map);
    		scanf("%d",&nn);
    		long long ans=0;
    		if(map[0]=='-')
    		{
    			for(int i=1;i<len;i++)
    			{
    				ans=ans*10+(map[i]-'0');
    				ans=ans%nn;
    			}
    		}
    		else
    		{
    			for(int i=0;i<len;i++)
    			{
    				ans=ans*10+(map[i]-'0');
    				ans=ans%nn;
    			}
    		}
    		printf("Case %d: ",uu);
    		if(ans%nn==0)
    		{
    			printf("divisible\n");
    		}
    		else
    		printf("not divisible\n");
    	}
    	return 0;
    }