SHARE
TWEET

E

a guest Apr 25th, 2013 758 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top