Spoj – COMDIV – Number of common divisors

Problem link

আলোচনাঃ
আমাকে দুইটা নম্বর A আর B দেয়া থাকবে। আমাকে বলতে হবে A আর B এর মধ্যে কয়টা common divisor আছে।

উত্তরঃ
ধরা যাক,A = 12 and B = 24,এদের divisor গুলো হবে,
12 = 1, 2, 3, 4, 6, 12 = 6 divisors
24 = 1, 2, 3, 4, 6, 8, 12, 24

দেখা যাচ্ছে , 12 and 24 দুইটারই সবথেকে বড় common divisor হচ্ছে 12 . তাহলে 12 আর 24 এর মধ্যে যত common divisor থাকবে তা সবথেকে বড় common divisor = 12 এর মধ্যেই থাকবে। কারণ এর পরে আর কোনো common divisor ই থাকবে না।আর সবথেকে বড় common divisor হচ্ছে gcd(12,24). তাহলে আমাদের A আর B এর gcd = 12 এর divisor কতগুলো তা বের করলেই হচ্ছে। আর 12 এর divisor আছে 6 টা।

আর আমরা জানি, কোনো সংখ্যার square root পর্যন্ত check করলেই সেই number এর total divisor count বের করা যায়। এটা কেন কাজ করে?

12 = 1 x 12
= 2 x 6

= 3 x 4

—————————

= 4 x 3
= 6 x 2
= 12 x 1

এখানে দেখতে পাচ্ছি, sqrt(12) = 3, এর পরে যেসব divisor আছে তা আমরা আগেই বের করে ফেলেছি এবং sqrt(12) = 3(divisor) এর পরে সেগুলো আবার repeat হচ্ছে। তাই একই জিনিস বার বার calculate করার কোনো প্রয়োজন আছে কি?

C++ Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7;
     
      // you should use scanf/printf for I/O, otherwise you will get TLE

int divCount(int &gcd){ //O(sqrt(gcd(A,B)))
    int cnt=0;
    for(int i=1;i*i<=gcd;i++){
        if(gcd%i==0){
            if(i!=(gcd/i)) cnt+=2; 
            else cnt++;   // for square number sqrt(16) = 4*4
                          // So, we should count 4 once
        }
    }
    return cnt;

}

int main(){
   
    int t,a,b;
    
    scanf("%d",&t);
    while(t--){
        
        scanf("%d%d",&a,&b);
        int gcd=__gcd(a,b); // O(logN) , where N = max(a,b)
       
        printf("%d\n",divCount(gcd));
    }
    return 0;
}

----------------------------------- OR -------------------------------------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7;
vector<int> prime;
bool vis[100000000];

int divCount(int &gcd){
    int ans=1,cnt;
    for(int i=0;i<prime.size() && prime[i]*prime[i]<=gcd;i++){
        if(gcd%prime[i]==0){
            cnt=1;
            while(gcd%prime[i]==0){
                cnt++;
                gcd/=prime[i];
                
            }
            ans=ans*cnt;
        }
    }
    if(gcd>1){
        ans=ans*2;
   }
    return ans;
}

void sieve(){
    for(int i=3;i*i<=N;i+=2){
        if(vis[i]==0){
            for(int j=i*i;j<=N;j+=2*i){
                vis[j]=1;
            }
        }
    }
    prime.push_back(2);
    for(int i=3;i<=N;i+=2){
        if(vis[i]==0) prime.push_back(i);
    }

}

int main(){
    sieve();

    int t,a,b;
    scanf("%d",&t);
    while(t--){
       
        scanf("%d%d",&a,&b);
        int gcd=__gcd(a,b);
        
        printf("%d\n",divCount(gcd));
    }
    return 0;
}

This Post Has 2 Comments

  1. Royal CBD

    Hey! Someone in my Facebook group shared this site with us so
    I came to look it over. I’m definitely enjoying the information. I’m book-marking and will be tweeting this to my followers!
    Superb blog and superb design.

    Also visit my web-site – Royal CBD

    1. tusher

      It’s nice to hear that you like the design and you are bookmarking my site and suggest to follow my website.It’s a new site and i try to upload more post. Hope it will help you a lot:)
      Thank you very much royalcbd.com

Leave a Reply