小工具知识网

当前位置: 首页 > 行业知识 > 【蓝桥杯】k倍区间

行业知识

【蓝桥杯】k倍区间

2026-11-19 02:07:48 来源:互联网转载

一.题目描述

二.问题分析 

对于该问题,���签上写的是暴力,但是如果使用暴力的话,会超时。

首先,对于两个数a,b(假设a小于b),若a与b对k取余后结果相同,则b-a可以整除k。

由此,我们可以利用上述结论:对于第i个数,我们只需要知道下标在1~i-1范围内有多少个和下标为1~i范围内数之和同余数的区间,该值等于新加入了第i个数之后k倍区间增加的数目。

//k倍区间#include using namespace std;const int N=1e5+2;int n,k;long long cnt=0;long long a[N]={0},c[N]={0};int main(int argc, const char * argv[]) {    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);      cin>>n>>k;        c[0]=1;    for(int i=1;i>a[i];        a[i]+=a[i-1];        cnt+=c[a[i]%k];        c[a[i]%k]++;    }    cout

上一篇:主机版这投篮怎么按绿啊

下一篇:hosts的主机名怎么定义