本文共 1230 字，大约阅读时间需要 4 分钟。
做题感悟：这题属于想法题，比赛时直接做的 D 题。可是处理坐标处理的头晕眼花的结果到最后也没AC。
解题思路：
由于查询的时候仅仅考虑素数，so~我们仅仅考虑素数就能够，这就须要筛素数。我们能够在筛素数的同一时候把某个素数出现的倍数加上。输入的时候仅仅要记录某个数的个数就能够了。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std ;#define INT long long intconst 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"<
转载地址：http://wzzmx.baihongyu.com/