蓝桥杯-k倍区间

http://lx.lanqiao.cn/problem.page?gpid=T444
问题描述
　　给定一个长度为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
 
思维题：
 
打前缀和却不能n^2的复杂度，n的复杂度的话必须贪心
将前缀和都%k，计算余数相同的个数
发现规律：
若前缀和%k后 arr[i]==arr[j],那么从i+1~j-1必须是k的倍数
所以C(n,2)就行
不过记得%k==0的情况是C（n+1,2），因为这种情况可以单取的
 

#include<bits/stdc++.h>

using namespace std;

#define maxn 10000000

typedef long long ll;

#define inf 2147483647

#define ri register int

#define getchar() (Ss==Tt&&(Tt=(Ss=BB)+fread(BB,1,1<<15,stdin),Ss==Tt)?EOF:*Ss++)

char BB[ << ], *Ss = BB, *Tt = BB;

inline int read()

{

    int x=;

    int ch=getchar(),f=;

    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();

    if (ch=='-')

    {

        f=-;

        ch=getchar();

    }

    while (isdigit(ch))

    {

        x=(x<<)+(x<<)+ch-'';

        ch=getchar();

    }

    return x*f;

}

int n,k;

ll a[maxn];

ll arr[maxn];

ll x;

ll ans=;

int main()

{

//    freopen("test.txt","r",stdin);

    cin>>n>>k;

    for(int i=; i<=n; i++)

    {

        x=read();

        a[i]=x+a[i-];

        arr[a[i]%k]++;

    }

    arr[]++;

    for(int i=; i<k; i++)

    {

        ll x=arr[i];

        if(x>)

            ans+=x*(x-)/;

    }

    cout<<ans;

    return ;

}

蓝桥杯-k倍区间的相关教程结束。