আলোচনাঃ
আমাকে দুইটা নম্বর 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;
}
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
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