Number of common divisors
Given below code is for comdiv spoj or number of common divisor spoj.
Hint :- > sieve and the number of common divisor of two number will be the number of divisor of its GCD.
#include <bits/stdc++.h> using namespace std; int prime[100000]; bool check[1000009]; void pre() { for(int i = 3 ; i<=1000 ; i+=2) { if(!check[i]) { for(int j = i*i ; j<=1000000 ; j+=i) check[j] = true; } } int j = 1; prime[0] = 2; for(int i = 3; i <=1000000 ; i+=2) if(!check[i]) prime[j++] = i; } int main() { pre(); int t; scanf("%d",&t); while(t--) { int a,b; scanf("%d%d",&a,&b); long long gcd = __gcd(a,b); long long res = 1; if(gcd == 1) { printf("1\n"); continue; } for(int i = 0 ;i <= 78500 && prime[i] < gcd && gcd; i++) { int count = 0; while(gcd%prime[i] == 0) { count++; gcd/=prime[i]; } res *= (count + 1); } if(gcd > 1) res *= 2; printf("%lld\n",res); } return 0; }
No comments:
Post a Comment
Your comment is valuable to us