c487: kevin 的大城市
標籤 :
通過比率 : 82% (9 人 / 11 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-02-21 00:04

內容

kevin 有 N 個大城市,編號為 1 , 2 , ... , i , ... N,每個城市也有一個值 ai

這些城市目前都不存在向外連通的道路,接著 kevin 找到了建造道路的建商
建商承諾若要將城市 i 與城市 j 建起一道雙向道路 (i <= j),將花費 gcd(ai , ai+1 , ai+2 ..... , aj-1 , aj) 元

現在 kevin 手上有 Q 個大城市的建造計畫,
每個計劃是將城市 qL 到城市 qR 建成完全圖 (且每個點都要有自環)

但由於 kevin 吃啃得雞已經花掉了大部分的國庫,
使得kevin 不得不謹慎理財
你能幫幫 kevin 評估每個建造計畫的花費嗎?

輸入說明

第一行有兩個數字 N , Q
分別代表 kevin 的大城市數量和 kevin 手中的建造計畫數量

接下來一行有 N 個數字代表每個城市的值 ai

接下來有 Q 行

每一行有兩個數字 qL 和 qR 代表 kevin 的建造計畫

輸出說明

對於每一個詢問,請輸出建造道路的花費總和

範例輸入
5 4
2 3 12 4 9
1 5
3 3
2 4
1 4
範例輸出
45
12
27
32
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (7%): 1.0s , <1M
公開 測資點#1 (8%): 1.0s , <1M
公開 測資點#2 (12%): 1.5s , <10M
公開 測資點#3 (13%): 1.5s , <10M
公開 測資點#4 (10%): 1.0s , <10M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (8%): 1.0s , <10M
公開 測資點#8 (9%): 1.0s , <10M
公開 測資點#9 (6%): 1.0s , <10M
公開 測資點#10 (7%): 1.0s , <10M
提示 :

測試資料中

前15% N <= 500 , Q <= 1000

前40% N <= 3000 , Q <= 500000

前70% N <= 50000 , Q <= 50000

前87% N <= 100000 , Q <= 200000

前100% N <= 100000 , Q <= 500000

前100% 1 <= qL <= qR <= N

1 <= ai <= 10 ^ 9

 

第三筆詢問中,答案為

gcd(3, 3) + gcd(3, 12) + gcd(3, 12, 4) + gcd(12, 12) + gcd(12, 4) + gcd(4, 4) = 27

標籤:
出處:
[編輯:
boook (boook)
]


編號 身分 題目 主題 人氣 發表日期
14018
johnchen902 (johnchen902)
c487
解題報告
81 2018-05-30 21:11