[BOJ] 13412 - 서로소 쌍

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

BOJ - 서로소 쌍

문제 유형: 수학

문제 난이도: Silver II

시간 제한: 1초

메모리 제한: 128MB

 

문제

두 자연수 A, B의 최대공약수를 GCD(A, B)라고 할 때, A와 B가 서로소면 GCD(A, B) = 1이다. 두 자연수 A, B의 최소공배수를 LCM(A, B)라고 할 때, A와 B가 서로소면 LCM(A, B) = A x B이다.

어떤 자연수 N이 서로소인 두 자연수 A, B의 최소공배수라고 할 때, A, B로 가능한 숫자 쌍은 여러 개가 있을 수 있다. 예를 들어 N = 30인 경우 30을 최소공배수로 하는 서로소인 두 자연수로 가능한 숫자 쌍은 (1, 30), (2, 15), (3, 10), (5, 6)의 4가지가 있다.

자연수 N이 주어질 때 N을 최소공배수로 하는 서로소인 자연수 쌍의 개수를 출력하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 다음 줄부터 차례로 T개의 테스트 케이스가 주어진다. 각각의 테스트 케이스의 첫째 줄에 100,000,000이하의 자연수 N이 주어진다.

 

출력

각 테스트 케이스의 답을 순서대로 출력한다. 각 테스트 케이스마다 첫 줄에 N을 최소공배수로 하는 서로소인 자연수 쌍의 개수를 한 줄에 하나씩 출력한다.

 

풀이

입력된 수의 약수인 두 수 쌍에 대해서 최대공약수가 1이면 N을 최소공배수로 하는 수이다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int gcd(int a, int b) {
  if (b == 0)
    return a;
  return gcd(b, a % b);
}

void solve() {
  int num;
  cin >> num;
  int root = sqrt(num);
  int ans = 0;
  for (int i = 1; i <= root; ++i) {
    if (num % i == 0 && gcd(num / i, i) == 1) {
      ans++;
    }
  }

  cout << ans << "\n";
}

int main(int argc, char *argv[]) {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}