Problem D 풀이 (C++)

문제 링크 : https://codeforces.com/contest/1538/problem/D

1보다 큰 숫자는 무조건 임의의 숫자로 나누어 1로 만들 수 있다.

소인수분해를 통해 숫자 a를 소수의 곱으로 나타내면

소수1 x 소수1 x 소수1 x ... x 소수2 x 소수2 x ...  이런 형태로 나타낼 수 있다.

a를 나눌 수 있는 수는 이 소수들의 조합의 곱으로 만들 수 있는 수이다.

예를 들면,

소수1 x 소수1 x 소수2 x 소수3 으로 구성되어 있는 수라면

소수1 x 소수2의 숫자로 나누었을 때 나머지가 0이고 몫이 소수1 x 소수3이 된다.

이런 방식이라면 임의의 숫자를 1보다 큰 수로 나눌 수 있는 최대 횟수는

소인수분해를 통해 구한 소수들의 개수이다.

이것이 기본 알고리즘이고 예외사항을 보자면

1. a = b = 1 인 경우, 2개 숫자 모두 더 이상 나눌 수 없으므로 "NO" 출력.

2. k = 1인 경우, a나 b 중 한 번만 나누어 둘이 같은 수를 만들어야 하므로

   a % b == 0 || b % a == 0 이고 a != b 라면 "YES" 출력. 아니면 "NO" 출력.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <vector>
 
using namespace std;
 
// prime numbers
int primes[40000];
 
int main() {
 
    int t;
    cin >> t;
 
    for (int i = 0; i < 40000; i++)
        primes[i] = 1;
 
    // find prime numbers.
    for (int i = 2; i * i < 40000; i++) {
        if (primes[i] == 1) {
            for (int j = i * i; j < 40000; j += i)
                primes[j] = 0;
        }
    }
 
    while (t--) {
 
        int a, b, k;
        cin >> a >> b >> k;
 
        if (a == 1 && b == 1) {
            cout << "NO" << endl;
            continue;
        }
 
        if (k == 1) {
            if ((a % b == 0 || b % a == 0) && a != b)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
            continue;
        }
 
        int divNum = 0;
 
        for (int i = 2; i < 40000; i++) {
            if (primes[i] == 1) {
 
                while (a % i == 0) {
                    a /= i;
                    divNum++;
                }
 
                while (b % i == 0) {
                    b /= i;
                    divNum++;
                }
 
                if (a == 1 && b == 1)
                    break;
            }
        }
 
        if (a > 1)
            divNum++;
        if (b > 1)
            divNum++;
 
        if (divNum >= k)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
 
    return 0;
}
cs

댓글

댓글 쓰기