行业知识
【蓝桥杯】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的主机名怎么定义