HDU 4548美素数(セグメントツリー)
14782 ワード
美素数
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 374 Accepted Submission(s): 159
Problem Description
明ちゃんは対数の研究が好きで、数といえば、頭の中に多くの問題が現れて、今日、明ちゃんは素数に対する認識を試験したいと思っています.
問題は、1つの10進数が素数であり、その各数字と素数であれば、29のように「美素数」と呼ばれ、それ自体が素数であり、2+9=11も素数であるため、美素数である.
区間を指定して、この区間に何個の美素数があるか計算できますか?
Input
1行目には、T組のデータが合計であることを示す正の整数Tが入力される(T<=10000).
次にT行を合計し、各行に2つの整数L、R(1<=L<=R<=1000000)を入力し、区間の左値と右値を表す.
Output
各セットのデータについて、Case数を先に出力し、次に区間内の美素数の個数(端点値L,Rを含む)を出力する.
各グループのデータは1行を占め、具体的な出力フォーマットはサンプルを参照してください.
Sample Input
3 1 100 2 2 3 19
Sample Output
Case #1: 14 Case #2: 1 Case #3: 4
Source
2013金山西山居クリエイティブゲームプログラム挑戦試合-初戦(2)
Recommend
liuyiding
1、表+列挙を打つ:
2,線分ツリー,,
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 374 Accepted Submission(s): 159
Problem Description
明ちゃんは対数の研究が好きで、数といえば、頭の中に多くの問題が現れて、今日、明ちゃんは素数に対する認識を試験したいと思っています.
問題は、1つの10進数が素数であり、その各数字と素数であれば、29のように「美素数」と呼ばれ、それ自体が素数であり、2+9=11も素数であるため、美素数である.
区間を指定して、この区間に何個の美素数があるか計算できますか?
Input
1行目には、T組のデータが合計であることを示す正の整数Tが入力される(T<=10000).
次にT行を合計し、各行に2つの整数L、R(1<=L<=R<=1000000)を入力し、区間の左値と右値を表す.
Output
各セットのデータについて、Case数を先に出力し、次に区間内の美素数の個数(端点値L,Rを含む)を出力する.
各グループのデータは1行を占め、具体的な出力フォーマットはサンプルを参照してください.
Sample Input
3 1 100 2 2 3 19
Sample Output
Case #1: 14 Case #2: 1 Case #3: 4
Source
2013金山西山居クリエイティブゲームプログラム挑戦試合-初戦(2)
Recommend
liuyiding
1、表+列挙を打つ:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1000010;
int isprime[N],prime[N],res[N];
void getprime(){
int i,j;
prime[0]=0;
for(i=0;i<N;i++)
isprime[i]=1;
for(i=2;i<N;i++)
if(isprime[i]){
prime[++prime[0]]=i;
for(j=2;i*j<N;j++)
isprime[i*j]=0;
}
}
int isok(int x){
for(int i=2;i*i<=x;i++)
if(x%i==0)
return 0;
return 1;
}
int cnt;
void Init(){
getprime();
cnt=0;
int tmp;
for(int i=1;i<=prime[0];i++){
tmp=prime[i];
int k=0;
while(tmp){
k+=tmp%10;
tmp/=10;
}
if(isok(k))
res[cnt++]=prime[i];
}
}
int main(){
//freopen("input.txt","r",stdin);
int t;
int l,r;
int cases=0;
scanf("%d",&t);
Init();
while(t--){
scanf("%d%d",&l,&r);
int ans=0;
for(int i=0;i<cnt && res[i]<=r;i++)
if(res[i]>=l)
ans++;
printf("Case #%d: %d
",++cases,ans);
}
return 0;
}
2,線分ツリー,,
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000010;
#define L(rt) (rt<<1)
#define R(rt) (rt<<1|1)
struct Tree{
int l,r;
int num;
}tree[N<<2];
int a[N]={0,0,1,1},ans;
int get(int x){
int res=0;
while(x){
res+=x%10;
x/=10;
}
return res;
}
void PushUp(int rt){
tree[rt].num=tree[L(rt)].num+tree[R(rt)].num;
}
void build(int L,int R,int rt){
tree[rt].l=L;
tree[rt].r=R;
tree[rt].num=0;
if(tree[rt].l==tree[rt].r){
if(a[L]==1 && a[get(L)]==1)
tree[rt].num=1;
return ;
}
int mid=(L+R)>>1;
build(L,mid,L(rt));
build(mid+1,R,R(rt));
PushUp(rt);
}
void query(int L,int R,int rt){
if(tree[rt].l==L && tree[rt].r==R){
ans+=tree[rt].num;
return ;
}
if(tree[rt].l==tree[rt].r)
return ;
int mid=(tree[rt].l+tree[rt].r)>>1;
if(R<=mid)
query(L,R,L(rt));
else if(L>mid)
query(L,R,R(rt));
else{
query(L,mid,L(rt));
query(mid+1,R,R(rt));
}
}
void Init(){
int i,j,k=4;
for(i=5;i<N;i+=k^=6){ // 5 , 2, 4,6 ,
if(a[i]==0){
a[i]=1;
for(j=i;j<=N/i;j++)
a[j*i]=-1;
}
}
build(0,N-1,1);
}
int main(){
//freopen("input.txt","r",stdin);
Init();
int t;
scanf("%d",&t);
int a,b,cases=0;
while(t--){
scanf("%d%d",&a,&b);
ans=0;
query(a,b,1);
printf("Case #%d: %d
",++cases,ans);
}
return 0;
}