1004. 大户爱的干草堆

题目描述

大户爱正在研究干草堆，她看到有这么一道题：有 T 组数据，对于每组数据，给定一个长度为 n 的序列 a1, ..., an 以

ri

及 m 组询问 li, ri, ki，你需要对每组询问求出 ∑ gcd2 (aj, k)。

j=li

输入格式

一共 T 组数据，每组数据第一行两个整数 n, m 表示序列长度和询问数量。接下来一行 n 个整数表示 a1, ⋯, an。 接下来 m 行，每行三个整数

li, ri, ki 表示一次询问。

1≤T ≤51 ≤ n, m ≤ 105, 1 ≤ li ≤ ri ≤ n1 ≤ ai, ki ≤ 105

数据规模较大，请使用高效的输入输出方式。

输出格式

对于每组数据，m 行，每行一个整数一个询问的答案。

样例输入

1
12 6
1 2 3 4 5 6 7 8 9 10 11 12
1 12 1
1 12 2
1 12 3
1 12 4
3 8 6
1 12 12

样例输出

12
30
44
66
55
242

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第10场）