17藍橋C語言B組 10.k倍區間 模

标題： k倍區間

給定一個長度為N的數列，A1, A2, … AN，如果其中一段連續的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍數，我們就稱這個區間[i, j]是K倍區間。

你能求出數列中總共有多少個K倍區間嗎？

輸入

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

以下N行每行包含一個整數Ai。(1 <= Ai <= 100000)

輸出

輸出一個整數，代表K倍區間的數目。

例如，

輸入：

5 2

1

2

3

4

5

程式應該輸出：

6

資源約定：

峰值記憶體消耗（含虛拟機） < 256M

CPU消耗 < 2000ms

請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入…” 的多餘内容。

注意：

main函數需要傳回0;

隻使用ANSI C/ANSI C++ 标準;

不要調用依賴于編譯環境或作業系統的特殊函數。

所有依賴的函數必須明确地在源檔案中 #include

不能通過工程設定而省略常用頭檔案。

送出程式時，注意選擇所期望的語言類型和編譯器類型。

——————————————————————————————————————————————

• 字首和
• 用sum記錄區間[1,i]的和，那麼有當(sum[i]-sum[s])%K=0，即[s,i]為K倍區間時，有sum[i]%K-sum[s]%K=0;就是說。。。。畫圖吧
• 最大1e10用long long

  

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
int n,K,a;
ll sum=0,res=0;
int ct[100005];
int main()
{
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		sum+=a;
		ct[sum%K]++;
	}
	ct[0]++;//因為本身是個K區間，最終再+ct[0]個，由1+2+…+(n-1)(+n)得到 
	for(int i=0;i<K;i++)
	{
		res+=(ll)ct[i]*(ct[i]-1)/2;
	}
	cout<<res<<endl;
	return 0;
}