SPOJ_COMDIV_AC

 avatar
kaziamir
c_cpp
2 months ago
760 B
4
Indexable
Never
#include<bits/stdc++.h>
using namespace std;

#define gcd(a,b) __gcd(a,b)

int NOD(int n){
    int i = 2;
    int ct = 0, nod = 1;
    while(n%i==0){
        ct++;
        n/=i;
    }
    nod*=(ct+1);
    ct = 0;
    for(int i = 3; i*i<=n;i+=2){
        if(n%i==0){
            while(n%i==0){
                ct++;
                n/=i;
            }
            nod*=(ct+1);
            ct = 0;
        }
    }
    if(n>1){
        nod*=2;
    }
    return nod;
    
}

void solution(){
    int tcase;
    scanf("%d", &tcase);
    for(int tc = 1; tc<=tcase; tc++){
        int A,B;
        scanf("%d %d", &A,&B);
        printf("%d\n",NOD(gcd(A,B)));
    }
    
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    solution();
}
Leave a Comment