F. Rats Rats(二分 or 预处理)[UTPC Contest 09-02-22 Div. 2 (Beginner)]

题面如下：

思路 or 题解

$x^k=a_i$
我们可以去想办法去找到 最小的$x$
为什么去寻找$x_{min}$
看样例：
$521=8^3$
$521=2^9$
一个数如果满足式子 $x^k=a_i$ 至少我们可以找到一个$x$
如果有多个$x$我们其实只需要记录最小的那个就行

思路一： 二分

通过二分来找到$x_{min}$

AC代码如下：

const int N = 100009;
int n;
set<int> s;
bool check(int mid, int x, int k)
{
    int res = 1;
    for (int i = 1; i <= k; i++)
    {
        res *= mid;
        if (res >= x)
        {
            return true;
        }
    }
    return false;
}
bool work(int x, int k)
{
    int l = 1, r = 5e4;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid, x, k))
            r = mid;
        else
            l = mid + 1;
    }

    int res = 1;
    for (int i = 1; i <= k; i++)
    {
        res *= r;
        if (res > x)
            return false;
    }
    if (res == x)
        return true;
    return false;
}
bool check2(int mid, int k, int x)
{
    int res = 1;
    for (int i = 1; i <= k; i++)
    {
        res *= mid;
        if (res >= x)
        {
            return true;
        }
    }
    return false;
}
int cal(int k, int x)
{
    int l = 2, r = 5e5;
    int mid = l + r >> 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check2(mid, k, x))
            r = mid;
        else
            l = mid + 1;
    }
    return r;
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int tt;
        cin >> tt;
        if (tt == 1)
        {
            s.insert(1);
            continue;
        }
        for (int j = 29;; j--)
        {
            if (work(tt, j))
            {
                s.insert(cal(j, tt));
                break;
            }
        }
    }
    cout << s.size() << '\n';
}
signed main()
{
    buff;
    solve();
}
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

思路二：预处理

$x^k\le 1e9$** $x^k$ 数量其实不大
我们可以通过预处理来得到 $a_i的x_{min}$

AC代码如下：

typedef long long ll;
int main()
{
    ll n;
    cin >> n;
    map<ll, ll> mp;
    // 预处理出来所有的情况
    mp[1] = 1;
    for (ll i = 2; i <= 100000; i++)
    {
        if (mp[i] == 0)
        {
            for (ll j = 2; pow(i, j) < 1e9 + 7; j++)
            {
                mp[pow(i, j)] = i;
            }
        }
    }
    set<ll> st;
    for (ll i = 0; i < n; i++)
    {
        ll x;
        cin >> x;
        st.insert(mp[x]);
    }
    cout << st.size();
}
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