[关闭]
@Falsyta 2015-10-26T23:53:57.000000Z 字数 11698 阅读 1386

PA2011

OI PA

想补的题快补完了……就单贴出来好了。

PA2011 pec

即使开坑还是颓得要死……
算了半天连样例都不会算就弃疗了……（又被自己蠢哭了……T_T

考虑让走的路最少。
从起点出发的次数是固定的。
走的时候把之后几次走这段路需要用的水都撒下去。

  1. # include <cstdio>
  2. # define REP_D(i, n) for (int i = n; i >= 1; -- i)
  3. typedef double dd;
  4. int main ()
  5. {
  6.     int s, w, k;
  7.     scanf ("%d%d%d", &s, &w, &k);
  8.     int ti = (w + k - 1) / k;
  9.     dd cur = 0, ans = 0;
  10.     REP_D (i, ti)
  11.     {
  12.         int c = i == ti ? w - (ti - 1) * k : k;
  13.         dd d = (dd) c / (2 * i - 1);
  14.         if (cur + d > s) return printf ("%.4f\n", w - s * (2 * i - 1) - ans), 0;
  15.         else cur += d, ans += 2 * cur;
  16.     }
  17.     printf ("%.4f\n", w - ans + cur);
  18.     return 0;
  19. }

PA2011 pod

老是幻想着线段树建图最短路可以过……
想起了自己炸掉的多校题……
直接线段树做BFS。

  1. # include <cstdio>
  2. # include <vector>
  3. # include <algorithm>
  4. using namespace std;
  5. # define REP(i, n) for (int i = 1; i <= n; ++ i)
  6. # define REP_0(i, n) for (int i = 0; i < n; ++ i)
  7. # define u t[x]
  8. # define lc ch[0]
  9. # define rc ch[1]
  10. # define ulfc t[u.lc]
  11. # define urtc t[u.rc]
  12. # define NR 501000
  13. # define MR 201000
  14. const int inf = 1 << 30;
  15. struct Seg {int ch[2], max; vector <int> cov;} t[NR << 2];
  16. int sz, q[NR], d[NR], L[MR], R[MR], head, tail, n, m, S;
  17. inline void segCov (int x, int l, int r, int cl, int cr, int id)
  18. {
  19.     if (cl <= l && r <= cr) {u.cov.push_back (id); return ;}
  20.     int mid = (l + r) >> 1;
  21.     if (cl <= mid) segCov (u.lc, l, mid, cl, cr, id);
  22.     if (cr > mid) segCov (u.rc, mid + 1, r, cl, cr, id);
  23. }
  24. inline int build (int l, int r) 
  25. {
  26.     int x = ++ sz, mid = (l + r) >> 1; u.max = inf;
  27.     if (l == r) return x; 
  28.     return u.lc = build (l, mid), u.rc = build (mid + 1, r), x;
  29. }
  30. inline void segPush (int x, int l, int r, int pl, int pr, int w)
  31. {
  32.     if (w >= u.max) return ;
  33.     if (l == r) {u.max = d[q[++ tail] = l] = w; return ;}
  34.     int mid = (l + r) >> 1;
  35.     if (pl <= mid) segPush (u.lc, l, mid, pl, pr, w);
  36.     if (pr > mid) segPush (u.rc, mid + 1, r, pl, pr, w);
  37.     u.max = max (ulfc.max, urtc.max);
  38. }
  39. inline void segLi (int x, int l, int r, int p, int w)
  40. {
  41.     int tl = u.cov.size (), mid = (l + r) >> 1;
  42.     REP_0 (i, tl) segPush (1, 1, n, L[u.cov[i]], R[u.cov[i]], w);
  43.     u.cov.clear ();
  44.     if (l == r) return ;
  45.     if (p <= mid) segLi (u.lc, l, mid, p, w);
  46.     else segLi (u.rc, mid + 1, r, p, w);
  47. }
  48. inline void bfs ()
  49. {
  50.     head = 1, segPush (1, 1, n, S, S, d[S] = 0);
  51.     while (head <= tail) {int x = q[head ++]; segLi (1, 1, n, x, d[x] + 1);}
  52.     REP (i, n) printf ("%d\n", d[i]);
  53. }
  54. int main ()
  55. {
  56.     scanf ("%d%d%d", &n, &m, &S);
  57.     build (1, n); int t1, t2;
  58.     REP (i, m) 
  59.     {
  60.         scanf ("%d%d%d%d", &L[2 * i - 1], &R[2 * i - 1], &L[2 * i], &R[2 * i]); 
  61.         segCov (1, 1, n, L[2 * i - 1], R[2 * i - 1], 2 * i);
  62.         segCov (1, 1, n, L[2 * i], R[2 * i], 2 * i - 1);
  63.     }
  64.     bfs ();
  65.     return 0;
  66. }

PA2011 cia

读错题+卡内存233
嘛……唯一的问题是二分确定每一位的话会不可减。
用线段树维护预处理的东西就好啦。

  1. # include <cstdio>
  2. # include <algorithm>
  3. # include <vector>
  4. using namespace std;
  5. # define REP(i, n) for (int i = 1; i <= n; ++ i)
  6. # define REP_0(i, n) for (int i = 0; i < n; ++ i)
  7. # define REP_D(i, n) for (int i = n; i >= 1; -- i)
  8. # define FOR(i, a, b) for (int i = a; i <= b; ++ i)
  10. # define u t[x]
  11. # define ulfc t[u.lc]
  12. # define urtc t[u.rc]
  13. # define LIM 1000000000000001000ll
  14. # define NR 101000
  15. # define w0 first
  16. # define w1 second
  17. typedef long long ll;
  18. typedef pair <ll, int> pli;
  20. struct Seg {int lc, rc; ll sum;} t[NR << 1];
  21. int rP, n, L, q0, tsz, a[NR], tp[NR], ans[NR][11]; 
  22. ll rK, *f[11], *bi, *iQ;
  23. vector <pli> q[2][NR];
  24. const int inf = 1 << 30;
  25. inline bool cmpP (int i, int j) {if (a[i] != a[j]) return a[i] < a[j]; return i < j;}
  26. inline void wAddTo (ll &x, ll y) {if (y == -1) x = -1; else if (x != -1) {x += y; if (x >= LIM) x = -1;}}
  27. void segAdd (int x, int l, int r, int p, ll d)
  28. {
  29.     wAddTo (u.sum, d);
  30.     if (l == r) return ;
  31.     int mid = (l + r) >> 1;
  32.     if (p <= mid) segAdd (u.lc, l, mid, p, d);
  33.     else segAdd (u.rc, mid + 1, r, p, d);
  34. }
  35. inline bool geq (ll t) {return t == -1 || t >= rK;}
  36. void segGet (int x, int l, int r)
  37. {
  38.     if (l == r) {rP = l; return ;}
  39.     int mid = (l + r) >> 1;
  40.     if (geq (ulfc.sum)) segGet (u.lc, l, mid); 
  41.     else rK -= ulfc.sum, segGet (u.rc, mid + 1, r);
  42. }
  43. bool segFind (int x, int l, int r, int p)
  44. {
  45.     if (l == r) 
  46.     {
  47.         if (geq (u.sum)) return rP = l, true;
  48.         return rK -= u.sum, false;
  49.     }
  50.     int mid = (l + r) >> 1;
  51.     if (p <= mid)
  52.     {
  53.         if (segFind (u.lc, l, mid, p)) return true;
  54.         if (geq (urtc.sum)) return segGet (u.rc, mid + 1, r), true;
  55.         return rK -= urtc.sum, false;
  56.     }
  57.     return segFind (u.rc, mid + 1, r, p);
  58. }
  59. int build (int l, int r) 
  60. {
  61.     int x = ++ tsz, mid = (l + r) >> 1; u.sum = 0;
  62.     if (l == r) return x;
  63.     return u.lc = build (l, mid), u.rc = build (mid + 1, r), x;
  64. }
  65. void solve (int lv)
  66. {
  67.     if (!lv) return ;
  68.     bool d = lv % 2;
  69.     int last = 0, root = build (1, n); tsz = 0;
  70.     if (lv == L)
  71.     {
  72.         REP (i, n) segAdd (root, 1, n, i, f[lv][i]);
  73.         REP (i, q0)
  74.         {
  75.             rK = iQ[i];
  76.             if (!segFind (root, 1, n, 1)) ans[i][0] = -1;
  77.             else q[!d][ans[i][0] = rP].push_back (pli (rK, i));
  78.         }
  79.         free (iQ), free (f[lv]), solve (lv - 1);
  80.         return ;
  81.     }
  82.     REP (i, n) q[!d][i].clear ();
  83.     REP (t, n)
  84.     {
  85.         int i = tp[t];
  86.         for (vector <pli>::iterator it = q[d][i].begin (); it != q[d][i].end (); ++ it)
  87.         {
  88.             rK = it->w0;
  89.             if (!segFind (root, 1, n, i)) ans[it->w1][0] = -1;
  90.             else q[!d][ans[it->w1][L - lv] = rP].push_back (pli (rK, it->w1));
  91.         }
  92.         q[d][i].clear ();
  93.         if (a[tp[t]] != a[tp[t + 1]]) FOR (k, last + 1, t) segAdd (root, 1, n, tp[k], f[lv][tp[k]]), last = t;
  94.     }
  95.     free (f[lv]), solve (lv - 1);
  96. }
  98. inline ll bSum (int x) {ll s = 0; for (; x; x -= x & -x) wAddTo (s, bi[x]); return s;}
  99. inline void bAdd (int x, ll d) {if (!x) return ; for (; x <= n; x += x & -x) wAddTo (bi[x], d);} 
  101. void init ()
  102. {
  103.     f[1] = (ll*) malloc ((n + 2) * sizeof (ll));
  104.     REP (i, n) f[1][i] = 1;
  105.     bi = (ll*) malloc ((2 * n + 2) * sizeof (ll));
  106.     FOR (i, 2, L)
  107.     {
  108.         int last = 0;
  109.         f[i] = (ll*) malloc ((n + 2) * sizeof (ll));
  110.         REP (j, 2 * n) bi[j] = 0;
  111.         REP (t, n)
  112.         {
  113.             int j = tp[t]; f[i][j] = bSum (n - j);
  114.             if (a[tp[t]] != a[tp[t + 1]]) {FOR (k, last + 1, t) bAdd (n - tp[k] + 1, f[i - 1][tp[k]]); last = t;}
  115.         }
  116.     }
  117.     free (bi);
  118. }
  119. int main ()
  120. {
  121.     scanf ("%d%d%d", &n, &L, &q0), a[0] = -inf;
  122.     REP (i, n) scanf ("%d", &a[i]), tp[i] = i;
  123.     sort (tp + 1, tp + n + 1, cmpP);
  124.     iQ = (ll*) malloc ((q0 + 2) * sizeof (ll));
  125.     REP (i, q0) scanf ("%lld", &iQ[i]);
  126.     init (), solve (L);
  127.     REP (i, q0)
  128.     {
  129.         if (ans[i][0] == -1) {puts ("-1"); continue;}
  130.         REP_0 (j, L) printf ("%d ", ans[i][j]); puts ("");
  131.     }
  132.     return 0;
  133. }

PA2011 bwp

n≠m就补满。

考虑一开始都是边(i,i)。

那么对于任意一个环要求有匹配中边权值和=非匹配边中权值和。

于是对于边(i,j)权值为wi,j−wi,i。
要求此图中所有环权值为0。
则显然1号点到一个点的距离是唯一的。
线段树判定。

  1. # include <cstdio>
  2. # include <algorithm>
  3. # include <vector>
  4. using namespace std;
  5. # define REP(i, n) for (int i = 1; i <= n; ++ i)
  6. # define REP_G(i, x) for (int i = pos[x]; i; i = g[i].frt)
  7. # define NR 101000
  8. # define ER 301000
  9. const int inf = 1 << 30;
  10. struct Edge {int l, r, w, frt; void set (int _l, int _r, int _w, int fr) {l = _l, r = _r, w = _w, frt = fr;}} g[ER * 2];
  11. struct Seg {int lc, rc, cov;} t[NR * 4];
  12. int pos[NR], dt[NR], z[NR], q[NR], n, m, K, tsz, gsz, head, tail, q0;
  13. vector <pair <int, int> > seq[NR];
  14. inline void AE (int x, int l, int r, int w) {g[++ gsz].set (l, r, w, pos[x]), pos[x] = gsz;}
  15. # define u t[x]
  16. int build (int l, int r)
  17. {
  18.     int x = ++ tsz;
  19.     if (l == r) return (l == 1 ? u.cov = dt[1] = 0 : u.cov = dt[l] = inf), x;
  20.     int mid = (l + r) >> 1; return u.lc = build (l, mid), u.rc = build (mid + 1, r), u.cov = inf, x;
  21. }
  22. bool segCov (int x, int l, int r, int cl, int cr, int w)
  23. { 
  24.     int mid = (l + r) >> 1;
  25.     if (cl <= l && r <= cr)
  26.     {
  27.         if (u.cov != inf && u.cov != w) return false;
  28.         if (u.cov != inf) return true;
  29.         u.cov = w;
  30.         if (l == r) return dt[q[++ tail] = l] = w, true;
  31.         if (!segCov (u.lc, l, mid, cl, cr, w)) return false;
  32.         return segCov (u.rc, mid + 1, r, cl, cr, w);
  33.     }
  34.     if (cl <= mid) if (!segCov (u.lc, l, mid, cl, cr, w)) return false;
  35.     if (cr > mid) return segCov (u.rc, mid + 1, r, cl, cr, w);
  36.     return true;
  37. }
  38. bool spfa ()
  39. {
  40.     int ro = build (1, n), x, d; q[head = tail = 1] = 1;
  41.     while (head <= tail) {x = q[head ++]; REP_G (i, x) if (!segCov (ro, 1, n, g[i].l, g[i].r, dt[x] + g[i].w)) return false;}
  42.     return true;
  43. }
  44. int main ()
  45. {
  46.     for (scanf ("%d", &q0); q0; -- q0)
  47.     {
  48.         scanf ("%d%d%d", &n, &m, &K);
  49.         int ta, tb, tc, tw;
  50.         n = m = max (n, m), tsz = gsz = 0;
  51.         REP (i, n) pos[i] = z[i] = 0, seq[i].clear ();
  52.         REP (i, K) 
  53.         {
  54.             scanf ("%d%d%d%d", &ta, &tb, &tc, &tw), AE (ta, tb, tc, tw), seq[ta].push_back (make_pair (tb, tc));
  55.             if (tb <= ta && ta <= tc) z[ta] = tw;
  56.         }
  57.         REP (x, n) 
  58.         {
  59.             sort (seq[x].begin (), seq[x].end ());
  60.             int lst = 0;
  61.             for (vector <pair <int, int> >::iterator it = seq[x].begin (); it != seq[x].end (); ++ it)
  62.             {
  63.                 if (lst + 1 != it->first) AE (x, lst + 1, it->first - 1, 0);
  64.                 lst = it->second;
  65.             }
  66.             if (lst != n) AE (x, lst + 1, n, 0);
  67.             REP_G (i, x) g[i].w -= z[x];
  68.         }
  69.         puts (spfa () ? "TAK" : "NIE");
  70.     }
  71.     return 0;
  72. }

PA2011 aut

波兰人连树Hash都卡……太可怕了……
显然选重心做根DP一遍就好了。

  1. # include <cstdio>
  2. # include <algorithm>
  3. # include <vector>
  4. # include <cassert>
  5. # include <iostream>
  6. using namespace std;
  7. # define REP(i, n) for (int i = 1; i <= n; ++ i)
  8. # define REP_G(i, x) for (int i = pos[x]; i; i = g[i].frt)
  9. # define NR 501000
  10. # define seed 1214
  11. # define P 1000000000007ll
  12. # define MOD 1000000007
  13. template <class T0, class T1> inline bool RlxX (T0 &x, T1 y) {if (x < y) return x = y, true; return false;}
  14. typedef long long ll;
  15. struct Edge {int y, frt; void set (int yr, int fr) {y = yr, frt = fr;}} g[NR << 1];
  16. int pos[NR], gsz, n, sz[NR], len, ro[NR], rl;
  17. int root_ta; 
  18. ll hashw[NR], li[NR];
  19. vector <ll> hw[NR];
  20. void AE (int x, int y) {g[++ gsz].set (y, pos[x]), pos[x] = gsz;}
  21. # define v g[i].y
  22. bool cmp (ll a, ll b) {return a > b;}
  23. ll Hash (int x, int fa)
  24. {
  25.     hw[x].clear (), sz[x] = 1;
  26.     REP_G (i, x) if (v != fa) hw[x].push_back (Hash (v, x)), sz[x] += sz[v];
  27.     hashw[x] = 1 + hw[x].size () + sz[x];
  28.     sort (hw[x].begin (), hw[x].end (), cmp); int d = 0;
  29.     for (vector <ll>::iterator it = hw[x].begin (); it != hw[x].end (); ++ it)
  30.         hashw[x] = (hashw[x] * seed + *it) % P;
  31.     return hashw[x];
  32. }
  33. void Centre (int x, int fa)
  34. {
  35.     sz[x] = 1; int ms = 0;
  36.     REP_G (i, x) if (v != fa) Centre (v, x), RlxX (ms, sz[v]), sz[x] += sz[v];
  37.     RlxX (ms, n - sz[x]);
  38.     if (2 * ms <= n) ro[++ rl] = x;
  39. }
  40. bool eqlr;
  41. int getCentre (int x)
  42. {
  43.     rl = 0, eqlr = false;
  44.     Centre (x, 0);
  45.     if (rl == 1) return ro[1];
  46.     ll h0 = Hash (ro[1], 0), h1 = Hash (ro[2], 0);
  47.     if (h0 == h1) eqlr = true;
  48.     return h0 <= h1 ? ro[1] : ro[2];
  49. }
  50. int dfs (int x, int fa)
  51. {
  52.     if (eqlr && x == ro[2]) return 1;
  53.     int res = 1;
  54.     REP_G (i, x) if (v != fa) res = 1ll * res * dfs (v, x) % MOD;
  55.     len = 0;
  56.     REP_G (i, x) if (v != fa) li[++ len] = hashw[v];
  57.     sort (li + 1, li + len + 1);
  58.     int cur = 0;
  59.     li[0] = -1;
  60.     REP (i, len)
  61.     {
  62.         if (li[i] != li[i - 1]) cur = 0;
  63.         ++ cur;
  64.         res = 1ll * res * cur % MOD;
  65.     }
  66.     return res;
  67. }
  68. int main ()
  69. {
  70.     scanf ("%d", &n); int t1, t2;
  71.     REP (i, n - 1) scanf ("%d%d", &t1, &t2), AE (t1, t2), AE (t2, t1);
  72.     int root = getCentre (1);
  73.     Hash (root, 0);
  74.     int res = dfs (root, 0);
  75.     printf ("%d\n", eqlr ? int (2ll * res * res % MOD) : res);
  76.     return 0;
  77. }

PA2011 kan

考虑两个区间[l,r]与[ml,mr]相交当且仅当ml≤r且mr≥l。
化到二维平面上以后，把区间序列中的区间按编号顺序插进去。
用二维线段树必死无疑……后来写了kd-Tree。
然而依然费了半天劲才过……

  1. # include <cstdio>
  2. # include <algorithm>
  3. using namespace std;
  4. const int inf = 1 << 30;
  5. # define REP(i, n) for (int i = 1; i <= n; ++ i)
  6. # define FOR(i, a, b) for (int i = a; i <= b; ++ i)
  7. # define MR 201000
  8. # define NR 50100
  9. inline void RlxX (int &x, int y) {if (x < y) x = y;}
  10. inline void RlxN (int &x, int y) {if (x > y) x = y;}
  11. struct Poi {int x, y, id;} p[MR];
  12. struct Info
  13. {
  14.     int cur, ans, last; bool bk;
  15.     inline void cover () {if (!bk) last = cur, bk = true; RlxX (ans, cur); cur = 0;}
  16.     inline void apply (const Info &t)
  17.     {
  18.         if (t.bk) 
  19.         {
  20.             if (!bk) last = cur + t.last, bk = true;
  21.             RlxX (ans, cur + t.last), cur = t.cur;
  22.         }
  23.         else cur += t.cur;
  24.     }
  25. };
  26. struct Kd {int xl, xr, yl, yr, lc, rc; Info w;} t[MR];
  27. Info fin[MR];
  28. int mx[NR], my[NR], n, m, ans[MR];
  29. inline bool cmpX (Poi a, Poi b) {if (a.x != b.x) return a.x < b.x; if (a.y != b.y) return a.y < b.y; return a.id < b.id;}
  30. inline bool cmpY (Poi a, Poi b) {if (a.y != b.y) return a.y < b.y; if (a.x != b.x) return a.x < b.x; return a.id < b.id;}
  31. # define u t[x]
  32. # define ulfc t[u.lc]
  33. # define urtc t[u.rc]
  34. inline void apply (int x, const Info &z) {u.w.apply (z), fin[x].apply (z);}
  35. void push (int x)
  36. {
  37.     if (!u.w.cur && !u.w.bk) return ;
  38.     apply (u.lc, u.w), apply (u.rc, u.w), u.w.cur = u.w.bk = 0;
  39. }
  40. int build (int l, int r, bool d)
  41. {
  42.     if (l > r) return 0;
  43.     int x = (l + r) >> 1; u.xl = u.yl = inf, u.xr = u.yr = -inf;
  44.     FOR (i, l, r) RlxN (u.xl, p[i].x), RlxX (u.xr, p[i].x), RlxN (u.yl, p[i].y), RlxX (u.yr, p[i].y);
  45.     nth_element (p + l, p + x, p + r + 1, (u.xr - u.xl >= u.yr - u.yl) ? cmpX : cmpY);
  46.     return u.lc = build (l, x - 1, !d), u.rc = build (x + 1, r, !d), x;
  47. }
  48. int xl, xr, yl, yr;
  49. void modify (int x)
  50. {
  51.     if (!x) return ;
  52.     if (xr < u.xl || xl > u.xr || yr < u.yl || yl > u.yr) {u.w.cover (), fin[x].cover (); return ;}
  53.     if (xl <= u.xl && u.xr <= xr && yl <= u.yl && u.yr <= yr) {++ u.w.cur, ++ fin[x].cur; return ;}
  54.     if (xl <= p[x].x && p[x].x <= xr && yl <= p[x].y && p[x].y <= yr) ++ fin[x].cur;
  55.     else fin[x].cover ();
  56.     push (x), modify (u.lc), modify (u.rc);
  57. }
  58. void pushAll (int x, int w) {if (!x) return ; RlxX (w, u.w.ans), RlxX (fin[x].ans, w), push (x), pushAll (u.lc, w), pushAll (u.rc, w);}
  59. int main ()
  60. {
  61.     scanf ("%d%d", &n, &m);
  62.     REP (i, n) scanf ("%d%d", &mx[i], &my[i]);
  63.     REP (i, m) scanf ("%d%d", &p[i].x, &p[i].y), p[i].id = i;
  64.     int root = build (1, m, 0); xl = 0, yr = inf;
  65.     REP (i, n) xr = my[i], yl = mx[i], modify (root);
  66.     pushAll (root, 0);
  67.     REP (i, m) ans[p[i].id] = max (fin[i].cur, fin[i].ans);
  68.     REP (i, m) printf ("%d\n", ans[i]);
  69.     return 0;
  70. }

PA2011 pie

卡常数是你姿势不对（逃……
二分答案，枚举指数，求k次方根，
然后就转化为求[l,r]中有多少素数。
记得对2特殊处理。

  1. # include <cstdio>
  2. # include <cmath>
  3. # include <iostream>
  4. using namespace std;
  5. # define REP(i, n) for (int i = 1; i <= n; ++ i)
  6. # define FOR(i, a, b) for (int i = a; i <= b; ++ i)
  7. typedef long long ll;
  8. typedef long double ld;
  9. # define B 1100000
  10. ll n, W;
  11. int cnt2[6010000], prc[B + 10], pl[B + 10], psz, hL[100];
  12. int vL, vR, K;
  13. int hypt (ll a, int K)
  14. {
  15.     if (a < 1ll << K) return 1;
  16.     ll l = 3, r = (ll) sqrt ((ld) a), mid, p;
  17.     for (; l < r;)
  18.     {
  19.         mid = (l + r) >> 1, p = 1; bool over = false;
  20.         REP (i, K)
  21.         {
  22.             if (p > a / mid) {over = true; break;}
  23.             p *= mid;
  24.         }
  25.         if (p == a && !over) return mid + 1;
  26.         (p > a || over) ? r = mid : l = mid + 1;
  27.     }
  28.     return l - 1;
  29. }
  30. void init ()
  31. {
  32.     FOR (i, 2, B)
  33.     {
  34.         if (!prc[i]) pl[++ psz] = i;
  35.         for (int j = 1; j <= psz && i * pl[j] <= B; ++ j)
  36.         {
  37.             prc[i * pl[j]] = 1;
  38.             if (i % pl[j] == 0) break;
  39.         }
  40.     }
  41.     FOR (i, 2, B) prc[i] = prc[i - 1] + !prc[i];
  42.     if (n <= 100) W = 2000000000000ll;
  43.     else if (K <= 10) W = (ll) (300ll * K * (sqrt ((ld) n) + K + 5));
  44.     else W = (ll) (60ll * K * (sqrt ((ld) n) + K + 5));
  45.     vL = (int) ceil (sqrt ((ld) n)), vR = (int) sqrt ((ld) (n + W));
  46.     int t = (int) sqrt (vR);
  47.     REP (i, t)
  48.         if (prc[i] - prc[i - 1])
  49.         {
  50.             int tL = max ((vL + i - 1) / i, 2), tR = vR / i;
  51.             FOR (j, tL, tR) cnt2[i * j - vL + 1] = 1;
  52.         }
  53.     FOR (i, vL, vR) cnt2[i - vL + 1] = cnt2[i - vL] + (!cnt2[i - vL + 1] && i > 1);
  54.     FOR (p, 3, 61) if (prc[p] - prc[p - 1]) hL[p] = hypt (n, p);
  55. }
  56. bool check (ll t)
  57. {
  58.     ll res = cnt2[(int) sqrt ((ld) (n + t)) - vL + 1] - cnt2[(int) sqrt ((ld) n) - vL + 1];
  59.     FOR (p, 3, 61) if (prc[p] - prc[p - 1]) res += prc[hypt (n + t, p)] - prc[hL[p]];
  60.     return res >= K;
  61. }
  62. int main ()
  63. {
  64.     scanf ("%lld%d", &n, &K);
  65.     init ();
  66.     ll l = 0, r = W, mid;
  67.     for (; l < r;) mid = (l + r) >> 1, check (mid) ? r = mid : l = mid + 1;
  68.     printf ("%lld\n", n + l);
  69.     return 0;
  70. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注