Submission #11855983


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

MOD = 10**9 + 7
N, K = map(int, read().split())

is_prime = np.zeros(K + 10, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3, K + 10, 2):
    if p * p > K:
        break
    if is_prime[p]:
        is_prime[p * p:: p + p] = 0
primes = np.where(is_prime)[0]


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

for p in primes.tolist():
    for i in range(K // p + 1):
        A[i] -= A[i * p]

answer = sum(i * x for i, 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 663 Byte
Status AC
Exec Time 295 ms
Memory 29640 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 24
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 109 ms 26544 KB
hand_02 AC 229 ms 27760 KB
hand_03 AC 105 ms 26772 KB
hand_04 AC 101 ms 26524 KB
hand_05 AC 98 ms 26720 KB
hand_06 AC 295 ms 29372 KB
random_01 AC 246 ms 29352 KB
random_02 AC 246 ms 29520 KB
random_03 AC 199 ms 28232 KB
random_04 AC 234 ms 29056 KB
random_05 AC 175 ms 27660 KB
random_06 AC 97 ms 26968 KB
random_07 AC 104 ms 26624 KB
random_08 AC 101 ms 26780 KB
random_09 AC 98 ms 26772 KB
random_10 AC 100 ms 26440 KB
random_11 AC 193 ms 27880 KB
random_12 AC 237 ms 28716 KB
random_13 AC 271 ms 28680 KB
random_14 AC 289 ms 29024 KB
random_15 AC 265 ms 28788 KB
sample_01 AC 98 ms 26768 KB
sample_02 AC 100 ms 26744 KB
sample_03 AC 284 ms 29640 KB