CodeForces - 1247D Power Products【数论】

谁践踏了优雅 2023-06-15 11:03 7阅读 0赞

题目链接：[https://codeforces.com/problemset/problem/1247/D][https_codeforces.com_problemset_problem_1247_D]

题意：给你一个序列a，问有多少对i，j满足存在x使得 ai \* aj = x ^ k , k是给定的。

思路：两个数满足条件就是要相同因数的个数要是k的倍数，  
把每个数质因数分解，然后算出来补数，例如还需要2个2，就是4  
然后我们就在map里找这个补数，然后再将当前数的贡献存入map

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define ls rt << 1
    #define rs rt << 1|1
    #define mid ((l + r) >> 1)
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    const int maxn = 1e5 + 10;
    int aa[maxn], prime[maxn], a[maxn];
    map<ll, int> mp;
    int tot = 0;
    void init()
    {
        for(int i = 2; i < maxn; ++i)
        {
            if(!aa[i])
            {
                prime[++tot] = i;
                for(int j = i * 2; j < maxn; j += i)
                    aa[j] = 1;
            }
        }
    }
    
    int main()
    {
        init();
        int n, k;
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        ll ans = 0;
        for(int i = 1; i <= n; ++i)
        {
            queue<pair<int, int> > q;
            while(!q.empty()) q.pop();
            int x = a[i];
            if(x == 1) q.push({1, 1});
            for(int j = 1; j <= tot && prime[j] <= x; ++j) //质因数分解
            {
                int cnt = 0;
                while(x % prime[j] == 0)
                {
                    x /= prime[j];
                    ++cnt;
                }
                cnt = cnt % k;
                if(cnt) q.push({prime[j], cnt});
            }
            bool flag = true;
            ll res = 1, res1 = 1;
            while(!q.empty())
            {
                pair<int, int> tmp = q.front(); q.pop();
                for(int j = 1; j <= k - tmp.second; ++j) //算补数
                    res = res * tmp.first;
                for(int j = 1; j <= tmp.second; ++j) //算贡献
                    res1 = res1 * tmp.first;
            }
            if(res > 100000) flag = false; //可以优化一下，超出值的范围一定不行
            if(flag) ans += mp[res];
            mp[res1]++;
        }
        printf("%lld\n", ans);
        return 0;
    }

[https_codeforces.com_problemset_problem_1247_D]: https://codeforces.com/problemset/problem/1247/D