C. 相邻重排 GCD 可分等差数列

    Type: Default 1000ms 256MiB

相邻重排 GCD 可分等差数列

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你正在参加国际构造排列大赛(International Construct Permutation Contest, ICPC),设 [ai]\left[ a_i \right] 是公差为 dd 的等差数列,一共有 nn 项。给定首项 a1a_1,请你将 [ai]\left[ a_i \right] 重新排列为 [pi]\left[ p_i \right] 并尝试求出

S=∑i=1n−1gcd⁡(pi,pi+1)S=\sum_{i=1}^{n-1}\gcd (p_i,p_{i+1})

的最小值。

输入描述

本题包含多个测试数据,第一行输入一个整数 tt 表示数据组数,其中 1⩽t⩽1×1041\leqslant t\leqslant 1\times 10^4

接下来 tt 行,每行输入一行由 33 个由空格隔开的整数 n,d,a1n,d,a_1,满足 $2\leqslant n\leqslant 1\times 10^5,0\leqslant d\leqslant 1\times10^9,1\leqslant a_i\leqslant 1\times10^9$。

保证所有测试点的 ∑n⩽2×105\sum n\leqslant 2\times 10^5。

输出描述

对于每个测试用例输出一个数,表示 SS 的最小值,请使用换行分隔输出每一组用例的结果。

样例

3
5 1 4
4 6 4
7 0 4
4
6
24