【藍(lán)橋杯學(xué)習(xí)記錄】K倍區(qū)間
一、題目
給定一個(gè)長(zhǎng)度為N的數(shù)列，A1, A2, ...... AN ，如果其中一段連續(xù)的子序列Ai,Ai+1, ...... Aj( i≤j ) 之和是K的倍數(shù)，我們就稱(chēng)這個(gè)區(qū)間 [i, j][i,j] 是 K 倍區(qū)間。你能求出數(shù)列中總共有多少個(gè) K 倍區(qū)間嗎？
第一行包含兩個(gè)整數(shù) N 和 K
以下 N 行每行包含一個(gè)整數(shù) Ai
輸出一個(gè)整數(shù)，代表 K 倍區(qū)間的數(shù)目。
二、數(shù)學(xué)知識(shí)
(a-b)%K==0等價(jià)于a&K==b%K
三、解題思路
本題很容易想到暴力的做法，就是用一個(gè)三層循環(huán)，但是這樣會(huì)超時(shí)。于是可以用前綴和，即sum[i]=A[1]+A[2]+·······A[i]。這樣每一個(gè)區(qū)間[i,j]的和就可以表示為sum[j]-sum[i]。由上面數(shù)學(xué)知識(shí)講到的等價(jià)式可知，我們想得到區(qū)間和對(duì)K取余==0，就是任意兩個(gè)前綴和對(duì)K取余得到的余數(shù)相等所以我們可以計(jì)算一下所有前綴和對(duì)K取余的余數(shù)的個(gè)數(shù)，并且用組合數(shù)公式來(lái)得到一共有幾個(gè)組合，即有幾個(gè)K倍區(qū)間。
四、完整代碼
五、出現(xiàn)的問(wèn)題
本來(lái)用暴力方法就已經(jīng)超時(shí)了，我在改成前綴和時(shí)又把求余數(shù)新加了一個(gè)循環(huán)，導(dǎo)致又超時(shí)了，挺笨的。還有就是測(cè)試數(shù)據(jù)有100000個(gè)，而我開(kāi)始把數(shù)組S設(shè)成了[100000]，但是我又棄用了S[0]導(dǎo)致數(shù)組越界了，另外答案很大，需要用long long類(lèi)型
六、參考資料
https://www.jianshu.com/p/3ed28f2bbcad
https://www.bbsmax.com/A/6pdD24EKJw/
