[13412] 서로소 쌍

https://www.acmicpc.net/problem/13412

입력 받은 N의 쌍을 먼저 만듭니다.

ex) N = 30 이라면.. (1, 30) ... (30, 1) 까지의 쌍이 있겠죠

하지만 (1, 30) (30, 1)은 같은 쌍이고, (2, 15), (15, 2)는 같은 쌍입니다.

그렇기 때문에 sqrt(N)까지만 쌍을 만들면 해결할 수 있습니다.

여기서 주의할 것은 약수라고 무조건 카운트하면 안됩니다.

두 쌍의 최대공약수가 1인 즉 서로소일 경우에만 쌍을 카운트해야 합니다.

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string.h>
#include <stack>
#include <cstdio>
 
#define mp make_pair
#define MOD 1000000007
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
 
int get_gcd(int a, int b) {
    return b ? get_gcd(b, a % b) : a;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int test;
    cin >> test;
 
    while (test--) {
        int n;
        cin >> n;
 
        int ret = 0;
 
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0 && get_gcd(i, n / i) == 1) {
                ret++;
            }
        }
 
        cout << ret << '\n';
    }
    return 0;
}