猜分数
Question
假设有一对关系很好的情侣 LXX 和 LKK
一开始女方 LXX 的手上有一个分数：\(\frac{p}{q}\)，其中 \(p、q\) 都是正整数，且互质，即 \(gcd(p, q) = 1\)。
LXX 并不打算告诉对象 LKK 手上的分数是什么，但是允许 LKK 猜测一个分数 \(\frac{x}{y}\)，其中 \(x、y\) 都是正整数，且 \(gcd(x, y) = 1\)。
为了增进彼此之间的感情，LXX 会及时的反馈一些有用的信息给 LKK 让他猜！
例如:
- 如果 \(\frac{x}{y} < \frac{p}{q}\) 时，
LXX会举起一张牌<代表「小了」； - 如果 \(\frac{x}{y} > \frac{p}{q}\) 时，
LXX会举起一张牌>代表 「大了」； - 如果 \(\frac{x}{y} = \frac{p}{q}\)，
LXX会举起一张牌=代表答对了！
为了不使得对象 LKK 耍无赖，从最小值一个一个枚举，这样太费时间了，LXX 要求只能最多问 20 次。
数据范围：
\(1 \leq x, y, p, q \leq 1000\)
询问方式：
compare x y
回答：
>、=、< 中的一种。
gcd(n, m) 的时间复杂的是 \(O(log(n))\)
对待该数据范围，完全可以使用暴力 \(n^2\) 寻找出 \(1 \sim 1000\) 内所有的 \(<x, y>\)，然后对其组成的分数 \(\frac{x}{y}\) 从小到大排序，然后采后二分查找来做。
Code
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define endl '\n'
#define pique priority_queue
#define oier \
ios_base::sync_with_stdio(false);\
cin.tie(nullptr); cout.tie(nullptr);
#define cf int t; cin >> t; while (t --)
#define upfor(i, l, r) for (i = (l); i <= (r); i ++)
#define downfor(i, l, r) for (i = (r); i >= (l); i --)
// #define int long long
typedef long long LL;
typedef long double LD;
//typedef __int128_t int128;
const int inf = ~(1 << 31); // 正无穷
const int ninf = (1 << 31); // 负无穷
const LL infll = ~(1ll << 63); // 正无穷
const LL ninfll = (1ll << 63); // 负无穷
inline LL rll() { oier LL x; cin >> x; return x; }
inline int rint() { oier int x; cin >> x; return x; }
const int N = int (1e7 + 10);
// 由于情报不足，只能透过「试行错误」来获取。
/* =============================代码区============================= */
int x[N], y[N], n;
double f[N];
void cge(int i, int j)
{
swap(f[i], f[j]); swap(x[i], x[j]); swap(y[i], y[j]);
}
void qsort(int l, int r)
{
if (l >= r) return;
double x = f[(l + r) >> 1];
int i = l - 1, j = r + 1;
while (i < j)
{
while (f[++i] < x);
while (x < f[--j]);
if (i < j) cge(i, j);
}
qsort(l, j); qsort(j + 1, r);
}
int gcd(int a, int b)
{
if (!a || !b) return a | b;
else return a >= b ? gcd(b, a % b) : gcd(a, b % a);
}
void init(int M = 1000)
{
for (int i = 1; i <= M; i ++)
{
for (int j = 1; j <= M; j ++)
{
if (gcd(i, j) == 1)
{
n ++; f[n] = i * 1.0 / j; x[n] = i; y[n] = j;
}
}
}
qsort(1, n);
}
void solve()
{ oier
/* =========================== */
srand((unsigned)time(NULL));
int t = (rand() % 10000) + 1; // 随机测试 1 ~ 10000 次
init();
while (t --)
{
int pos = (rand() % n) + 1; // 获取 1 ~ n 的随机下标
int l = 1, r = n, mid;
int times = 0, success = 0;
while (++times <= 20)
{
mid = (l + r) / 2;
if (mid < pos) l = mid + 1;
else if (mid > pos) r = mid - 1;
else { success = 1; break; }
}
if (success) cout << "code right: LXX's (p, q) = (" << x[pos] << ", " << y[pos] << "), and LKK's answer is (x, y) = (" << x[mid] << ", " << y[mid] << ")\n";
else cout << "code error! times over 20\n";
}
/* =========================== */
}
/* =============================代码区============================= */
/**
* _ooOoo_
* o8888888o
* 88" . "88
* (| -_- |)
* O\ = /O
* ____/`---'\____
* .' \\| |// `.
* / \\||| : |||// \
* / _||||| -:- |||||- \
* | | \\\ - /// | |
* | \_| ''\---/'' | |
* \ .-\__ `-` ___/-. /
* ___`. .' /--.--\ `. . __
* ."" '< `.___\_<|>_/___.' >'"".
* | | : `- \`.;`\ _ /`;.`/ - ` : | |
* \ \ `-. \_ __\ /__ _/ .-` / /
* ======`-.____`-.___\_____/___.-`____.-'======
* `=---='
* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
* 佛祖保佑 永无BUG
* 佛曰:
* 写字楼里写字间，写字间里程序员；
* 程序人员写程序，又拿程序换酒钱。
* 酒醒只在网上坐，酒醉还来网下眠；
* 酒醉酒醒日复日，网上网下年复年。
* 但愿老死电脑间，不愿鞠躬老板前；
* 奔驰宝马贵者趣，公交自行程序员。
* 别人笑我忒疯癫，我笑自己命太贱；
* 不见满街漂亮妹，哪个归得程序员？
**/
/* ========================佛祖保佑, 永无bug======================== */
int main()
{
// oier cf solve(); return 0;
oier solve(); return 0;
}