QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: xcx0902

Posted at: 2026-04-23 14:30:13

Last updated: 2026-04-23 14:30:54

Back to Problem

New Editorial for Problem #11554

如果 $\gcd(p,q)$ 不整除 $n$,那么显然无解。

下面讨论有解的情况:

  1. $p=q$:显然先手必胜。
  2. $p\gt q \land n\lt p$:先手第一次数量加 $p$,后手可以把数量变成 $n\bmod q$,这样先手永远无法取石子,后手必胜。
  3. $p\gt q \land n\ge p$:如果先手第一次取完石子,石子数量大于 $p$,后手还是可以把数量变成 $n\bmod q$,后手必胜;否则,先手取成 $n \bmod p$,后手 $+q$,先手 $\bmod p$,后手 $+q$,一直循环下去,直到先手取成 $0$(先手胜),或者先手只能 $+p$(后手胜)。这等价于:如果 $n\bmod (p-q)=0$,则先手必胜。
  4. $p\lt q \land n\lt p$:先手变成 $n+p$,如果 $n+p\lt q$,就变成了第二种情况,否则是第三种情况。
  5. $p\lt q \land n\ge p$:先手变成 $n\bmod p$,就变成了第二种情况。

Comments

No comments yet.