competitive-programming/solved-lightOj/1220.cpp at master · the-redback/competitive-programming · 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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/**
 *                                   ____
 *       ____ ___  ____ ________  __/ __/
 *      / __ `__ \/ __ `/ ___/ / / / /_
 *     / / / / / / /_/ / /  / /_/ / __/
 *    /_/ /_/ /_/\__,_/_/   \__,_/_/
 *
 *    @link : https://the-redback.com
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long llu;

#define ft           first
#define sd           second
#define mp           make_pair
#define pb(x)        push_back(x)
#define all(x)       x.begin(), x.end()
#define allr(x)      x.rbegin(), x.rend()
#define mem(a, b)    memset(a, b, sizeof(a))
#define repv(i, a)   for (i = 0; i < (ll)a.size(); i++)
#define revv(i, a)   for (i = (ll)a.size() - 1; i >= 0; i--)
#define rep(i, a, b) for (i = a; i <= b; i++)
#define rev(i, a, b) for (i = a; i >= b; i--)
#define sf(a)        scanf("%lld", &a)
#define sf2(a, b)    scanf("%lld %lld", &a, &b)
#define sf3(a, b, c) scanf("%lld %lld %lld", &a, &b, &c)
#define inf          1e9
#define eps          1e-9
#define mod          1000000007
#define NN           100010

// clang-format off
#ifdef  redback
#define bug printf("line=%d\n",__LINE__);
#define debug(args...) {cout<<":: "; dbg,args; cerr<<endl;}
struct  debugger{template<typename T>debugger& operator ,(const T& v){cerr<<v<<" ";return *this;}}dbg;
#else
#define bug
#define debug(args...)
#endif  //debugging macros
// clang-format on

#define NN 70000

bool p[NN + 7];        // Hashing
vector<ll> pr, facts;  // storing prime
void sieve(ll n) {
    ll i, j, k, l;
    p[1] = 1;
    pr.push_back(2);
    for (i = 4; i <= n; i += 2) p[i] = 1;
    for (i = 3; i <= n; i += 2) {
        if (p[i] == 0) {
            pr.push_back(i);
            for (j = i * i; j <= n; j += 2 * i) p[j] = 1;
        }
    }
}

ll factor(ll n) {
    facts.clear();
    ll count, k, i;

    for (i = 0; i < pr.size() && pr[i] * pr[i] <= n; i++) {
        k = pr[i];
        count = 0;
        while (n % k == 0) {
            n /= k;
            count++;
        }
        facts.pb(count);
        if (n == 1) break;
    }
    if (n > 1) facts.pb(1);
}

int main() {
// ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef redback
    freopen("C:\\Users\\Maruf\\Desktop\\in.txt", "r", stdin);
#endif

    sieve(NN);

    ll t = 1, tc;
    sf(tc);
    ll l, m, n;
    while (tc--) {
        ll i, j, l;
        sf(n);

        ll minusFlag = 0;

        if (n < 0) {
            n *= -1;
            minusFlag = 1;
        }
        factor(n);

        ll ans = 0;
        for (i = 1; i < 34; i++) {
            ll flag = 1;
            for (j = 0; j < facts.size(); j++) {
                if (facts[j] % i != 0) {
                    flag = 0;
                    break;
                }
            }
            if (minusFlag && i % 2 == 0) continue;

            if (flag) ans = max(ans, i);
        }

        printf("Case %lld: %lld\n", t++, ans);
    }
    return 0;
}