Hadn't

我的微博Hadn_t

隨筆 - 40, 文章 - 0, 評論 - 19, 引用 - 0

數據加載中……

PKU 3005 Exploding CPU

呵呵過了這個題目挺高興
鍛煉了篩法和判斷素數的能力
還想了一個關鍵的枚舉剪枝
這個題目我是去枚舉題目中的A和第一個素數P1；
然后計算B 幷繼續推Pn
對小于1000000的數一次性篩出；
大數用最基本的判斷的方式。

Source Code
2

Problem: 3005 User: hongtaozhy
4

Memory: 4244K Time: 94MS
5

Language: G++ Result: Accepted
6

Source Code
8

#include<stdio.h>
9

#include<math.h>
10

#define SSS 6000
11

#define SIZE 1000000
12

#define INF 2000000000
13

#define NUM 200
14

__int64 aa[300];
15

__int64 rr[50000];
16

int pri[NUM];
17

int sub[SIZE];
18

int pdsu(__int64 n)
19

{
20

__int64 i;
21

if(n<=0||n==1 )
22

return 0;
23

if( n==2)
24

return 1;
25

else{
26

for(i=2; i*i<=n; i++)
27

if(n%i==0)
28

return 0;
29

}
30

return 1;
31

}
32

void sf(){
33

int temp,n;
34

for(int i=0;i<SIZE;i++)
35

sub[i]=1;
36

sub[0]=sub[1]=0;
37

for(int i=2;i<=sqrt(SIZE);i++){
38

if(sub[i]==1){
39

temp=2*i;
40

while(temp<=SIZE){
41

sub[temp]=0;
42

temp+=i;
43

}
44

}
45

}
46

}
47

int init(){
48

int j = 0 ;
49

pri[j++] = 2 ;
50

pri[j++] = 3 ;
51

for( int i = 3 ; i<SSS ;i++ ){
52

if(sub[i]){
53

pri[j++]=i;
54

}
55

}
56

return j;
57

}
58

int main(){
59

int num;
60

int t = 0 ;
61

__int64 res , next ,next2 ;
62

int b;
63

sf();
64

num = init();
65

sf();
66

for(int a = 1 ; a< 600 ; a++ ){
67

for(int i = 0; i<NUM ;i++ ){
68

res = pri[i] ;
69

b = pri[i] - a;
70

if(b == 0 ) continue;
71

next = a * pri[i] + b ;
72

if(next == pri[i]) continue;
73

if(res * next > INF){
74

continue;
75

}
76

if(next <0 )
77

continue;
78

if(next >= SIZE){
79

if(!pdsu(next))
80

continue ;
81

}
82

else{
83

if(!sub[next])
84

continue ;
85

}
86

res = res * next;
87

if(res >INF) continue;
88

while(1){
90

next2 = next * a +b;
91

if(next2 == next ) break;
92

if(res * next2 > INF){
93

break;
94

}
95

if(next2 <0 )
96

break;
97

if(next2 >= SIZE){
98

if(!pdsu(next2))
99

break ;
100

}
101

else{
102

if(!sub[next2])
103

break ;
104

}
105

res = res * next2;
106

if(res >INF) break;
107

rr[t++] = res ;
108

next = next2 ;
109

110

}
111

112

}
113

}
114

115

for(int i = 0 ; i<t ;i++ )
116

for(int j = i+1 ; j <t ;j++)
117

{
118

if(rr[i]>rr[j]){
119

int temp = rr[i];
120

rr[i] = rr[j];
121

rr[j] = temp;
122

}
123

124

}
125

int ccc = 0;
126

for(int i = 0 ; i <t ; i++)
127

{
128

if(rr[i]!= rr[i+1])
129

aa[ccc++]=rr[i];
130

}
131

// printf("init over\n");
132

int N;
133

__int64 zuo ,you ;
134

scanf("%d",&N);
135

while(N--){
136

scanf("%I64d%I64d",&zuo,&you);
137

138

int ans = 0 ;
139

for(int i = 0 ; i <243 ;i++){
140

if(zuo<=aa[i] && you>=aa[i])
141

ans++;
142

}
143

printf("%d\n",ans);
144

}
145

return 0 ;
146

}

posted on 2008-10-06 23:02 hadn't 閱讀(353) 評論(1) 編輯收藏引用

# re: PKU 3005 Exploding CPU 回復 更多評論

寫的什么程序啊看都看不懂

2009-07-03 15:14 | ddd

刷新評論列表

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

# re: PKU 3005 Exploding CPU 回復 更多評論

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

Hadn't

PKU 3005 Exploding CPU

評論

導航

常用鏈接

留言簿(2)

隨筆檔案(40)

wic'blog

友情鏈接

最新隨筆

搜索

積分與排名

最新隨筆

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

Hadn't

PKU 3005 Exploding CPU

評論

# re: PKU 3005 Exploding CPU 回復 更多評論

導航

常用鏈接

留言簿(2)

隨筆檔案(40)

wic'blog

友情鏈接

最新隨筆

搜索

積分與排名

最新隨筆

最新評論

閱讀排行榜

評論排行榜

# re: PKU 3005 Exploding CPU 回復更多評論