【light oj1078】Integer Divisibility（同余定理）

刺骨的言语ヽ痛彻心扉 2022-07-16 02:41 195阅读 0赞

<table style="margin:0px; padding:0px"> 
 <tbody style="margin:0px; padding:0px"> 
  <tr style="margin:0px; padding:0px"> 
   <td title="normal judge" style="margin:0px; padding:0px"><img src="http://www.myexception.cn/img/2015/08/17/085025436.png" alt="" style="margin:0px; padding:0px; max-width:635px; height:auto"></td> 
   <td style="margin:0px; padding:0px">PDF (English)</td> 
   <td style="margin:0px; padding:0px">Statistics</td> 
   <td style="margin:0px; padding:0px">Forum</td> 
  </tr> 
 </tbody> 
</table>

<table style="margin:0px; padding:0px"> 
 <tbody style="margin:0px; padding:0px"> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:0px">Time Limit:&nbsp;<span style="margin:0px; padding:0px; list-style:none outside none; word-break:normal; word-wrap:break-word; color:rgb(180,95,4)">2 second(s)</span></td> 
   <td style="margin:0px; padding:0px">Memory Limit:&nbsp;<span style="margin:0px; padding:0px; list-style:none outside none; word-break:normal; word-wrap:break-word; color:rgb(180,95,4)">32 MB</span></td> 
  </tr> 
 </tbody> 
</table>

If an integer is not divisible by 2 or 5, some multiple ofthat number in decimal notation is a sequence of only a digit. Now you aregiven the number and the only allowable digit, you should report the number ofdigits of such multiple.

For example you have to find a multiple of 3 which containsonly 1's. Then the result is 3 because is 111 (3-digit) divisible by 3.Similarly if you are finding some multiple of 7 which contains only 3's then,the result is 6, because 333333 is divisible by 7.

# Input #

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

Each case will contain two integers n (0 < n ≤106 and n will not be divisible by 2 or 5)and the allowable digit (1 ≤ digit ≤ 9).

# Output #

For each case, print the case number and the number ofdigits of such multiple. If several solutions are there; report the minimumone.

<table style="margin:0px; padding:0px"> 
 <tbody style="margin:0px; padding:0px"> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:0px"> <h1 style="margin:0px; padding:0px">Sample Input</h1> </td> 
   <td style="margin:0px; padding:0px"> <h1 style="margin:0px; padding:0px">Output for Sample Input</h1> </td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:0px"> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 3</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 3 1</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 7 3</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> 9901 1</p> </td> 
   <td style="margin:0px; padding:0px"> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> Case 1: 3</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> Case 2: 6</p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> Case 3: 12</p> </td> 
  </tr> 
 </tbody> 
</table>

考察同余定理，因为数据过大可能会超long long 型。

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #define LL long long
    #include<algorithm>
    using namespace std;
    int main(){
    	int T,cases=0;
    	scanf("%d",&T);
    	while(T--){
    		LL n,m;
    		scanf("%lld%lld",&n,&m);
    		LL ans=1,cnt=m;
    		while(cnt%n!=0){
    			cnt=(cnt*10+m)%n;
    			ans++;
    		}
    		printf("Case %d: %lld\n",++cases,ans);
    	}
    	return 0;
    }