k倍區(qū)間

給定一個(gè)長(zhǎng)度為N的數(shù)列，A1, A2, ... AN，如果其中一段連續(xù)的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍數(shù)，我們就稱這個(gè)區(qū)間[i, j]是K倍區(qū)間。??

你能求出數(shù)列中總共有多少個(gè)K倍區(qū)間嗎？??

輸入

-----

第一行包含兩個(gè)整數(shù)N和K。(1 <= N, K <= 100000)??

以下N行每行包含一個(gè)整數(shù)Ai。(1 <= Ai <= 100000)??

輸出

輸出一個(gè)整數(shù)，代表K倍區(qū)間的數(shù)目。??

例如，

輸入：

5 2

1??

2??

3??

4??

5??

程序應(yīng)該輸出：

6

資源約定：

峰值內(nèi)存消耗（含虛擬機(jī)） < 256M

CPU消耗? < 2000ms

請(qǐng)嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請(qǐng)您輸入...” 的多余內(nèi)容。

注意：

main函數(shù)需要返回0;

只使用ANSI C/ANSI C++ 標(biāo)準(zhǔn);

不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。

所有依賴的函數(shù)必須明確地在源文件中 #include <xxx>

不能通過工程設(shè)置而省略常用頭文件。

提交程序時(shí)，注意選擇所期望的語言類型和編譯器類型。

前綴和法

這種方法對(duì)于該題不能得滿分，因?yàn)樵擃}數(shù)據(jù)量范圍大，前綴和法無法遍歷這么多的數(shù)量級(jí)

C++代碼：

樣例運(yùn)行結(jié)果：

純數(shù)學(xué)法：

之后我會(huì)持續(xù)更新，如果喜歡我的文章，請(qǐng)記得一鍵三連哦，點(diǎn)贊關(guān)注收藏，你的每一個(gè)贊每一份關(guān)注每一次收藏都將是我前進(jìn)路上的無限動(dòng)力 ?。?！↖(▔▽▔)↗感謝支持！