P8541 「Wdoi-2」死亡之后愈发愉悦

· · 题解

P8541 「Wdoi-2」死亡之后愈发愉悦

二分未知上界的数的最好方式是倍增。

考察两个相邻的完全平方数 i ^ 2 和 (i + 1) ^ 2 之间 [i ^ 2, (i + 1) ^ 2) 可爱数的分布，发现为 i + 1 个可爱数和 i 个非可爱数。

设 j(x) 表示 x 是否为可爱数。

因此，考虑倍增求出使得 j(a) \sim j(a + p) 全部相同的最大的 p，再倍增求出使得 f(a + p + 1)\sim f(a + p + q) 全部相同的最大的 q，则根据 q 和 j(a) 容易求得 a。

倍增方法：依次尝试以 1, 1, 2, 4, \cdots, 2 ^ k, 2 ^ {k - 1}, \cdots, 1 为步长 d 向后跳，检查 j(a + d) 是否等于 j(a)。若 j(a) = j(a + d)，则令 a\gets a + d，称为成功，否则不变，称为失败。其中 2 ^ k 是第一次失败的步长。一开始多一个 1 是为了保证 除第一次跳跃以外，其它每一次跳跃的步长不大于已经跳过的长度，结合可爱数的分布，这保证了不会在 j(a) = j(a + d) 之间出现 j(a + i)\neq j(a) (0 < i < d)。实际上若可爱数分布为 i 个可爱数接着 i 个非可爱数，也即极长连续相等段长度不降，则没有必要在第二次跳 1，而是直接跳 2，读者可对比两种情况自行思考。

询问次数为 4\log\sqrt a 即 2\log a，无法接受。

实际上我们发现 p \leq q，所以倍增求 q 时，可以直接从 2 ^ k 为步长开始，其中 2 ^ k \leq p。这样询问次数即可做到 3\log \sqrt a，可以接受。

代码和题解有一些细节上的差异。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;
inline ll read() {
  ll x = 0, sgn = 0;
  char s = getchar();
  while(!isdigit(s)) sgn |= s == '-', s = getchar();
  while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return sgn ? -x : x;
}
inline void print(int x) {
  if(x < 0) return putchar('-'), print(-x);
  if(x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
bool Mbe;
map<int, bool> mp;
int query(int x) {
  if(mp.find(x) != mp.end()) return mp[x];
  cout << "? " << x << endl;
  int res = read();
  return mp[x] = res;
}
int suc(int x, int acc) {
  int st = query(x);
  if(query(x + 1) != st) return x;
  int pw = 0;
  while((1 << pw + 1) <= acc) pw++;
  while(1) {
    if(query(x + acc + (1 << pw)) != st) break;
    acc += 1 << pw, pw++;
  }
  for(int i = pw - 1; ~i; i--)
    if(query(x + acc + (1 << i)) == st)
      acc += 1 << i;
  return x + acc;
}
bool Med;
signed main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  // #ifdef ALEX_WEI
  //   FILE* IN = freopen("1.in", "r", stdin);
  //   FILE* OUT = freopen("1.out", "w", stdout);
  // #endif
  int T;
  cin >> T;
  while(T--) {
    mp.clear();
    int p = suc(0, 1);
    int q = suc(p + 1, max(1ll, p - 1)) - p;
    if(!query(0)) cout << "! " << (q - 1) * (q - 1) - 1 - p << endl;
    else cout << "! " << q * (q + 1) - p << endl;
  }
  cerr << TIME << " ms\n";
  return 0;
}