编程介的小学生 2019-05-08 22:27 采纳率: 20.5%
浏览 110

最大公约数的平方的问题,采用C语言编程技术的实现过程代码运行的思路怎么实现?

Problem Description
There is a mysterious organization called GCD. They get a permutation P, permutation is a sequence of length N, only consists of number 1 to N and each number appears only once.
They want to gain magic power from this permutation. For the interval [L, R] they can get power:
∑i=LR∑j=i+1R∑k=j+1R(gcd(P[i],P[j])==P[k])⋅P[k]
Now they have M queries, for each query can you help them calculate how many power they can get?

Input
The first line is an integer T which indicates the case number.
And as for each case, first line is two integer N and M which indicates the length of permutation and number of query.
Next line is N integer which indicate the permutation P
Next M line, for each line is two integer L and R which indicate each query.

Limit
1≤T≤100
1≤N,M≤100000
1≤Pi≤N, for any pair (i,j), Pi≠Pj
1≤Li≤Ri≤N

About 95% test case: 1≤N≤1000
Other test case: 1≤N≤100000

Output
As for each case, you need to output M integer which indicate the answer of each query.

Sample Input
2
3 1
3 2 1
1 3
6 3
6 5 4 3 2 1
1 6
2 6
3 5

Sample Output
1
8
5
0

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题