Sweetlemon 的博客

Sweetlemon 的博客

整数?字符串!——Power Products

posted on 2019-10-29 13:41:00 | under 题解 |

CF #596 Div. 2, D (CF1225D), Power Products

这题非常巧妙,非常值得一做!

两个数的积为 $k$ 次方数,当且仅当每一质因子的次数和都是 $k$ 的倍数。

我们把每一个数的质因数分解的每一个次数都模 $k$ ,那么同一对里的两个数,一个的次数为 $t$ ,另一个的次数就必须是 $-t$ ( $\mod{k}$ 同余意义下)。

首先当然是有一个暴力枚举的思路——枚举数对中靠后的一个数,找它之前有多少可以与它组成“合法数对”(满足上一段所述条件)的数,累加即可。

沿用暴力枚举的思路,如果“找”这一步能用 $O(\log n)$ 的复杂度解决,那么问题就解决了。

如果我们把整数用质因数分解向量形式表示,那么我们也就需要对于一个特定的 $(a_2,a_3,a_5,\cdots)$ (指这个数 $2,3,5,\cdots$ 的次数),找到向量 $(-a_2,-a_3,-a_5)$ 的个数。

向量和字符串非常类似(事实上向量 (vector) 就是序列嘛,字符串也不就是 vector<char> 嘛),因此我们可以考虑用字符串的方法来解题。(事实上这句话是赛后总结各种做法的时候才悟出来的。)

从字符串的角度考虑,这就是一个——插入字符串、查询字符串出现次数的问题。

这个问题有两种解法。

一是利用 Trie。当然这题中 Trie 有很多需要调整的地方,比如直接开会 MLE,需要各种分条件优化等(比如把质因子按 $\sqrt{n}$ 分治)。这个可以参考 $\textcolor{red}{\text{逆流之时}}$ 题解

二是利用 Hash(Hana~!)。如果我们能有一种把这些向量准确地 Hash 的方法,就很容易判断是否存在了。

回忆一下哥德尔不完备定理的证明过程,哥德尔是把逻辑公式的字符表示成数,再把数的向量 hash 成自然数的吧?

这个 hash 方法对于一般字符串来说完全不可行,因为 hash 值随随便便就会变得很大。

但我们的向量本来不就是质因数分解向量嘛!这就说明即使把我们的向量用质因数分解方法表示,它也不会很大!

于是,我们的思路就是,对于每一个数,用一个“指数模 $k$ 后的数”来代表它。

例如,当 $k=3$ 时, $2^4\times 3^3 \times 7^2 \times 11^1$ 可以用 $2^1\times 3^0 \times 7^2 \times 11^1$ 来代表。

我们每次寻找时只需寻找这个数所需的向量的代表数,如上例中数要配对只需寻找 $2^2\times 3^0 \times 7^1 \times 11^2$ 即可。

接下来似乎就没有问题了。存哈希值用一个 multiset 就可以了吧。

然而……lower_bound 和 upper_bound 之间的距离怎么算呢?

用 std::distance 吧?然而,复杂度:线性

干脆用 multiset::count 吧?复杂度:与容器大小的对数和找到元素的个数成线性,也就是说,复杂度是 $O(v+\log n)$ 的,其中 $v$ 指 count 的返回值。

上述两个复杂度的参考资料:

std::distance

线性。

然而,若 InputIt 额外满足遗留随机访问迭代器 (LegacyRandomAccessIterator) 的要求,则复杂度是常数。

std::multiset::count

与容器大小成对数,加上与找到的元素数成线性。

所以最终我们还是选择了 map……

因此这题有一个额外的价值,那就是科普了上述两个函数的复杂度,尤其是 multiset::count 的诡异复杂度。

附代码。

(我第一次交这篇题解的时候看错题号了……交到了 CF 596D 上去……太丢人了)

#include <cstdio>
#include <cctype>
#include <map>
#include <algorithm>
#define MAXIOLG 25
#define FILENAME(x) \
freopen(x".in","r",stdin); \
freopen(x".out","w",stdout);
#define MD(x) (((x)>=MOD)?((x)-=MOD):(0))
#define MAXN 100005
#define N 100000

using namespace std;

typedef long long ll;
typedef long double ld;
typedef ll io_t;

io_t shin[MAXIOLG];
io_t seto(void); //快读
void ayano(io_t x,char spliter='\n'); //快写

int minp[MAXN]={0};
int prime[MAXN],pr=0; //质数筛
int a[MAXN];
int mxdg[MAXN]; //防越界处理,每个数不超过 1e5 的最大次幂
map<ll,int> st;
void make_p(int n); //线性筛
ll kasumi(ll a,ll b);

int main(void){
    make_p(100000);
    int n,k;
    ll ans=0;
    n=seto(),k=seto();
    for (int i=1;i<=n;i++)
        a[i]=seto();
    mxdg[1]=0; //无意义
    //计算每个数不超过 1e5 的最大幂
    for (int i=2;i<=N;i++){
        int tans=1;
        ll tx=i;
        while (tx*i<=N)
            tans++,tx*=i;
        mxdg[i]=tans;
    }
    for (int i=1;i<=n;i++){
        ll x=a[i]; //当前枚举数列的后一个数为 x
        ll y=1; //x 的 hash 为 y
        ll u=1; //x 所匹配的 hash 为 u
        int uok=1; //防溢出处理, 如果 x 所匹配的数超过了范围则此变量为 0
        while (x>1){
            int tdeg=0; //此质因数的次数
            //质因数分解
            int tminp=minp[x];
            while (minp[x]==tminp)
                x/=tminp,tdeg++;
            tdeg%=k; //次数模 k
            y*=kasumi(tminp,tdeg); //计算 x 的 hash

            int udeg; //x 所匹配的数的此项次数
            udeg=(k-tdeg)%k;

            if (udeg>mxdg[tminp]) //如果超过了 1e5 的范围
                uok=0;
            else
                u*=kasumi(tminp,udeg);
        }
        (uok && st.count(u))?(ans+=st[u]):(0); //如果存在 x 所匹配的数, 则累加
        //将 x 的 hash 加入 map
        if (st.count(y))
            st[y]++;
        else
            st[y]=1;

    }
    ayano(ans); //输出答案
    return 0;
}

void make_p(int n){
    //线性筛
    int nd2=n>>1;
    minp[1]=0;//No meaning
    for (int i=2;i<=n;i++){
        if (!minp[i]){
            minp[i]=i;
            prime[pr++]=i;
        }
        int t;
        for (int j=0;j<pr && (t=prime[j]*i)<=n;j++){
            minp[t]=prime[j];
            if (prime[j]==minp[i])
                break;
        }
    }
}

ll kasumi(ll a,ll b){
    //快速幂
    ll ans=1;
    while (b){
        (b&1)?(ans*=a):(0);
        a*=a,b>>=1;
    }
    return ans;
}

io_t seto(void){
    //快读
    io_t x=0;
    char ch=getchar();
    int symbol=0;
    while (!isdigit(ch))
        (ch=='-')?(symbol=1):(0),ch=getchar();
    while (isdigit(ch))
        x=(x*10)+(ch-'0'),ch=getchar();
    return (symbol)?(-x):(x);
}
void ayano(io_t x,char spliter){
    //快写
    if (!x){
        putchar('0'),putchar(spliter);
        return;
    }
    if (x<0)
        putchar('-'),x=-x;
    int len=0;
    while (x){
        io_t d=x/10;
        shin[len++]=x-d*10;
        x=d;
    }
    while (len--)
        putchar(shin[len]+'0');
    putchar(spliter);
}