Eight Function

2 secs 1024 MB

$88888888$ を素因数分解すると、 $2^3 \times 11 \times 73 \times 101 \times 137$ となります。
よって、 $137$ 以降の階乗の値は $88888888$ の倍数であることが分かるため、この問題における答えは変動しません。
したがって、 $N = 136$ までは愚直に計算することによってこの問題を十分高速に解くことができました。

実装例(C++)

#include<bits/stdc++.h>

using namespace std;

const long long MOD = 88888888;

int main(){
    long long n;
    cin >> n;
    if(n > 136){
        n = 136;
    }
    vector<long long> fact(n + 1);
    fact[0] = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = fact[i - 1] * i;
        fact[i] %= MOD;
    }
    long long ans = 1;
    for(int i = 0; i < n; i++){
        ans += fact[i + 1];
        ans %= MOD;
    }
    cout << ans << endl;
}