Baby Stepsなブログ

競プロとか。間違ったこと書いてあったら@pi0nep1oneにご連絡ください。

ABC 186 E - Throne

過去問埋め 解説 競技プログラミング AtCoder

一次合同式についての教育的な良問だったので、考えたことを書き残しておく。

問題

atcoder.jp

考えたこと

この問題は言い換えると、初期値がsの状態からkを何度か足すことで、nの倍数を作れるか、という問題になる。

つまり、(kx+s)%n==0となる最小のxを求める問題（解が存在しない場合も有り得る）であり、この式を更に変形すると、kx+s≡0 (mod n) => k*x≡-s (mod n) という一次合同式を解く問題に帰着できる。

一次合同式 a*x≡b (mod m) の解を求める手順は以下の通り。

  1. 整数 a, b, mの最大公約数gを求めて、gでそれぞれの値を割った値に置き換える
    • これはただの前処理で、gで割る前と後の合同式は同値
  2. 次に、a, mが互いに素であるかを確認するためにa, mの最大公約数を求める
    • このとき、その最大公約数が1でないなら、解は存在しない（これは乗法逆元が定まらないため）
  3. 解が存在するなら、mod mにおけるaの乗法逆元a'とすると、その解は、a'*bとなる

注意点

逆元が存在する条件

ここに丁寧に記されている通り、乗法逆元の存在する条件は、aとmが互いに素であること。

以下の2点は正であるのに誤解しがちなところので注意する。

  • mは素数である必要はない
  • mが素数であっても、a==mなら逆元は定まらない

上記を踏まえると逆元が存在する場合には、与えられるa, b, mによってはaとmが互いに素ではあるが、mは素数ではないという場合が有り得る。

さらに整理すると、合成数である可能性もあるMが与えられ解として計算結果のmod Mを求めよという問題で計算結果がWAとなるのは、計算過程に除法があるならばmod Mの乗法逆元を求める必要があり、割る数とMが互いに素でない場合（フェルマーの小定理等では）その逆元を正しく求められないからである。

この問題もその一例で、(m-2)乗で逆元が求まらない場合がある。結局この場合の求め方がわからなかったので、以下の解答コードではACLのmodintを使いお茶を濁している。（誰か教えてください）

解答コード

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;

int solve(int a, int b, int m) {
  int g = gcd(gcd(a, b), m);
  a /= g, b /= g, m /= g;
  if (gcd(a, m) != 1)
    return -1;
  modint::set_mod(m);
  modint ma = a;
  modint mb = b;
  return (mb * ma.inv()).val();
}

signed main() {
  int t;
  cin >> t;
  while (t--) {
    int n, s, k;
    cin >> n >> s >> k;
    cout << solve(k, -s, n) << endl;
  }
}

個人的なメモ

  • gcdと__gcdの挙動は異なる

※この問題で__gcdを使って実装するとバグります。（__gcdはパラメータに負数を含む場合に結果が負数になる可能性があるため）

結論gcdを使う。

  • ACL modintを呼ぶ前にmodint::set_modを呼ぶのを忘れない

参考

合成数の可能性があるMが与えられて、計算結果にmod Mを求める必要があり、かつ、計算過程に逆元を求める必要がある問題

atcoder.jp