Loading... 本题会给你一段长度为N的整数序列,并进行K次询问。每次询问要求你给出区间a到b的和(序列**下标由1到N**)。由于区间和可能较大,请你输出它**对10000019取模**的结果。 (注意:如果你想不到高效的做法,可以用朴素算法得到一部分分,但本题满分需要你用一个比较高效的做法。) ## 输入格式: 首先一行整数N,代表序列长度。 接下来一行N个整数,为序列内容。 接下来一行整数K,代表对区间和的询问次数。 接下来K行,每行两个整数a和b,请你输入序列的第a到b号元素(含)的和取模后的结果。 ## 输出格式: 一共K行,每行一个整数,代表询问的区间和取模后的结果。 ## 输入样例: 在这里给出一组输入。例如: ```in 5 1 2 3 4 5 3 1 5 2 3 3 3 ``` ## 输出样例: 在这里给出相应的输出。例如: ```out 15 5 3 ``` ## 数据限制: N<=106 K<=105 ## 答案(感谢邱靖贤学长的提示,算法很赞!) ```cpp #include<stdio.h> int main() { int m=0,c,d; long long int n; scanf("%lld",&n); long long int a[1000010]={0}; a[0]=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i]+=a[i-1]; } scanf("%d",&m); while(m--) { scanf("%d %d",&c,&d); c--; printf("%d",(a[d]-a[c])%10000019); if(m) printf("\n"); } return 0; } ``` 最后修改:2021 年 05 月 25 日 © 禁止转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏