Submission #11988127

---

Source Code Expand

#include<bits/stdc++.h>

int main(){
    using namespace std;
    constexpr unsigned long MOD = 1000000007;
    // 冪剰余 a^n mod MOD
    const auto& modpow = [](unsigned long a, unsigned long n) -> unsigned long {
        unsigned long r{1};
        while(n){
            if(n & 1)(r *= a) %= MOD;
            (a *= a) %= MOD;
            n >>= 1;
        }
        return r;
    };
    
    unsigned long N, K;
    cin >> N >> K;

    vector<unsigned long> v(K + 1);
    // v[i] = floor(K/i)^N で初期化
    for(unsigned long i{1}; i <= K; ++i)v[i] = modpow(K / i, N);
    // 正しい v[i] を i の大きい方から求めます
    for(unsigned long i{K}; i > 0; --i){
        // v[i] = floor(K/i)^N - Σv[ij]
        for(unsigned long j{i * 2}; j <= K; j += i)v[i] += MOD - v[j];
        v[i] %= MOD;
    }

    // ans = Σ i v[i]
    unsigned long ans{0};
    for(unsigned long i{0}; i <= K; ++i)ans += i * v[i];
    cout << ans % MOD << endl;
    
    return 0;
}

Submission Info

Judge Result