循環小数N桁目 Hard [yukicoder No.747]

https://yukicoder.me/problems/no/747

解説

https://yukicoder.me/submissions/293314

Easyと方針は同じ。
(N^K)%6が求まれば答えが求まる。
　
(N^K)%6=((N%6)^K)%6　となるので、とりあえずNは%6とした値としておく。
上の桁から1桁ずつ%6しながら足し合わせることで、N%6を求めることができる。
　
mod上での累乗は周期性を持つ。
なので、N = N^loop (mod 6)となるloopが存在する。
これを求めよう。
　
すると、KはK%loopの値がわかればいいことになる。
N^K = N^(K%loop) (mod 6)
なので、K%loopをN%6と同じ要領で求める。
これでN^Kが普通に計算できる形になったので、(N^K)%6を計算して、その位置の数を答える。
"428571"

string N, K;
string S = "428571";
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;

    int n = 0;
    fore(c, N) n = (n * 10 + c - '0') % 6;

    int loop = 1;
    int x = n;
    rep(i, 1, 101) {
        x = (x * n) % 6;
        if (n == x) {
            loop = i;
            break;
        }
    }

    int k = 0;
    fore(c, K) k = (k * 10 + c - '0') % loop;
    if (k == 0) k = loop;

    int nk = 1;
    rep(i, 0, k) nk = (nk * n) % 6;
    cout << S[nk] << endl;
}