自动搬运

查看原文

来自洛谷，原作者为

	SCma Stay foolish!!!!!!!!!!!!!

搬运于2025-08-24 23:14:30，当前版本为作者最后更新于2025-04-23 17:41:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

这是一道数学题，但其实它的难度并不大。

数学转换：

问题本身其实等价于找到 $(x^x + y^y) \equiv 0 \pmod{6421}$，即：

因此，统计每个数 $n \in [1,20240601]$ 的 $n^n \bmod 6421$ 值，并计算互补余数的组合数。

周期性：

$n^n \bmod 6421$ 的值由 $n \bmod 6421$ 和 $n \bmod 6420$ 共同决定。而最大周期为 $\text{lcm}(6421,6420) = 38943840$，远大于 $20240601$，故直接遍历计算就行了，不需要重复计算。

复杂度分析

因为使用了快速幂，所以时间复杂度是 $O(N\log N)$。

代码

#include<bits/stdc++.h>
#define endl '\n'
#define MIN(a,b,c) min(min(a,b),c)
#define MAX(a,b,c) max(max(a,b),c)
#define ri register int
#define int long long
#define fixedset(a) fixed << setprecision(a)
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
#define ls(x) x<<1
#define rs(x) x<<1|1
#define MAXN 20240601
#define inf 2114514
#define mf 5011
#define sf 1011
#define MOD 6421
#define PHI_MOD 6420 
using namespace std;
mt19937_64 randint{std::chrono::steady_clock::now().time_since_epoch().count()};
int tot,cnt[inf]={0};
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    
    for(ri i=1;i<=MAXN;i++) {
        if(i%MOD==0) ++cnt[0];
        else ++cnt[ksm(i%MOD,i%PHI_MOD)];
    }
    for(ri r=0;r<MOD;r++) {
        int s=(MOD-r)%MOD;
        if(r<s) tot+=cnt[r]*cnt[s];
        else if(r==s) tot+=cnt[r]*(cnt[r]-1)/2;
    }
    
    cout << tot << endl;
    return 0;
}