Why so serious? --[NKU]schindlerlee

2009年12月21日星期一.sgu499

2009年12月21日星期一.sgu499
注:此文包括线性筛法,质因子分解,dfs生成一个数的所有因子

sgu499:我想撞墙
http://www.cppblog.com/schindlerlee/
那天arxor看我和angelclover在做,然后也在看题,这个题我还没看,然后arxor大牛就给我说了个想法

把每个数分解素因子,然后dfs出这个数的所有因子。
对每个数进行一次此操作,最后找最大的且被访问了两边以上的因子,
但是这个方法tle在test 20了。怪我当时没细想,被大牛随便一说就觉得这个方法很好。。。。然后。。。杯具了

上代码:tle@20
 1 /*
 2  * SOUR:sgu Greatest Greatest Common Divisor
 3  * ALGO:因子分解
 4  * DATE: 2009年 12月 20日 星期日 19:24:49 CST
 5  * COMM:3http://www.cppblog.com/schindlerlee/
 6  * */
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<cstdlib>
10 #include<cstring>
11 #include<algorithm>
12 using namespace std;
13 typedef long long LL;
14 const int maxint = 0x7fffffff;
15 const long long max64 = 0x7fffffffffffffffll;
16 
17 const int N = 1000010;
18 int vis[N], n, is_prime[N], primes[N], top;
19 int exp[100], num[100], cnt;
20 int can[N];
21 void generate()
22 {
23     int i, j, k;
24     top = 0;
25     fill(is_prime, is_prime + N, 1);
26     for (i = 2; i <= 1000000; i++) {
27         if (is_prime[i]) {
28             primes[top++= i;
29         }
30         for (j = 0; j < top && i * primes[j] <= 1000000; j++) {
31             is_prime[i * primes[j]] = 0;
32             if (i % primes[j] == 0)
33                 break;
34         }
35     }
36     //for(i = 0;i < top;i++) {
37     //printf("%d\n",primes[i]);
38     //}
39 }
40 
41 void factor(int x)
42 {
43     //printf("factor %d\n",x);
44     cnt = 0;
45     for (int i = 0; i < top && x > 1; i++) {
46         if (x % primes[i] == 0) {
47             //printf("primes[i] = %d\n",primes[i]);
48             can[i]++;
49             num[cnt] = primes[i];
50             exp[cnt] = 0;
51             while (x % primes[i] == 0) {
52                 exp[cnt]++;
53                 x /= primes[i];
54             }
55             cnt++;
56         }
57     }
58 }
59 
60 void dfs(int x, int level)
61 {
62     if (level == cnt) {
63         //printf("dfs x= %d\n",x);
64         vis[x]++;
65         return;
66     }
67     dfs(x, level + 1);
68     for (int i = 1; i <= exp[level]; i++) {
69         x *= num[level];
70         dfs(x, level + 1);
71     }
72 }
73 
74 int main()
75 {
76     int i, j, k;
77     generate();
78     scanf("%d"&n);
79     for (i = 0; i < n; i++) {
80         scanf("%d"&k);
81         factor(k);
82         dfs(10);
83     }
84     for (i = N - 1; i >= 0; i--) {
85         if (vis[i] >= 2) {
86             printf("%d\n", i);
87             break;
88         }
89     }
90     return 0;
91 }
92 

然后比赛完google了以下,原来是水题,不予解释了,贴代码
 1 
 2 const int N = 1000010;
 3 int vis[N],n,m;
 4 void chkmax(int &x,int k) { if(x < k) x = k; }
 5 int main()
 6 {
 7     int i,j,k;
 8     scanf("%d",&n);
 9     for(i = 0;i < n;i++) {
10         scanf("%d",&k);
11         vis[k] ++;
12         chkmax(m,k);
13     }
14 
15     int res = 1;
16     for(i = 2;i <= m;i++) {
17         int tmp = 0;
18         for(j = i;tmp < 2 && j <= m;j += i) {
19             tmp += vis[j];
20         }
21         if(tmp >= 2) res = i;
22     }
23     printf("%d\n",res);
24
25     return 0;
26 }
27 
28 

结果第二天arxor,说他用那个方法过了。。。。。。。。。
然后我看了他的代码,我发现原来我的因子分解是没有优化的。。。
然后把第45行改成
    for (int i = 0; primes[i] * primes[i] <= x && i < top && x > 1; i++) {

过了。。。。。

posted on 2009-12-21 20:54 schindlerlee 阅读(1085) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理