循序渐进

观察到 $Kruskal$ 生成树是最优解的一种.

将每种操作视为一条边，每个元素视为一个点即可构造一张图，最终结果就是最小生成树的值。

#include <bits/stdc++.h>
using namespace std;

int power(int a, int k, int p) // a^k%p
{
	int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (long long)res * a % p;
        a = (long long)a * a % p;
        k >>= 1;
    }
    return res;
}

int get_weight(int x, int y, int k)
{
	return (power(x, y, k) + power(y, x, k)) % k;
}

struct edge
{
	int u, v, w;
	edge(int u, int v, int k) :
		u(u), v(v), w(get_weight(u, v, k))
		{}
	bool operator<(const edge& o) const {
		return w < o.w;
	}
	bool operator>(const edge& o) const {
		return w > o.w;
	}
};

void solve()
{
	int l, r, k;
	cin >> l >> r >> k;
	int n = r - l + 1;
	vector<int> p(r - l + 1);
	iota(p.begin(), p.end(), 0);
	function<int(int)> find = [&](int x) -> int {
		if (p[x] == x) return x;
		return p[x] = find(p[x]);
	};
	priority_queue<edge, vector<edge>, greater<edge>> heap;
	for (int i = l; i < r; i++)
	{
		heap.push(edge(i, i + 1, k));
		if ((i << 1) > r) continue;
		heap.push(edge(i, i << 1, k));
	}
	long long cnt = 0, ans = 0;
	while (heap.size())
	{
		auto [u, v, w] = heap.top(); heap.pop();
		int pu = find(u - l), pv = find(v - l);
		if (pu == pv) continue;
		p[pu] = pv; cnt++;
		ans += (n - cnt) * w;
		// cout << u << " -> " << v << " : " << w << "\n";
		if (cnt == r - 1) break;
	}
	cout << ans << "\n";
}

int main()
{
	// int T = 1; cin >> T; while (T--) 
	solve();	
	return 0;
}

要说明的是，本题因数据都偏大，乘法和除法能够被用到的情况偏少，所以有些同学直接考虑遍历也通过了