Timus/2102.cpp at main · Free-Denis/Timus · GitHub

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
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
using namespace std;

double BinaryPower(double b, unsigned long long e) {
    double v = 1.0;
    while (e != 0) {
        if ((e & 1) != 0) {
            v *= b;
        }
        b *= b;
        e >>= 1;
    }
    return v;
}

int main()
{
    long long n;
    cin >> n;


    long long rt = sqrt(n), count = 0;
    bool ans = true;

    for (long long i = 2; i <= rt && i <= n; i = i + 2)
    {
        if (i == 4)
            i--;

        while (n % i == 0)
        {
            count++;
            n = n / i;
        }

        if (count > 20)
        {
            ans = false;
            break;
        }
        else
            if (count == 20)
            {
                if (n != 1) ans = false;
                break;
            }
            else
                if (count == 19)
                {
                    if ((i + 1) * (i + 1) > n)
                    {
                        if (i + 1 <= n) break;
                        else
                        {
                            ans = false;
                            break;
                        }
                    }
                }

        if (ans == false)
            break;
        if (BinaryPower(i + 1, 20 - count) > n)
        {
            ans = false;
            break;
        }
    }

    if (ans && n != 1)
    {
        count++;
    }

    if (count != 20)
    {
        ans = false;
    }

    if (ans)
        cout << "Yes";
    else
        cout << "No";

    return 0;
}