c487.
kevin 的大城市
內容
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 的建造計畫
輸出說明
對於每一個詢問，請輸出建造道路的花費總和
範例輸入
#1
5 4 2 3 12 4 9 1 5 3 3 2 4 1 4
範例輸出
#1
45 12 27 32
測資資訊：
記憶體限制：
256
MB
提示 ：
測試資料中
前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 |
|
c487 | 748 | 2018-05-30 21:11 |