SPOJ - Number of common divisor

এই প্রোবলেম এ একটি টেস্ট কেস দেওয়া থাকবে T যার রেঞ্জ 10, 000000।প্রতিটি  T এর দু’টি নাম্বার দেওয়া থাকবে A এবং B  । এখন আমাদের বলতে হবে দু’টি নাম্বার মধ্যে কমন ডিভিসর কত?


সলিশন:--
উদাহরনসরুপ  12 এবং 24 দেওয়া আছে । প্রথমে 12 ডিভিসর বের করব এবং পরে 24 এর ডিভিসর গুলো বের করব এবং তাদের মধ্যে যেগুলো কমন সেগুলো প্রিন্ট করব। কিন্তু নরমালি এই কাজ টা করতে গেলে টাইম লিমিট ইরর খাবো। তবে এক্ষেত্রে আমরা একটা বিশেষ ট্রিকস ব্যবহার করতে পারি। মনে করি আমাদের কাছে দু’টি সংখ্যা আছে 30 এবং 45 । এই দু’সংখ্যার মধ্যে জিসিডি হচ্ছে 15 । এই 15 ডিভিসর গুলো হচ্ছে 1, 3, 5, 15 । তার মানে 15 সংখ্যা 30 কে ভাগ করতে পারে এবং 45 কেও ভাগ করতে পারে । তাহলে 15 যে ডিভাসরগুলো আছে সেগুলো অবশ্যই 30 কে ভাগ যাবে এবং 45 কেও ভাগ যাবে। এদ্বারা বুজা যায় যে 15 ডিভাসরগুলো হচ্ছে এই দু’সংখ্যার কমন ডিভিসর।সাধারনত এটাই আমাদের উত্তর।

 কোডিং  স্টেপ:

 প্রথমে, ‍A এবং B এর GCD বের করতে হবে । তোমরা চাইলে GCD ফাংশন না লিখে GCD function call  পারো । STL এ ফাংশন করে দেওয়া আছে। তবে এভাবে ডিক্লেয়ার করা যায় __gcd(a, b);

দ্বিতীয়ত, gcd call করার পরে যে value আসবে ঐ value কে ডিভিসর ফাংশনে কল করব  এবং ডিভিসর সাম করে রেজাল্ট রির্টান করে দিবো।

সম্পূর্ন কোড:

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

int getdiv(int n)
{
    int ans=0;
    for(int i=1; i*i<=n; i++)
    {
        if(i*i==n)ans+=1;
        else if(n%i==0)ans+=2;
    }
    return ans;
}
int main ()
{
    int t, a, b;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &a, &b);
        int x = __gcd(a, b);
        printf("%d\n", getdiv(x));
    }
}

বিঃ দ্রঃ যদি কোন কিছুতে বুজতে সমস্যা হয় তাহলে অবশ্যই কমেন্ট এ জানাবেন।