回『DDJ競賽題目』
a516: E. Benson 的 LCM
標籤 :
通過比率 : 2人/3人 ( 67% ) [非即時]
評分方式：
Tolerant

最近更新 : 2021-07-04 22:20

內容

身為數學電神 Benson，不論是級數、排列組合、線性代數沒有甚麼可以難倒他的，但是某天他在學最大公因數、最小公倍數的時候，讓他非常懊惱的性質 $a\times b=gcd(a,b)\times lcm(a,b)$，其中 gcd 為最大公因數， lcm 為最小公倍數。但不會證明的他，還是得背這個性質，於是他就自己出了題來練習。現在來看看是 Benson 寫得比較快還是你寫的比較快！

 

一開始有空的序列，接著每次有兩種操作其中之一:

  • $A.$ 將 $x$ 位置上的值設為 $v$。
  • $B.$ 查詢 $[l,\ r]$ 的最小公倍數，如果位置為空，則代表 $1$。
     

每個 tast case 第一筆操作必為 $A.$。

 

輸入說明

第一行有兩個數 $N,Q$ 表示最大範圍 (即 $1\le l\le r\le N$) 和詢問次數。

接著有 $Q$ 行每行有三個數，

先讀入 $op$，

  • $op=1$ 再讀入 $x,\ v$，將在 $x$ 位置上的值設為 $v$，
  • $op=0$ 再讀入 $l,\ r$，詢問 $[l,\ r]$ 的最小公倍數。
     
輸出說明

對於每個 $op=0$ 輸出題敘所求。

範例輸入 
100 12
1 5 2
0 1 100
1 25 7
1 4 9
0 1 5
1 51 11
0 50 100
0 1 100
1 99 9
1 98 8
0 98 100
0 1 100
範例輸出 
2
18
11
1386
72
5544
測資資訊：
記憶體限制： 64 MB
公開 測資點#0 (5%): 1.0s , <1M
公開 測資點#1 (5%): 1.0s , <1M
公開 測資點#2 (7%): 1.0s , <1M
公開 測資點#3 (8%): 1.0s , <10M
公開 測資點#4 (17%): 1.0s , <10M
公開 測資點#5 (18%): 1.0s , <10M
公開 測資點#6 (18%): 1.0s , <10M
公開 測資點#7 (22%): 1.5s , <50M
提示 ：

# subtask (5+5)% : $N\le1000,\ Q\le1000$。

# subtask (7+8)% : $N\le500000,\ Q\le100000$。

# subtask (17+18)% : $N\le10^9,\ Q\le500000$。

# subtask (18 +22)% : $N\le10^{18},\ Q\le500000$。

# 對於 100% 的測資 : $1\le 答案\le2^{31}-1,\forall op\in\{0,1\},1\le x\le N,1\le v\le10^4$。

標籤:
出處:
DDJ Regular ContestRound#6 [管理者：
fdhs109_GT (9th 進階助教)
]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」