#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;
inline int read()
{
int x = 0, f = 1; char ch = getchar();
while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
struct edge{
int u, v, w;
}g[N];
int a[N], fa[N];
int n, m, ans;
bool cmp(edge a,edge b){
return a.w > b.w;
}
int fpow(int a, int b, int p)
{
int res = 1;
while(b > 0)
{
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int getf(int x){
return fa[x] == x ? x : (fa[x] = getf(fa[x]));
}
void Merge(int x, int y){
if((x == getf(x)) == (y == getf(y))) return;
if(fa[x] < fa[y]) fa[x] += fa[y],fa[y] = x;
else fa[y] += fa[x], fa[x] = y;
}
int kruskal(int n, int tot){
sort(g + 1, g + tot + 1, cmp);
ans = 0;
for(int i = 1, x, y, w;i <= tot;i ++){
x = g[i].u;
y = g[i].v;
w = g[i].w;
if(getf(x) == getf(y)) continue;
ans += w;
fa[getf(x)] = getf(y);
}
return ans;
}
signed main() {
int T = 1;
int tot = 0;
while(T --)
{
n = read();
m = read();
for (int i = 1;i <= n; ++ i) a[i] = read(), fa[i] = i;
for (int i = 1;i <= n; ++ i)
{
for (int j = 1;j < i; ++ j)
{
g[ ++ tot].u = i;
g[tot].v = j;
g[tot].w = (fpow(a[i], a[j], m) + fpow(a[j], a[i], m)) % m;
//fa[tot] = i;
}
}
cout << kruskal(n - 1, tot) << "\n";
}
return 0;
}
4 个赞
ok，我过了，快速幂没取模。
4 个赞