题解中的r-1应该为r-l,因为有r-l+1个点，则只需要连r-l条边，就可以使点全部连通。题解能通过是由于对于所有的测试点，都有l*2>r，导致循环结束的原因始终是堆空，而不是cnt==r-1。

积少成多

本题可以采取二分答案的策略，主要步骤如下：

1. 假定拥有 x 的力量可以完成该任务。
2. 任取一点（以左端点$l$为例），从该点开始dfs搜索。如果所需力量小于等于 x, 那么打上标记。
3. 如果所有点都被打上标记，那么x就是可行
4. 二分搜索 x 找到最优解。

复杂度为$\Theta((r-l)\times logk \times logw)$, 其中$l, r$是端点，$k$是模数，$w$是点的取值范围（此处为$10^9$）.

本题也有其它解法，比如并查集等。

#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;
	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));
	}
	int 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;
		cnt++; p[pu] = pv; ans = 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;
}