题解：P12312 [蓝桥杯 2024 国 C] 六一儿童节

· · 题解

一些闲话：

关于题解：

这是一个数论并不好的人的暴力题解，只用了最简单的组合和取模，适合不喜欢数学的同学食用。

一些私货：

膜拜神犇 Hootime 和 TA 的 npy chenyuexiC2026。

思路：

要求 x^x+y^y 能被 6401 整除，其实就是 x^x+y^y 对 6401 取模等于 0。\ 那么幂次方中大于 6401 的数就没有用了，可以直接取模掉。\ 那就有一个超级暴力的思想了：对于每一个 i，预处理 i^i 的结果，然后算匹配数。\ 预处理 i^i 可以用快速幂，时间复杂度 O(n \log n)，这里 n 是数据范围，也就是 20240601。\ 乍一看过不了，但是不用担心，这是一道输出答案题。\ 令 mi_i 表示 i^i 对 6041 取模后的结果。\ 预处理之后，建立一个桶，表示余数出现次数，从小到大枚举 i，答案累加 6041-mi_i 的出现次数。\ 为神马呢？\ 每一个 mi_i 能相加刚好凑成 0，或者说 6041 的不就是 6041-mi_i 吗？\ 还有一个注意点，如果 mi_i = 0，累加的应该也是 0 的出现次数。\ 那么，输出答案就可以了。

代码：

#include <bits/stdc++.h>
using namespace std;
#define p 6421
#define int long long
int mi[20240605],tong[6425],ans;
int Fastpow(int a,int b){//快速幂 
    int sum = 1;
    a = a % p;
    while(b > 0){
        if(b & 1) sum = (sum * a) % p;
        a = (a * a) % p;
        b = b >> 1;
    }
    return sum % p;
}
signed main(){
    for(int i = 1;i <= 20240601;++i) mi[i] = Fastpow(i,i);
    for(int i = 1;i <= 20240601;++i){
        ans += tong[(6421-mi[i]) % p];
        ++tong[mi[i]];
    }
    cout << ans;
    return 0;
}

虽然理论会超时，但直接用这段代码其实也能 AC。

答案：

#include <bits/stdc++.h>
using namespace std;
int main(){
    cout << "51349141107";
    return 0;
}