UVA 11610 Reverse Prime(数论+树状数组+二分)

2013 年 2 月 24 日3540

欢迎进入C/C++编程社区论坛,与300万技术人员互动交流 >>进入

  给出一个reverse_prime,自身是一个7位数,反转后是一个<=1e6的素数。

  首先求出所有的这种数

  两种操作

  q k :表示删除数字K

  http://http://www.zjjv.com///index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2657

  首先预处理出所有的reverse_prime,我的做法是先打出<=1e6的所有素数

  然后将其反转,可以看出所有素数都是6位数,但是题目要求是7位数,可见原数的最低位都为0,可以不考虑这个0,之后的效率也许会快点。

  将所有素数反转,然后凑成6位数。再算出每个数的素因子个数,不要忘记之前少算的末尾的0,也就是因子2和因子5.

  对于统计部分,建立两个树状数组,第一 个表示区间内还有多少个数,第二个表示区间内因子个数和。

  对于D操作, 直接用map记录某个reverse_prime的下标,然后更新两个树状数组

  对于q操作,二分位置,然后用第一个树状数组,可以知道区间内有多少个数。最后用第二个树状数组求和。

  [cpp]

  #include<iostream>

  #include<cstdio>

  #include<map>

  #include<cstring>

  #include<cmath>

  #include<vector>

  #include<algorithm>

  #include<set>

  #include<string>

  #include<queue>

  #define inf 1600005

  #define M 40

  #define N 1000000

  #define maxn 300005

  #define eps 1e-12

  #define zero(a) fabs(a)<eps

  #define Min(a,b) ((a)<(b)?(a):(b))

  #define Max(a,b) ((a)>(b)?(a):(b))

  #define pb(a) push_back(a)

  #define mp(a,b) make_pair(a,b)

  #define mem(a,b) memset(a,b,sizeof(a))

  #define LL unsigned long long

  #define MOD 1000000007

  #define lson step《1

  #define rson step《1|1

  #define sqr(a) ((a)*(a))

  #define Key_value ch[ch[root][1]][0]

  #define test puts("OK");

  #define pi acos(-1.0)

  #define lowbit(x) ((-(x))&(x))

  #pragma comment(linker, "/STACK:1024000000,1024000000")

  using namespace std;

  int flag[N]={0},prime[N],cnt=0;

  int fac[N],a[N],tot=0,p[N];

  LL s1[N],s2[N];

  map<int,int>m;

  int slove(int num){

  int len=0,ret=0,bit[20];

  while(num){

  bit[len++]=num%10;

  num/=10;

  }

  for(int i=0;i<len;i++)

  ret=ret*10+bit[i];

  while(ret<100000) ret*=10;

  return ret;

  }

[1][2]下一页

【责编:peter】

0 0