Codeforces 385C Bear and Prime Numbers
and Codeforces Numbers Prime
2023-09-14 09:07:56 时间
题目链接:Codeforces 385C Bear and Prime Numbers
这题告诉我仅仅有询问没有更新通常是不用线段树的。或者说还有比线段树更简单的方法。
用一个sum数组记录前n项和,这个sum数组在打素数表时候就能够求出来,注意一点求素数的内层循环要改成i。不能再写成i + i或者i * i了。原因想想就明确了。
这学期最后一场比赛也结束了,结果不非常惬意但也还好。
总的来说这学收获还是蛮多的。
近期可能就不再做ACM了吧,可能要复习CET6了吧,可能要复习期末考试的内容了吧。可能要考研了吧。。
#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int MAX_N = 1000000 * 10 + 1000; bool primes[MAX_N]; long long sum[MAX_N]; int arr[MAX_N], cnt[MAX_N]; //primes[i] = 0表示i是素数,为1表示i不是素数 void get_primes() { memset(primes,0,sizeof primes); primes[0]=primes[1]=1; for(int i=2;i<MAX_N;i++) { sum[i] = sum[i - 1]; if(!primes[i]) { for(int j=i;j<MAX_N;j+=i) { sum[i] += cnt[j]; primes[j]=1; } } } } int main() { int n, _max = 0; scanf("%d", &n); memset(sum, 0, sizeof(sum)); memset(cnt, 0, sizeof(cnt)); for(int i = 1; i <= n; i++) { scanf("%d", &arr[i]); cnt[arr[i]]++; _max = max(_max, arr[i]); } get_primes(); int q, a, b; scanf("%d", &q); for(int i = 0; i < q; i++) { scanf("%d%d", &a, &b); if(a > _max && b > _max) puts("0"); else { if(a > _max) a = _max; if(b > _max) b = _max; printf("%I64d\n", sum[b] - sum[a - 1]); } } return 0; }
相关文章
- [Typescript] Extends and override an existing interface
- [Javascript] Chaining the Array map and filter methods
- [Angular] Remove divs to Preserve Style and Layout with ng-container in Angular
- [AngularJS] Default Child state and nav between child state
- [Unit Testing for Zombie] 04. Mock and Stub
- 【Codeforces 1083A】The Fair Nut and the Best Path
- 【Codeforces 339C】Xenia and Weights
- 【Codeforces 385C】Bear and Prime Numbers
- 【Educational Codeforces Round 48 (Rated for Div. 2) D】Vasya And The Matrix
- 【Educational Codeforces Round 37 F】SUM and REPLACE
- 【77.39%】【codeforces 734A】Anton and Danik
- 【32.89%】【codeforces 574D】Bear and Blocks
- 【codeforces 766C】Mahmoud and a Message
- 【codeforces 793B】Igor and his way to work
- 【codeforces 515A】Drazil and Date
- 【Codeforces Round #430 (Div. 2) D】Vitya and Strange Lesson
- 【codeforces 367C】Sereja and the Arrangement of Numbers
- 【codeforces 46C】Hamsters and Tigers
- Fiori offline support : overrideRefreshHandling and injectRefreshList
- 成功解决TypeError: Cannot compare types ‘ndarray(dtype=float64)‘ and ‘str‘
- Codeforces Round #252 (Div. 2) B. Valera and Fruits(模拟)
- Codeforces #250 (Div. 2) C.The Child and Toy