Large Division LightOJ - 1214 (大数取模)

Love The Way You Lie 2022-05-19 13:41 170阅读 0赞

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’.

**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<bits/stdc++.h>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<string>
    #include<algorithm>
    #include<iostream>
    #include<map>
    #include<set>
    #include<vector>
    using namespace std;
    typedef long long ll;
    
    ll pow_mod(ll a,ll b,ll c)
    {
        ll ans=1;
        a%=c;
        while(b)
        {
            if(b&1) ans=ans*a%c;
            a=a*a%c;
            b>>=1;
        }
        return ans;
     } 
    
    ll exgcd(ll a,ll b,ll &x,ll &y)
    {
        if(b==0)
        {
            x=1;
            y=0;
            return a;
        }
        ll r=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return r;
    }
    
    ll inv(ll a,ll mod)
    {
        ll x,y;
        ll d=exgcd(a,mod,x,y);
        if(d==1)    return (x%mod+mod)%mod;
        return -1;
    }
    
    int main()
    {
        int t,n,m;
        scanf("%d",&t);
        char s[205];
        ll b;
        int c=t;
        while(t--)
        {
            memset(s,0,sizeof(s));
            scanf("%s %lld",s,&b);
            int i=0;
            b=b>0?b:-b;
            if(s[0]>='0'&&s[0]<='9')    i=0;
            else    i=1;
            ll ans=0;
            for(;i<strlen(s);i++)
                ans=(ans*10+s[i]-'0')%b;
            if(ans%b==0)    printf("Case %d: divisible\n",c-t);
            else            printf("Case %d: not divisible\n",c-t);
    
        }
        return 0;
    }