Submission #11814810


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9 + 7

N, K = map(int, read().split())

A = [0] * (K + 1)
for d in range(1, K + 1):
    A[d] = pow(K // d, N, MOD)

for d in range(K, 0, -1):
    for i in range(2, K // d + 1):
        A[d] -= A[d * i]

answer = sum(d * x for d, x in enumerate(A))
print(answer % MOD)

Submission Info

Submission Time
Task E - Sum of gcd of Tuples (Hard)
User maspy
Language Python (3.8.2)
Score 500
Code Size 412 Byte
Status
Exec Time 377 ms
Memory 11540 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01, sample_02, sample_03
All 500 / 500 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 19 ms 9012 KB
hand_02 307 ms 9696 KB
hand_03 18 ms 8908 KB
hand_04 20 ms 8896 KB
hand_05 17 ms 8900 KB
hand_06 377 ms 11148 KB
random_01 323 ms 11540 KB
random_02 314 ms 11404 KB
random_03 221 ms 10188 KB
random_04 301 ms 10900 KB
random_05 173 ms 9588 KB
random_06 20 ms 9200 KB
random_07 17 ms 8900 KB
random_08 19 ms 8904 KB
random_09 18 ms 9192 KB
random_10 20 ms 9068 KB
random_11 180 ms 9816 KB
random_12 274 ms 10732 KB
random_13 313 ms 10884 KB
random_14 360 ms 10884 KB
random_15 311 ms 10916 KB
sample_01 23 ms 9072 KB
sample_02 18 ms 9052 KB
sample_03 362 ms 11336 KB