Number of common divisors of 2 numbers

Problem link: COMDIV - Number of common divisors

For this we need to know
                         CommonDivisor(a,b) = NumberOf Divisor(gcd(a,b)) proof

Find the number of divisors: Time Complexity O(sqrt(n))

tutorial for finding the number of divisors : progkriya

Solution:

	#include<bits/stdc++.h>
	using namespace std;
	int countDivisor(int n) { //time complexity O(sqrt(n))
	int divisor = 0;
	for (int i = 1; i * i <= n; i++) {
	if (i * i == n) {
	divisor += 1;
	}
	else if (n % i == 0) {
	divisor += 2;
	}
	}
	return divisor;
	}
	int main(){
	int t;
	int a,b;
	scanf("%d",&t);
	while(t--){
	scanf("%d %d",&a,&b);
	int n = __gcd(a,b);
	printf("%d\n",countDivisor(n));
	}
	}

view raw COMDIV - Number of common divisors.cpp hosted with ❤ by GitHub