https://atcoder.jp/contests/abc139/tasks/abc139_d
解説
https://atcoder.jp/contests/abc139/submissions/7339048
Nの上限が109なので、Nに起因するアルゴリズムではなさそう。
それで400点ということもあり、特殊な解法が存在するっぽい。
という訳で実験してみよう。
N ans P 1 0 1 2 1 2 1 3 3 1 3 2 2 3 1 4 6 2 3 4 1 5 10 1 3 4 5 2 2 1 4 5 3 2 3 4 5 1
2 3 4 ... N 1のようにしていけばいいっぽい。
こうすると、1+2+3+...+(N-1)が得られる。
つまり、(N-1)*N/2が答え。
ll N; //--------------------------------------------------------------------------------------------------- void labo(int n) { vector<int> v; rep(i, 0, n) v.push_back(i + 1); do { int tot = 0; rep(i, 0, n) tot += (i + 1) % v[i]; printf("%d", tot); rep(i, 0, n) printf(" %d", v[i]); printf("\n"); } while (next_permutation(all(v))); } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; ll ans = (N - 1) * N / 2; cout << ans << endl; }