自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:39:59，当前版本为作者最后更新于2022-09-11 00:37:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}