c265. 數學遊戲 - 高中生程式解題系統

內容

相信大家在很小的時候就學過如何判別一個數是不是另一個數的倍數，用除法就好了。而當要判斷的數字很小時，常常有特別的判斷法。例如，判斷一個數是不是3的倍數時只要把所有位數的數字加起來看看是不是3的倍數就好了。有個有名的數學問題是這樣子的：請寫出一個10位數，每個位數的數字都不重複(也就是剛好是0~9)，其中要滿足第1位數是1的倍數，前2位數是2的倍數，前3位數是3的倍數，…，前9位是9的倍數，前10位是10的倍數。

而今天皓皓和裴裴決定玩一個類似的數學遊戲。首先，裴裴在黑板上從左至右寫下n個數字。接下來裴裴會做q件事，他有2種事可以做。第一種是把一個數字擦掉並在同個位置寫下另一個數字；第二種是問皓皓如果把黑板上第L個數字至第R個數字全部合併在一起，那這個數字是不是k的倍數?請在每次裴裴做第二件事時，幫皓皓回答他的問題。

例如：黑板上寫下 2 3 0 12 5 這五個數字。如果裴裴問說”第1個到第3個數字合併在一起是不是5的倍數?”，答案就是YES，因為230是5的倍數。如果裴裴問說”第3個到第5個數字合併在一起是不是4的倍數?”，答案就是NO，因為0125=125不是4的倍數。

輸入說明

每筆測資的第一行有兩個數字n和q，分別代表裴裴在黑板上寫下了幾個數字還有裴裴要做幾件事。接下來一行有n個數字a1~an，代表黑板上的n個數字。接下來q行，每行的第一個數字o代表裴裴做了哪件事。若o=1，接下來會有2個數字x,v，代表裴裴把第x個數字ax擦掉並改成數字v。若o=2，接下來會有3個數字L,R,k，代表裴裴問了皓皓一個問題：”如果把黑板上第L個數字至第R個數字全部合併在一起，那這個數字是不是k的倍數?”

(1≦n,q≦105,0≦ai≦1000,o=1或2,1≦x≦n, 0≦v≦1000, 1≦L≦R≦105,2≦k≦50)

輸出說明

每次裴裴做第二件事時，輸出一行代表皓皓應該回答的答案。若答案為是，輸出YES；否則，輸出NO。

範例輸入 #1

//sample input 1
5 5
2 3 0 12 5
2 1 3 5
2 3 5 4
1 5 16
2 1 5 3
2 3 3 17
//sample input 2
10 10
3 8 1 6 5 4 7 2 9 0
2 1 1 1
2 1 2 2
2 1 3 3
2 1 4 4
2 1 5 5
2 1 6 6
2 1 7 7
2 1 8 8
2 1 9 9
2 1 10 10

範例輸出 #1

//sample output 1
YES
NO
YES
YES
//sample output 2
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

測資資訊：

記憶體限制： 256 MB

提示：

請仔細看每個測資的特殊條件歐!

測資配置:

(1)測資一(5分)

k=2或5或10

(2)測資二(8分)

保證所有時刻0≦ai≦9,且保證每次裴裴做第二件事時R-L≦7

(3)測資三(17分)

保證所有時刻0≦ai≦9,且1≦n,q≦1000

(4)測資四(10分)

1≦n,q≦1000

(5)測資五(10分)

k=3或9，且裴裴不會做第一件事情

(6)測資六(15分)

k=3或9

(7)測資七(15分)

保證所有時刻0≦ai≦9

(8)測資八(20分)

無特殊限制

標籤:

出處:

[管理者： VacationClub (雄中公假社) ]

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