# ZeroJudge - g541: 類題:兔子跳躍(TOIP) ### 題目連結:https://zerojudge.tw/ShowProblem?problemid=g541 ###### tags: `ZeroJudge` `數學` `數論` ```cpp= #include <iostream> using namespace std; static const auto Initialize = [] { cin.sync_with_stdio(false); cin.tie(nullptr); return nullptr; }(); int gcd; long long amount1, amount2; void ExtendedEuclid(int a, int b) { bool flag = false; long long left1 = 1, left2 = 0, right1 = 0, right2 = 1, buffer; while (b) { if (!flag) { left1 -= a / b * right1; left2 -= a / b * right2; } else { right1 -= a / b * left1; right2 -= a / b * left2; } flag = !flag; buffer = a % b; a = b; b = buffer; } gcd = a; if (!flag) { amount1 = left1; amount2 = left2; } else { amount1 = right1; amount2 = right2; } } bool IfFeasible(int step1, int step2, int target) { long long needs1, needs2, slope1, slope2, buffer; if (target % gcd) return false; target /= gcd; slope1 = step2 / gcd; slope2 = step1 / gcd; needs1 = amount1 * target; needs2 = amount2 * target; if (needs1 < 0) { buffer = -(needs1 / slope1) + (needs1 % slope1 != 0); needs1 += buffer * slope1; needs2 -= buffer * slope2; } else if (needs2 < 0) { buffer = -(needs2 / slope2) + (needs2 % slope2 != 0); needs1 -= buffer * slope1; needs2 += buffer * slope2; } return needs1 >= 0 && needs2 >= 0; } int main() { int step1, step2, queries, position; while (cin >> step1 >> step2 >> queries) { ExtendedEuclid(step1, step2); while (queries--) { cin >> position; cout << (IfFeasible(step1, step2, position) ? "YES\n" : "NO\n"); } } } ```