Blog

Problem link

আলোচনাঃ

a/b করলে ভাগশেষ 0 হয় কিনা দেখা লাগবে। কিন্তু a এর লিমিট (-10200 ≤ a ≤ 10200)। যেহেতু a অনেক বড় তাই একে string হিসেবে রাখা লাগবে।

উত্তরঃ

1^st row = index

2^nd row = a (string)

b= – 101
আমরা দেখতে পারি, a এর প্রথম 3 digit b দিয়ে নিঃশেষে ভাগ যায় কিনা। 3 digit করে করে check করব কারণ b এর size=3 . b এর size 4 হলে 4 digit করে করে পুরো string ‘b’ দিয়ে divisible কিনা তা check করলেই হয়। আর a যেহেতু positive/negative হতে পারে তাই দেখা লাগবে 0 no index এ minus sign আছে কিনা ।থাকলে index = 1 থেকে check করা শুরু করব।

আর a যেহেতু string তাই এর প্রতিটি character কে আগে digit এ convert করা লাগবে এবং b=3 হলে a এর 3 digit কে কোথাও একটা save করে দেখা লাগবে সেটা b দিয়ে ভাগ যায় কিনা। এভাবে পুরো a check করে যদি 0 পাওয়া যায় তাহলে বুঝব যে, a এর প্রতি 3 digit এর part ‘b’ দিয়ে ভাগ গেছে। অন্যথায় বিপরীত ঘটনা ঘটবে। a এর প্রতি 3 digit এর part ‘b’ দিয়ে ভাগ যায় কিনা তা আমরা নিচের উপায়ে check করতে পারি –

part=(a[j]-‘0’)+(part*10);
part=part%b; /// এখানে (a[j]-‘0’) হচ্ছে character কে digit এ convert করার উপায়

/*

part = 2 + 0*10 = 2

part = 2 % -101 = 2

——————————————

part = 0 + 2*10 = 20

part = 20 % -101 = 20

——————————————

part = 2 + 20*10 = 202
part = 202 % -101 = 0

*/

প্রথম part এর শেষে 0 পেয়েছি। এভাবে পুরো a check করতে হবে।

C++ Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){

    int t,c=1;
    cin>>t;
    while(t--){
        string a;
        ll b;
        cin>>a>>b;
        ll len=a.size(),i;
        if(a[0]=='-') i=1;
        else i=0;

        ll part=0;
        for(ll j=i;j<len;j++){
            part=(a[j]-'0')+(part*10);
            part=part%b;
        }
        if(part==0) printf("Case %d: divisible\n",c);
        else printf("Case %d: not divisible\n",c);
        c++;
    }
}