$A: Acwing4317.$ 不同正整数的个数

#include<bits/stdc++.h>
using namespace std;
const int N = 1000;
int cnt[N];
int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int x; cin >> x;
        if (x > 0) cnt[x] ++;
    }
    int ans = 0;
    for (int i = 0; i < N; i ++)
        if (cnt[i]) ans ++;
    cout << ans;
}

$B: Acwing4318.$ 最短路径

脑子短路，根据题意分析即走法中不能存在重复经过一个点，然后就开始无限$WA$
但是其实对于我们当前所在的点(x,y)，当前点的上下左右的点除了上一步所在的点的三个点只要有一个走过，当前路径即不合法，因为可以通过这三个点可以在之前更快的到达当前点。
如下图中可以通过红色的箭头走到新的点获得更短的路径，所以当前所给路径不符合题意。

#include<bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 100010;
int n;
PII q[N];
bool check(int x, int y)
{
    for (int i = 0; i < n; i ++)    
    if (q[i].first == x && q[i].second == y) return true;
    return false;
}
int main()
{
    string str; cin >> str;
    int dx = 0, dy = 0;
    q[n ++] = {0, 0};
    for (int i = 0; i < str.size(); i ++)
    {
        if (str[i] == 'U') 
        {
            dx --;
            if (check(dx, dy) || check(dx, dy - 1) || check(dx, dy + 1) || check(dx - 1, dy)) return puts("NO"), 0;
            q[n ++] = {dx, dy};
        }
        else if (str[i] == 'D' ) 
        {
            dx ++;
            if (check(dx, dy) || check(dx, dy - 1) || check(dx, dy + 1) || check(dx + 1, dy)) return puts("NO"), 0;
            q[n ++] = {dx, dy};
        }
        else if (str[i] == 'L') 
        {
            dy --;
            if (check(dx, dy) || check(dx - 1, dy) || check(dx + 1, dy) || check(dx, dy - 1)) return puts("NO"), 0;
            q[n ++] = {dx, dy};
        }
        else if (str[i] == 'R') 
        {
            dy ++;
            if (check(dx, dy)  || check(dx - 1, dy) || check(dx + 1, dy) || check(dx, dy + 1)) return puts("NO"), 0;
            q[n ++] = {dx, dy};
        }
    }
    puts("YES");
    return 0;
}

$C: Acwing4319.$ 合适数对

1. 算术基本定理：

   任何一个大于1的自然数N，如果N不为质数，那么N可以唯一分解为有限个质数的乘积。即
   $$N=P_1^{a_1}×P_2^{a_2}×P_3^{a_3}×…×P_n^{a_n}(P_i均为质数,a_i均为正整数)$$

2. 我们可以固定$a_j$来讨论j前面的$a_i$.

   将$a_i$和$a_j$分解质因数:
   $$a_i=P_1^{α_1}×P_2^{α_2}×P_3^{α_3}×…×P_n^{α_n}$$
   $$a_j=P_1^{β_1}×P_2^{β_2}×P_3^{β_3}×…×P_n^{β_n}$$
   $a_i×a_j=P_1^{α_1+β_1}×P_2^{α_2+β_2}×P_3^{α_3+β_3}×…×P_n^{α_n+β_n}=x^k$
   即满足$k$|$(α_i+β_i)$
   因为$2×3×5×7×11×13=510510$就已经超过了$a_i$的最大范围100000，所以每个$a_i$最多只能包含$6$种质因子$P_i$
   
   假设$a_j$被分解为$3$个质因数$r_1$,$r_2$,$r_3$，$a_i$被分解为质因数$t_1$,$t_2$,$t_3$，对$r_1$,$r_2$,$r_3$，$a_i$和$t_1$,$t_2$,$t_3$都$mod$ $k$处理，那么$r_i$和$t_i$都∈(0,k)。
   $mod$ $k$的原因是$k$|$(t_i+r_i)$，所以$t_i$%$k$ + $r_i$%k = $k$
   所以匹配的$r_i$和$t_i$满足$r_i$+$t_i$=$k$
   所以最后我们可以发现我们求的其实是和$r_1$,$r_2$,$r_3$匹配的$t_1$,$t_2$,$t_3$
   求$r_1$,$r_2$,$r_3$和$t_1$,$t_2$,$t_3$的匹配，可以将他们都转化成字符串进行哈希匹配，也可以但是我们可以发现可以将$P_1^{r_1}×P_2^{r_2}×P_3^{r_3}$和$P_1^{t_1}×P_2^{t_2}×P_3^{t_3}$这个运算的结果来当做哈希值，因为根据算术基本定理，每个数可以唯一分解为$P_1^{r_1}×P_2^{r_2}×P_3^{r_3}$的形式，那么$P_1^{r_1}×P_2^{r_2}×P_3^{r_3}$表示的也是唯一一个数值，所以可以直接用它来当哈希值($k-t_i=r_i$)。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int cnt[N];
int power(int a, int b)  // 方幂函数，计算a^b
{
    LL res = 1;  // 答案可能会爆int
    while (b -- )
    {
        res *= a;
        if (res >= N) res = 0;
    }
    return res;
}
int main()
{
    scanf("%d%d", &n, &m);
    LL res = 0;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        LL y = 1, z = 1;
        for (int i = 2; i * i <= x; i ++ )  // 将i分解质因数
            if (x % i == 0)
            {
                int s = 0;
                while (x % i == 0) x /= i, s ++ ;  // 将次数算出来
                s %= m;  // 值只保留次数模k后的值
                if (s)  // 将哈希值算出来
                {
                    y *= power(i, s);
                    z *= power(i, m - s);  // 互补的哈希值
                }
            }
        if (x > 1) y *= x, z *= power(x, m - 1);  // 如果分解完还有
        if (z >= N) z = 0;  // 边界判断

        res += cnt[z];  // 加上和当前ai分解出的r1,r2,r3...匹配的t1,t2,t3的”个数“
        cnt[y] ++ ;  // 哈希值个数++
    }
    printf("%lld\n", res);
    return 0;
}