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.

题意概述

给定$x_1, x_2, P, K$,求一组非负整数$(P_1, N_1, P_2, N_2)$满足:
$$
\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.
$$
数据范围:$0 \lt x_1, x_2 \lt 40000, \; -40000 \lt P \lt 40000, \; 0 \le K \lt 2 \times 10^9$。

算法分析

设$g=(x_1, x_2)$,如果$g \not \mid P$则无解,否则可以将$x_1, x_2, P$同时除以$g$,对答案没有影响。
设$a=P_1-N_1, \; b=P_2-N_2$,则$ax_1+bx_2=P$,可用扩展GCD求出它的一组解。若$(a, b)$是一组解,则$(a+kx_2, b-kx_1)$也是一组解。只要在$\pm P$的范围内枚举$k$,判断是否存在$(P_1, N_1, P_2, N_2)$满足第二个方程即可。

代码

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

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *