😺

ABC161 F - Division or Subtraction

2021/01/27に公開約600字

解法

まず重要な点として、NKで割り切れないときに、N-KKで割り切れるということはありえない
NKで割り切れるということはgcd(N, K) = Kになるが
gcd(N, K) = gcd(N-K, K)であり、
N-KKの最大公約数は操作前の値と等しくなる
よって、操作としては

  1. Kで割り切れるだけ割る
  2. Kで引けるだけ引く

という流れになる
2は結局mod Kをとることに等しい

以上を踏まえて以下の2つのパターンが考えられる

1. KがNで割り切れるとき

このときはNをKで割れるだけ割る。割った値をN'とすると
N' \mod K \equiv 1となればよい
Nを割り切るKというのはNの約数なので、Nの約数を列挙して(1は除く)、以上をシミュレーションすればよい

2. KがNで割り切れないとき

N \mod K \equiv 1となればよい
こうなるようなKの数を数えたい
元の式を式変形すると
N - 1 \mod K \equiv 0
N-1Kで割り切れる、つまりKN-1の約数となる
N-1の約数の個数-1が答えになる

1と2で重複して数えられるものがないか気になるが、
NN-1は互いに素なので、公約数は1しか存在せず、問題にならない

提出コード

https://atcoder.jp/contests/abc161/submissions/19722162

Discussion

ログインするとコメントできます