Jumping Joe

题目描述

Joe is a frog who likes to jump a lot. In fact, that’s all he does: he jumps forwards and backwards on the integer axis (a straight line on which all the integer numbers, both positive and negative are marked). At first, Joe sits next to the point marked with $0$. From here, he can jump in the positive or the negative direction a distance equal to either $x_1$ or $x_2$. From the point where he arrived, he can jump again a distance equal to $x_1$ or $x_2$, in the positive or the negative direction and so on.. Joe wants to arrive next to the point marked with the number $P$, after exactly $K$ jumps. You have to decide whether such a thing is possible.

题意概述

\left\{ \begin{align} P_1x_1-N_1x_1+P_2x_2-N_2x_2&=P \\ P_1+N_1+P_2+N_2&=K \end{align} \right.

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
int x1, x2, p, k;
void input() { io > x1 > x2 > p > k; }
int ex_gcd(int a, int b, int &x, int &y) {
if (! b) { x = 1, y = 0; return a; }
int ret = ex_gcd(b, a % b, y, x); y -= a / b * x; return ret;
}
bool check(int x, int y) {
if (abs(x) + abs(y) > k) return false;
if (k - abs(x) - abs(y) & 1) return false;
io < (char *) "YES\n";
int t = k - abs(x) - abs(y) >> 1;
if (x > 0) io < x + t < ' ' < t < ' ';
else io < t < ' ' < -x + t < ' ';
if (y > 0) io < y < ' ' < 0 < '\n';
else io < 0 < ' ' < -y < '\n';
return true;
}
void process() {
int x, y, gcd = ex_gcd(x1, x2, x, y);
if (p % gcd) io < (char *) "NO\n";
else {
x1 /= gcd, x2 /= gcd, p /= gcd, x *= p, y *= p;
for (int i = -abs(p) - 1; i <= abs(p) + 1; ++ i)
if (check(x + x2 * i, y - x1 * i)) goto label;
io < (char *) "NO\n";
label: ;
}
}

public:
void solve() { input(), process(); }
} solver;

signed main() {
solver.solve();
return 0;
}

418 I'm a teapot