您现在的位置是:网站首页> 内容页

UVA-10539 打表+二分

  • 铜雀台注册账号
  • 2019-09-24
  • 171人已阅读
简介题意非常简单,就是给你一个区间(闭区间),然后让你统计区间内有多少数满足本身不是素数,但只有一个素因子 首先注意题目中区间左右端点最大可以取到1e12,这早就超越了int的表示范围我们

题意非常简单,就是给你一个区间(闭区间),然后让你统计区间内有多少数满足本身不是素数,但只有一个素因子

 

首先注意题目中区间左右端点最大可以取到1e12,这早就超越了int的表示范围

我们首先打表计算出1e6内的素数表,然后计算所有满足要求的数,存进数组,最后排序

然后对于给定的区间[L,R],我们用二分找到上界和下届

二分一直是我心中的痛,总是用不好,以后碰一道二分记录一道

#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<cstring>#include<iomanip>#include<assert.h>#include<vector>#include<list>#include<map>#include<set>#include<sstream>#include<stack>#include<queue>#include<string>#include<bitset>#include<algorithm>#pragma warning(disable:4996)#define me(s) memset(s,0,sizeof(s))#define _for(i,a,b) for(int i=(a);i<(b);++i)#define _rep(i,a,b) for(int i=(a);i<=(b);++i)using namespace std;typedef pair <int, int> pii;typedef long long ll;typedef unsigned long long llu;const int inf = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double pi = acos(-1.0);const double eps = 1e-15;const int maxn = 1000000;ll p[maxn + 5], vis[maxn + 5], pcnt;vector<ll> ans;void init(){me(vis);pcnt = 0;for (int i = 2; i<maxn; i++) {if (!vis[i]) {p[pcnt++] = i;for (int j = 2; i*j < maxn; j++) vis[i*j] = true;}}for (int i = 0; i<pcnt; i++) {ll tmp = p[i] * p[i];//刚开始没用p数组没用ll坑死while (tmp < 1000000000000LL) {ans.push_back(tmp);tmp *= p[i];}}sort(ans.begin(), ans.end());}ll L, R;int main(){init();int T; scanf("%d", &T);while (T--) {scanf("%lld%lld", &L, &R);cout << lower_bound(ans.begin(), ans.end(), R+1) - lower_bound(ans.begin(), ans.end(), L) << endl;}}

  

文章评论

Top