算是很难的题目了
准备测试数据
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | #include <stdio.h> #define MM_SIZE 50 #define BIG_NUMBER 99999999 int bottle_cell[MM_SIZE+1]; int bottle_num[MM_SIZE+1]; void split_cell(int n, int n_cell[], int n_num[]) { int i, j, now; int t, count=0; t = sqrt(n+1); for (i=0; i<=MM_SIZE; i++) n_num[i]=0; for (i=2; i<=t; i++) { if (n%i!=0) continue; count++; n_cell[count] = i; while (n % i ==0) { n_num[count]++; n = n / i; /* printf("i=%d n=%d ",i,n); */ } } if (count==0) { n_cell[1]=n; n_num[1]=1; count++; } n_num[0] = n_cell[0] = count; } int calc_step(int cell, int num, int n_cell[], int n_num[]) { int i; int pos=0, now; int count=1; /* printf("call func: cell %d num %dn", cell, num); */ for (i=1; i<=n_cell[0]; i++) if (n_cell[i]==cell) pos=i; /* printf("pos=%dn", pos); */ if (!pos) return 0; now = n_num[pos]; /* printf("now=%d num=%dn", now, num); */ if (num % n_num[pos] == 0) count = num / n_num[pos]; else count = 1 + num / n_num[pos]; return count; } int main(int argc, char *argv[]) { int i, j, cur; int m1, m2; int n, t; int s[10000+1]; int steps[10000+1]; int n_cell[MM_SIZE]; int n_num[MM_SIZE]; int no_answer; int step, max; int pos, min; scanf("%d", &n); scanf("%d%d", &m1, &m2); for (i=1; i<=n; i++) scanf("%d", &s[i]); /* printf("n=%dn", n); printf("m1=%d m2=%dn", m1, m2); for (i=1; i<=n; i++) printf("%d ", s[i]); */ if (m1==1) { printf("%dn", 0); return 0; } split_cell(m1, bottle_cell, bottle_num); for (i=1; i<=bottle_num[0]; i++) { bottle_num[i] *= m2; /* printf("num%d=%dn", i, bottle_num[i]); */ } for (i=1; i<=n; i++) { split_cell(s[i], n_cell, n_num); max = 0; for (j=1; j<=bottle_num[0]; j++) { step = calc_step(bottle_cell[j], bottle_num[j], n_cell, n_num); if (step==0) { break; } if (step>max) max = step; } if (!step) steps[i] = 0; else steps[i] = max; /* printf("max step=%dn", max); */ } min = BIG_NUMBER; for (i=1; i<=n; i++) { if (!steps[i]) continue; if (steps[i]<min) { pos = i; min = steps[i]; } } if (min==BIG_NUMBER) printf("%dn", -1); else printf("%dn", min); return 0; } |
