Codeforces Round #596 (Div. 2, based on Technocup 2020 Elimination Round 2)

A - Forgetting Things

题意：给 \(a,b\) 两个数字的开头数字（1~9），求使得等式 \(a=b-1\) 成立的一组 \(a,b\) ，无解输出-1。

题解：很显然只有 \(a=b\) 和 \(a=b-1\) 的时候有解，再加上一个从 \(9\) 越到 \(10\) 的就可以了。被样例的 \(199,200\) 误导了。

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

int main() {
#ifdef KisekiPurin
    freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
    int a, b;
    while(~scanf("%d%d", &a, &b)) {
        if(a == b)
            printf("%d %d\n", a * 10, b * 10 + 1);
        else if(a == b - 1)
            printf("%d %d\n", a, b);
        else if(a == 9 && b == 1)
            printf("9 10\n");
        else
            puts("-1");
    }
}

D - Power Products

题意：给 \(n\)（2e5）个1e5内的数和 \(k\) （100），求有多少个无序数对 \((i,j)\) 满足存在一个 \(x\) 使得 \(a_ia_j=x^k\) 成立。

题解：

很显然就是每种质因数都要是k的倍数，那么每个数要找的那个数是在模意义下面唯一的，一个暴力的做法是分解1e5内的质数，然后求出不超过1e5的这个质数的最高幂，很明显这个最高幂很快就收敛到只剩下1了，那么可以用一个next指针为[0,16]（也就是log(2,1e5)）的字典树来存储。这样到后面一般只有两条路可以走。问题在于由于质数过多深度太大。

一种简单的改进就是特判掉k=2的情况，然后质数的范围就真的缩小到sqrt(1e5)，超过这个范围的质数最多只有一个，且出现以后不可能会和另一个数配出k>=3时的k的倍数。这样是大概只有200多层的一个字典树。

那怎么特判掉k=2的情况呢？应该是存在同一个大质因数的放在一堆，然后堆内匹配。不存在任何大质因数的也是一堆，也是堆内匹配。

补题题解：

不用搞这么复杂……直接把一个数映射到幂模k的另一个数，然后用map存下来就可以了。甚至不需要用map，他的补数也必须限制在1e5里面的。

Codeforces Round #596 (Div. 2, based on Technocup 2020 Elimination Round 2)

原文：https://www.cnblogs.com/KisekiPurin2019/p/11818856.html