Guest User

E

a guest
Apr 25th, 2013
1,164
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2.  
  3. const int N = (int)1e7 + 100;
  4.  
  5. int lp[N], simples[N], simsz;
  6. long long cnt[N];
  7. bool ok(long long mid) {
  8. bool can = true;
  9. for(int i = 0; i < simsz && can; i++) {
  10. long long tmp = mid, f = 0;
  11. while(tmp) {
  12. tmp /= simples[i];
  13. f += tmp;
  14. }
  15. if (f < cnt[i])
  16. can = false;
  17. }
  18. return can;
  19. }
  20. int main() {
  21. int n, max = 0;
  22. scanf("%d", &n);
  23. long long rg = 0, lf = 1;
  24. for(int i = 0; i < n; ++i) {
  25. int a;
  26. scanf("%d", &a);
  27. if (a > max)
  28. max = a;
  29. rg += a;
  30. ++cnt[a];
  31. }
  32. for(int i = 2; i <= max; ++i) {
  33. if (lp[i] == 0) {
  34. lp[i] = i;
  35. simples[simsz++] = i;
  36. }
  37. for(int j = 0; j < simsz && simples[j] <= lp[i] && (long long)i*simples[j]<=max; ++j) {
  38. lp[i * simples[j]] = simples[j];
  39. }
  40. }
  41. for(int i = max; i>=2; i--)
  42. cnt[i] += cnt[i+1];
  43. for(int i = max; i>=2; i--) {
  44. if (lp[i] != i)
  45. cnt[lp[i]] += cnt[i];
  46. cnt[i / lp[i]] += cnt[i];
  47. }
  48. for(int i = 0; i < simsz; i++) {
  49. cnt[i] = cnt[simples[i]];
  50. }
  51. while (rg != lf) {
  52. long long mid = (rg+lf)>>1;
  53. if (ok(mid)) {
  54. rg = mid;
  55. } else lf = mid + 1;
  56. }
  57. printf("%I64d", lf);
  58. }
RAW Paste Data