2009年12月21日星期一.sgu499
注：此文包括線性篩法，質因子分解，dfs生成一個數的所有因子
sgu499:我想撞墻
http://www.shnenglu.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.shnenglu.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(1, 0);
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++) {
過了。。。。。