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
| Submission Time | |
|---|---|
| Task | E - Sum of gcd of Tuples (Hard) |
| User | MMNMM |
| Language | C++ (GCC 9.2.1) |
| Score | 500 |
| Code Size | 1012 Byte |
| Status | AC |
| Exec Time | 13 ms |
| Memory | 4008 KiB |
Judge Result
| Set Name | Sample | All | ||||
|---|---|---|---|---|---|---|
| Score / Max Score | 0 / 0 | 500 / 500 | ||||
| Status |
|
|
| Set Name | Test Cases |
|---|---|
| Sample | sample_01, sample_02, sample_03 |
| All | hand_01, hand_02, hand_03, hand_04, hand_05, hand_06, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, random_11, random_12, random_13, random_14, random_15, sample_01, sample_02, sample_03 |
| Case Name | Status | Exec Time | Memory |
|---|---|---|---|
| hand_01 | AC | 2 ms | 3456 KiB |
| hand_02 | AC | 7 ms | 3956 KiB |
| hand_03 | AC | 2 ms | 3560 KiB |
| hand_04 | AC | 2 ms | 3552 KiB |
| hand_05 | AC | 2 ms | 3532 KiB |
| hand_06 | AC | 11 ms | 3940 KiB |
| random_01 | AC | 7 ms | 4008 KiB |
| random_02 | AC | 7 ms | 3912 KiB |
| random_03 | AC | 7 ms | 3516 KiB |
| random_04 | AC | 8 ms | 3912 KiB |
| random_05 | AC | 5 ms | 3680 KiB |
| random_06 | AC | 2 ms | 3384 KiB |
| random_07 | AC | 2 ms | 3456 KiB |
| random_08 | AC | 2 ms | 3516 KiB |
| random_09 | AC | 2 ms | 3624 KiB |
| random_10 | AC | 2 ms | 3560 KiB |
| random_11 | AC | 8 ms | 3748 KiB |
| random_12 | AC | 11 ms | 3584 KiB |
| random_13 | AC | 11 ms | 3692 KiB |
| random_14 | AC | 13 ms | 3844 KiB |
| random_15 | AC | 11 ms | 3848 KiB |
| sample_01 | AC | 2 ms | 3572 KiB |
| sample_02 | AC | 2 ms | 3572 KiB |
| sample_03 | AC | 11 ms | 3960 KiB |