Codeforces 385 C Bear and Prime Numbers
and Codeforces Numbers Prime
2023-09-14 09:06:25 时间
做题感悟:这题属于想法题,比赛时直接做的 D 题。可是处理坐标处理的头晕眼花的结果到最后也没AC。
解题思路:
由于查询的时候仅仅考虑素数,so~我们仅仅考虑素数就能够,这就须要筛素数。我们能够在筛素数的同一时候把某个素数出现的倍数加上。输入的时候仅仅要记录某个数的个数就能够了。
代码:
#include<iostream> #include<sstream> #include<map> #include<cmath> #include<fstream> #include<queue> #include<vector> #include<sstream> #include<cstring> #include<cstdio> #include<stack> #include<bitset> #include<ctime> #include<string> #include<iomanip> #include<algorithm> using namespace std ; #define INT long long int const int INF = 0x3f3f3f ; const double esp = 0.0000000001 ; const double PI = acos(-1.0) ; const int mod = 1000000007 ; const int MY = 100 + 5 ; const int MX = 10000000 + 5 ; int Max ,n ,m ; bool isprime[MX] ; int sum[MX] ,num[MX] ; void init() // 筛法同一时候记录个数 { memset(isprime ,false ,sizeof(isprime)) ; memset(sum ,0 ,sizeof(sum)) ; for(int i = 2 ;i <= Max ; ++i) { sum[i] += sum[i-1] ; if(!isprime[i]) { sum[i] += num[i] ; for(int j = i + i ;j <= Max ; j += i) { sum[i] += num[j] ; isprime[j] = true ; } } } } int main() { int x ; while(~scanf("%d" ,&n)) { memset(num ,0 ,sizeof(num)) ; Max = 0 ; for(int i = 0 ;i < n ; ++i) { scanf("%d" ,&x) ; num[x]++ ; // 记录个数 Max = max(Max ,x) ; } init() ; scanf("%d" ,&m) ; int le ,rt ; for(int i = 0 ;i < m ; ++i) { scanf("%d%d" ,&le ,&rt) ; if(rt > Max) rt = Max ; if(le > Max) cout<<"0"<<endl ; else cout<<sum[rt]-sum[le-1]<<endl ; } } return 0 ; }
相关文章
- codeforces MUH and Cube Walls
- [Typescript] Scopes and TypeParams
- [Java Spring data] Paging and sorting
- [Other] An Overview of Arrays and Memory
- [React] Create a queue of Ajax requests with redux-observable and group the results.
- [RxJS] Transformation operators: debounce and debounceTime
- Atitit.ALT+TAB没反应车and 点击任务栏程序闪烁但是不能切换
- atitit.提升备份文件复制速度(1) -----分析统计问题and解决方案
- 【Codeforces Round #635 (Div. 2) D】Xenia and Colorful Gems
- 【Codeforces Round #635 (Div. 2) A】Ichihime and Triangle
- 【Codeforces 339C】Xenia and Weights
- 【Codeforces 584D】Dima and Lisa
- 【Codeforces 1106E】Lunar New Year and Red Envelopes
- 【【henuacm2016级暑期训练】动态规划专题 M】Little Pony and Harmony Chest
- 【Codeforces Round #482 (Div. 2) C】Kuro and Walking Route
- 【23.24%】【codeforces 629C】Famil Door and Brackets
- 【24.17%】【codeforces 721D】Maxim and Array
- 【74.89%】【codeforces 551A】GukiZ and Contest
- 【35.29%】【codeforces 557C】Arthur and Table
- 【codeforces 742A】Arpa’s hard exam and Mehrdad’s naive cheat
- 【poj 1704】Georgia and Bob
- 【codeforces 602E】Kleofáš and the n-thlon
- 【codeforces 798C】Mike and gcd problem
- 【codeforces 514E】Darth Vader and Tree
- 【Codeforces Round #430 (Div. 2) D】Vitya and Strange Lesson
- Codeforces Round #311 (Div. 2)A Ilya and Diplomas