随便VP了一下大概是四题的样子

B. Build Roads

链接：https://ac.nowcoder.com/acm/contest/15600/B
来源：牛客网

题目描述

In the cat country, there are nnn cities. The cat country king wants to build n−1n-1n−1 roads to connect all the cities. The iii-th city has a construction company with an experience value of aia_iai. To build a road between the iii-th city and the jjj-th city, the two cities' construction companies need to cooperate with each other. However, in the process of building a road, the two construction companies may have conflicts due to poor communication, and it will result in a waste of building materials. Formally, building a road between the iii-th city and the jjj-th city will waste gcd⁡(ai,aj)\gcd(a_i, a_j)gcd(ai,aj) building materials.

Can you help the cat country king choose to build n−1n-1n−1 roads that connect all the cities and minimize the waste of building materials?

To decrease the input size, the king of the cat country gives you a random integer generator and 333 parameters L,R,seedL,R,seedL,R,seed. The following C language code shows how to generate nnn integers a1,a2,…,ana_1, a_2, \dots, a_na1,a2,…,an, and a[i]a[i]a[i] stores the experience value of the construction company of the iii-th city. You can use the code directly in your submissions.

输入描述:

The only line contains four integers n,L,R,seedn,L,R,seedn,L,R,seed (2≤n≤2×105,1≤L≤R≤2×105,1≤seed≤1018)(2 \le n \le 2 \times 10^5, 1 \le L \le R \le 2 \times 10^5, 1 \le seed \le 10^{18})(2≤n≤2×105,1≤L≤R≤2×105,1≤seed≤1018).

输出描述:

Print one integer -- the minimum waste of connecting all the cities.

示例1

输入

[复制](javascript:void(0)