Ecasdqina's MEMO

Ecasdqina's MEMO.

メモ帳.

数列について

らてひるど

ARC050-E LCM111(https://beta.atcoder.jp/contests/arc050/tasks/arc050_c)をやった時に次の数列の任意項を一般の法で求める方法が必要になったのでメモ程度に書いておきます.
a_{N + 1} = a_N \times 10 + 1

コード

このコードでは a_{N + 1} = a_N \times p + 1 の任意項を求めています.

int sequence(int p, int n, int mod){
    if(!n) return 0;
    if(n & 1) return sequence(p, n - 1, mod) * p + 1;
    return sequence(p, n / 2, mod) * (mod_pow(p, n / 2, mod) + 1) % mod;
}