C - K-th Not Divisible by n (Codeforces Round #640 Div. 4)

やっと通った、けど・・・

問題

https://codeforces.com/contest/1352/problem/C

問題概要

整数nとkが与えられる。正の整数でnで割り切れないもののうち、k番目に大きいものを答えよ。

自分の考察（コンテスト中）

隣り合うnの倍数とnの倍数の間には整数がn-1個あります。なのでk / (n - 1)が、求めるk番目の整数より小さいnの倍数の個数で、求めるk番目の整数はn * (k / (n - 1)) + (k - (k / (n - 1)) * (n - 1)となる、と思ったのですが、微妙に合わなかったのです。

とりあえず通しました

なんで合わないかというと、kがn - 1の倍数の時、k / (n - 1)は本来求めるべき値より1大きくなるからです。例えばnが3, kが8のときk / (n - 1) = 8 / (3 - 1) = 4となりますが、実際は1 2 _ 4 5 _ 7 8 _ 10 11 という具合で、答えである11の前にnの倍数は3つしかないのです。ずれてます・・・。

というわけで、このケースを場合分けして通した自分のコードがこちらです。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n, k;
        cin >> n >> k;
        long long m = k / (n - 1);
        if (k % (n - 1) == 0) cout << n * m - 1 << endl;
        else cout << n * m + (k - m * (n - 1)) << endl;
    }
}

想定解

Editorialによれば、kから1ひいたものを割ればよいとのこと。言われてみればそれはそう、ですね・・・。

反省

こういうときはおちついて、具体例をいくつか作って考えましょう。