威佐夫博弈扩展（HDU-6869 Slime and Stones）

威佐夫博弈扩展 第i个奇异局面为： $$a[i]=\lfloor \frac{1-k-\sqrt{k^2+2k+5}}{2}i\rfloor$$ $$b[i]=\lfloor \frac{3+k+\sqrt{k^2+2k+5}}{2}i\rfloor$$ 当k=0时，即为威佐夫博弈的结论。 做差即可验证： $$b[i]-a[i]=\lfloor (k+1)i\rfloor$$ $$i=\lfloor \frac{b[i]-a[i]}{(k+1)}\rfloor$$

#include<cstdio> #include<iostream> #include<cstring> #include <map> #include <queue> #include <set> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <list> #include <bitset> #include <array> #include <cctype> #include <time.h> #pragma GCC optimize(2) void read_f() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); } void fast_cin() { std::ios::sync_with_stdio(false); std::cin.tie(); } void run_time() { std::cout << "ESC in : " << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << std::endl; } template <typename T> bool bacmp(const T & a, const T & b) { return a > b; } template <typename T> bool pecmp(const T & a, const T & b) { return a < b; } #define ll long long #define ull unsigned ll #define _min(x, y) ((x)>(y)?(y):(x)) #define _max(x, y) ((x)>(y)?(x):(y)) #define max3(x, y, z) ( max( (x), max( (y), (z) ) ) ) #define min3(x, y, z) ( min( (x), min( (y), (z) ) ) ) #define pr(x, y) (make_pair((x), (y))) #define pb(x) push_back(x); using namespace std; const int N = 1e5 + 5; double f1(double k) { return (sqrt(k*k+2*k+5.0) + 1 - k) / 2.0; } double f2(double k) { return (sqrt(k*k+2*k+5) + 3 + k) / 2.0; } int main() { int t; cin >> t; while(t--) { int a, b, k; scanf("%d%d%d", &a, &b, &k); if (a > b) swap(a, b); double k1 = f1(k); double k2 = f2(k); int d = (b - a) / (k + 1); if ((int)(d * k1) == a && (int)(d * k2) == b) puts("0"); else puts("1"); } }