Yukicoder072 そろばん Med

問題概要

no71の制約の強化版。

$N\leqq10^{15}$

yukicoder072

解法

$i,N-i$個に分けるとすると、個数は二次関数として表現でき、当然凸である。
式から極値が求められる。
Nが奇数のときに限り少し右に移動したほうが嬉しい?

計算量:$O(1)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using LL = long long;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        const LL mod = 1000007;
        LL N; cin >> N;
        LL x = (N + 1) / 2;
        N %= mod;
        x %= mod;
        LL ans = (-x*x + N*x + N) % mod;
        ans = (ans + mod) % mod;
        cout << ans << "\n";
    
        return 0;
    }