专栏文章

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

LLPR_318
P12312题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mipazr6q
此快照首次捕获于
2025/12/03 09:03
3 个月前
此快照最后确认于
2025/12/03 09:03
3 个月前
查看原文

一些闲话：

关于题解：

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

一些私货：

膜拜神犇 Hootime 和 TA 的 npy chenyuexiC2026。

思路：

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

代码：

CPP
#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。

答案：

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

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...