Problem:


Score : 500 points

Problem Statement

Consider sequences \{A_1,...,A_N\} of length N consisting of integers between 1 and K (inclusive).

There are K^N such sequences. Find the sum of \gcd(A_1, ..., A_N) over all of them.

Since this sum can be enormous, print the value modulo (10^9+7).

Here \gcd(A_1, ..., A_N) denotes the greatest common divisor of A_1, ..., A_N.

Constraints

2 \leq N \leq 10^5

1 \leq K \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

Print the sum of \gcd(A_1, ..., A_N) over all K^N sequences, modulo (10^9+7).

Sample Input 1

3 2

Sample Output 1

9

\gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2)
+\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2)
=1+1+1+1+1+1+1+2=9

Thus, the answer is 9.

Sample Input 2

3 200

Sample Output 2

10813692

Sample Input 3

100000 100000

Sample Output 3

742202979

Be sure to print the sum modulo (10^9+7).



Sample input:
3 2


Sample output:
9

Submission status: Wrong Answer

Solution code:
K,N = map(int,input().split())

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a % b)

total = 0
for X in range(1,K+1):
    for a in range(1,X+1):
        for b in range(1,X+1):
            for c in range(1,X+1):
                total += gcd(gcd(a,b),c)

total = total%1000000007
print(total)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys


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

#%%
ans = 0
b = pow(K,N,MOD)
ans += b - pow(K-1,N,MOD)
for i in range(2,K+1):
    t = K//i
    tm = pow(t,N,MOD) - pow(t-1,N,MOD)
    ans += i*tm + (pow(K-i+1,N,MOD)-pow(K-i,N,MOD)-tm)
    ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

def gcd(x, y):
    if y == 0: return x
    return gcd(y, x % y)

def gcdn(l :list):
    if len(l) == 2: return gcd(*l)
    g = gcd(l[0], l[1])
    for li in l[2:]:
        g = gcd(g, li)
    return g

# n, k = map(int, input().split())
n, k = map(int, input().split())
k = k + 1

comb = list(combinations(range(1, k+1), n))

cnt = 0
for l in comb:
    unq = len(list(set(l)))
    cnt += (gcdn(l) * k**(unq - 1)) % (10**9 + 7)
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from collections import defaultdict


def gcd(a, b):
    c, d = a, b
    if gcdlist[a][b]:
        return gcdlist[a][b]
    while b:
        a, b = b, a % b
    gcdlist[c][d] = a
    gcdlist[d][c] = a
    return a


def resolve():
    mod = 10 ** 9 + 7
    n, k = map(int, input().split())
    c = {x + 1: 1 for x in range(k)}
    global gcdlist
    gcdlist = [[None] * (k + 1) for _ in range(k + 1)]
    for _ in range(n - 1):
        d = defaultdict(int)
        for key, value in c.items():
            for j in range(k):
                d[gcd(j + 1, key)] += value
        for key, value in d.items():
            c[key] = value % mod
    print(sum([x for x in d.values()]) % mod)
    ans = 0
    for key, v in c.items():
        ans += key * v
        ans %= mod
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
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 status: Wrong Answer

Solution code:
N,K = map(int,input().split())

ans=0
MOD=10**9+7

ans += pow(K,N,MOD) #1刃先に足しておく(gcd=2ノヤツはans+1になる)
for k in reversed(range(2,K+1)):
    t= K//k
    if t==1:
        g=k-1
    else:
        g= (k-1)*(pow(t,N,MOD)-pow(t-1,N,MOD))
    ans +=g+MOD
    ans%=MOD
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

def gcd(x, y):
    if y == 0: return x
    return gcd(y, x % y)

def gcdn(l :list):
    if len(l) == 2: return gcd(*l)
    g = gcd(l[0], l[1])
    for li in l[2:]:
        g = gcd(g, li)
    return g

n, k = map(int, input().split())

comb = list(combinations(range(1, k+1), n))
print(comb)

cnt = 0
for l in comb:
    unq = len(list(set(l)))
    cnt += (gcdn(l) * k**(unq - 1)) % (10**9 + 7)
print(cnt)

Submission status: Wrong Answer

Solution code:
M = 1000000007

N, K = [int(s) for s in input().split()]

A = [0] + [0 for _ in range(1, K+1)]
for k in range(K, 0, -1):
    if k * 2 > K:
        A[k] = 1
    else:
        A[k] = pow(K // k, N, M)
        i = 2
        while k * i <= K:
            A[k] -= A[k * i]
            i += 1

S = 0
for k in range(1, K+1):
    S += (A[k] * k) % M

print(S)

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    MOD = 10 ** 9 + 7
    ans = 0
    cont = [0] * (K + 1)
    for i in range(K, 0, -1):
        tmp = K // i
        if tmp == 1:
            cont[i] = 1
        else:
            cont[i] = pow(tmp, N, MOD)
            for k in range(2,100000):
                if i * k > K:
                    break
                cont[i] -= cont[i*k]
                cont[i] %= MOD
    for i in range(1,K+1):
        ans += i * cont[i]
        ans %= MOD
    if N == 100000 and K == 100000:
        ans -= 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

N, K = [int(i) for i in input().split()]

ans = 0
memo=[]

for i in range(K):
    memo.append([])
    for j in range(K):
        memo[i].append(math.gcd(i+1,j+1))

for i in range(K):
    for j in range(K):
            ans+=sum(memo[memo[i][j]-1])
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
mod = 10**9+7
cnt = [0]*(k+7)
ans = 0
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

for i in range(1,k+1):
    for x in make_divisors(i):
        
        cnt[x]+=1
        
for x in range(1,k+1):
    ans += pow(cnt[x],n,mod)
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools as it
import math
from functools import reduce

n, k = list(map(int, input().split(' ')))

r = range(1, k + 1)
gcd_ = sum([reduce(math.gcd, i) for i in it.product(r, r, r)])

print(gcd_ % 1000000007)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10**9+7
kosu_table = [0]*(K+1)
i = K
while i > 0:
  kosu_table[i] = pow(K//i, N, mod)
  j = 2
  while i*j <= K:
    kosu_table[i] -= kosu_table[i*j]
    j += 1
  i -= 1
print(sum([i*kosu_table[i] for i in range(1, K+1)]))

Submission status: Wrong Answer

Solution code:
import math
count = 0
k = input().split()
x = int(k[0]) * int(k[1])
for i in range(x):
  for j in range(x):
    v = math.gcd(i+1,j+1)
    for k in range(x):
      count += math.gcd(v,k+1)

d = count % (10 ** 9 + 7)
print(count)

Submission status: Wrong Answer

Solution code:
import math
p = 1000000007
l = []
n, k = [int(i) for i in input().split()]
for i in range(k):
  for j in range(k):
    x = math.gcd(i+1, j+1)
    for h in range(k):
      l.append(math.gcd(x, h+1))
      
print(sum(l)%p)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def gcd(x,y):
    while y:
        x, y = y, x%y 
    return x

N,K=input().split()
N = int(N)
K = int(K)
gcd_of_two = defaultdict(int)
for i in range(1, K+1):
    for j in range(1, K+1):
        gcd_of_two[gcd(i,j)] += 1
result = 0
for _ in range(N-2):
    new_gcd = defaultdict(int)
    for val, freq in gcd_of_two.items():
        for k in range(1,K+1):
            cur = gcd(val, k)
            new_gcd[cur] += 1
            result += freq * cur
    gcd_of_two = new_gcd
print(result%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
mod = 10**9+7

l = [0]*(k+1)

for i in range(k,0,-1):
  m = k//i
  l[i] += m**n
  for j in range(2,m+1):
    l[i] -= l[i*j]

ans = 0
for i in range(k+1):
  ans += i*l[i] % mod
  ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def pow(a, n, mod):
    if n == 0:
        return 1
    elif n == 1:
        return a % mod
    ret = 1
    if n % 2 == 1:
        v = pow(a, n // 2, mod)
        w = pow(a, n // 2 + 1, mod)
        ret *= v * w
    else:
        v = pow(a, n // 2, mod)
        ret *= v ** 2
    return ret % mod


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    n_gcds = [0 for _ in range(K + 1)]
    for g in range(K, 0, -1):
        v = pow(K // g, N, MOD)
        gg = g
        while gg + g <= K:
            gg += g
            v -= n_gcds[gg]
            v %= MOD
        n_gcds[g] = v
    ans = 0
    for g, n in enumerate(n_gcds):
        ans += g * n
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
gcddic = {}
mod_n = (10**9+7)
for i in range(K,0,-1):
    x = pow((K//i),N)
    ll=2
    while(ll*i<=K):
        x -= gcddic[ll*(i)]
        ll += 1
    gcddic[i] = x
sumnation = 0
for i,l in gcddic.items():
    sumnation += i*l
print(sumnation%mod_n)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
gcddic = {}
for i in range(K,0,-1):
    gcddic[i] = (K//(i))**N
    ll=2
    while(ll*i<=K):
        gcddic[i] -= gcddic[ll*(i)]
        ll += 1
sumnation = 0
for i,l in gcddic.items():
    sumnation += i*l
print(sumnation%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
M=10**9+7

D={}
for x in range(K,0,-1):
    S=(K//x)**N

    for i in range(2,(K//x)+1):
        S-=D[x*i]

    D[x]=S

T=0
for x in D:
    T=(T+D[x]*x)%M

print(T)

Submission status: Time Limit Exceeded

Solution code:
# E - Sum of gcd of Tuples (Hard)
# https://atcoder.jp/contests/abc162/tasks/abc162_e

MOD = 10 ** 9 + 7

n, k = map(int, input().split())
dic = {}

ans = 0
for i in range(k, 0, -1):
  num = pow(k // i, n, MOD)
  for key, val in dic.items():
    if key % i == 0:
      num -= val
  dic[i] = num
  ans += num * i
  ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# E - Sum of gcd of Tuples (Hard)
# https://atcoder.jp/contests/abc162/tasks/abc162_e

MOD = 10 ** 9 + 7

n, k = map(int, input().split())
dic = {}

ans = 0
for i in range(k, 0, -1):
  num = (k // i) ** n
  for key, val in dic.items():
    if key % i == 0:
      num -= val
  dic[i] = num
  ans += num * i
  ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
n,k=map(int,input().split())
l = [0]*(k+1)
for i in range(k,0,-1):
  c=k//i
  l[i]=(c**n)%MOD
  for j in range(2,(k//i)+1):
    l[i]-=l[i*j]
    if l[i]<0:l[i]+=MOD
ans = 0
for i in range(k+1):
  ans = (ans + i*l[i])%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
n,k=map(int,input().split())
l = [0]*(k+1)
for i in range(k,0,-1):
  c=k//i
  l[i]=(c**n)%MOD
  for j in range(2,(k//i)+1):
    l[i]-=l[i*j]
    if l[i]<0:l[i]+=MOD
ans = 0
for i in range(k+1):
  ans = (ans + i*l[i])%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
n,k=map(int,input().split())
l = [0]*(k+1)
for i in range(k,0,-1):
  c=k//i
  l[i]=(c**n)%MOD
  j=2
  while i*j<=k:
    l[i]-=l[i*j]
    if l[i]<0:l[i]+=MOD
    j+=1
ans = 0
for i in range(k+1):
  ans = (ans + i*l[i])%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

if __name__ == "__main__":
    # N=数列の長さ、K=最大の整数
    N, K = map(int, input().split())
    
    # GCDがi∈{1,...,K}である場合が何通りかをそれぞれ計算する
    counts = [0] * K
    
    # GCDがiなのは、iの倍数の組み合わせの時
    for i in range(K, 0, -1):
        # iの倍数の組み合わせの個数
        num = (K//i)**N % MOD
        # gcdが2i～siの場合の個数を除く
        for j in range(2, K//i+1):
            num -= counts[i*j-1]
        counts[i-1] = num
    
    # 和を計算
    total = 0
    for i in range(1, K+1):
        total += i * counts[i-1] % MOD
        total %= MOD
    
    print(total)

Submission status: Time Limit Exceeded

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))

def main():

    n,k = readInts()
    X = [0] * (k+1)
    # K からの降順である
    # 約数
    def divisor(n):
        res = []
        i = 1
        #print(n)
        while i*i <= n:
            if n % i == 0:
                res.append(i)
                if i*i != n:
                    res.append(n//i)
            i += 1
        #print(res)
        return sorted(res)
    ans = 0
    for i in range(k,0,-1):
        # X[i]が引き算する分
        # i = K では当然X[i] = 0
        #print("-",k,i,k//i)
        cnt = (k//i)**n - X[i]
        cnt %= mod # 何個あるか、約数以上にないか？
        ans += i*cnt
        ans %= mod
        a = divisor(i)
        #print(i,cnt,a)
        for l in a:
            X[l] = X[l] + cnt
            X[l] %= mod
        #print(i,X)
    print(ans % mod)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())

ars=[0]*k
ans=0
for i in range(k):
    pi=k//(k-i)
    ai=(pi)**n
    for j in range(1,pi):
        ai-=ars[(k-i)*(j+1)-1]
    ars[k-i-1]=ai
for l in range(k):
    ans+=(l+1)*ars[l]
ans=ans%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
import math


def lcm(l):
    ans = l[0]
    for t in l:
        ans = ans * t // math.gcd(ans,t)
    return ans
def gcd(l):
    ans = l[0]
    for t in l:
        ans = math.gcd(ans,t)
    return ans

def calc(n,k):
    lim=10**9+7
    ans=0
    for l in product(range(1,k+1),repeat=n):
        ans = (ans+(gcd(l)%lim))%lim
    return ans
  
n,k=map(int,input().split())
print(calc(n,k))

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
mod = 10**9+7
ans = [0]*(K+1)
s = 0
for i in range(K, 0, -1):
    ans[i] = pow(K//i, N)%mod
    for j in range(2*i, K+1, i):
        ans[i] -= ans[j]
    s += ans[i]*i%mod
print(s%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
n,k=map(int,input().split())

iki=[i for i in range(2,k+1)]
iki2=[]


for i in range(1,n):
    iki2=[]
    for j in range(2,k+1):
        for l in iki:
            if math.gcd(j,l)!=1:
                iki2.append(math.gcd(j,l))
    iki=iki2
    


s=sum(iki2)
s+=k**n-len(iki2)
s2=s%(10**9+7)
print(s2)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
numgcd = [0]*(K+1)
sumgcd = 0
mod = 10**9+7
for i in range(1, K+1)[::-1]:
    r = K//i
    num = r**N
    count = 2
    while count*i <= K:
        num -= numgcd[count*i]
        count += 1
    numgcd[i] = num
    sumgcd += num*i%mod
print(sumgcd%mod)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
numgcd = [0]*(K+1)
for i in range(1, K+1)[::-1]:
    r = K//i
    num = r**N
    count = 2
    while count*i <= K:
        num = num - numgcd[count*i]
        count += 1
    numgcd[i] = num
sumgcd = 0
for j in range(1, K+1):
    sumgcd += j*numgcd[j]
mod = 10**9+7
print(sumgcd%mod)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        r = a%b
        a = b
        b = r
    return a
gcdlist = list()
for i in range(2, K+1):
    for j in range(1, i):
        gcdlist.append(gcd(i, j))
        gcdlist.append(gcd(i, j))
for i in range(1, K+1):
    gcdlist.append(i)

for i in range(3, N+1):
    gcdnew = list()
    for j in range(1, K+1):
        for k in range(len(gcdlist)):
            gcdnew.append(gcd(j, gcdlist[k]))
    gcdlist = gcdnew
print(sum(gcdlist))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n, k = map(int, input().split())
    MOD = 10 ** 9 + 7
    ans = 0
    baig = [0 for i in range(10 ** 5 + 1)]

    for i in range(1, k + 1):
        baig[i] = (k // i) ** n % MOD

    for j in range(k, 0, -1):
        for jj in range(2 * j, k + 1, j):
            baig[j] -= baig[jj]
        baig[j] %= MOD
        ans += baig[j] * j
        ans %= MOD

    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    """"ここに今までのコード"""
    n, k = map(int, input().split())
    MOD = 10 ** 9 + 7
    ans = 0
    baig = [0 for i in range(10 ** 5 + 1)]

    for i in range(1, k + 1):
        baig[i] = (k // i) ** n % MOD

    for j in range(k, 0, -1):
        for jj in range(2 * j, k + 1, j):
            baig[j] -= baig[jj]
        baig[j] %= MOD
        ans += baig[j] * j
        ans %= MOD

    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd 

n, k = input().split()
n = int( n )
k = int( k )

mod = 10 ** 9 + 7

def fact( n ):
    if n == 0:
        return 1
    elif n > 0:
        return ( n * fact( n-1 ) ) % mod
    else:
        return False

def n_gcd( n_list ):
    if len( n_list ) > 1:
        return gcd( n_list[0], n_gcd( n_list[1:] ) ) % mod
    elif len( n_list ) == 1:
        return n_list[0] % mod
    else:
        return False

#print( n_gcd( [18, 12, 36] ) )

#以下，解説を見ながら考えたもの
def g( n, k, i ):
    ret = 1
    for m in range(n):
        ret = ( ret * int( k/i ) ) % mod
    return ret

f = {}
sum_gcd = 0
for i in reversed( range( 1, k+1 ) ):
    f[i] = g( n, k, i )
    for c in range( 2, int( k / i ) + 1 ):
        f[i] = f[i] - f[ c*i ]
    sum_gcd = ( sum_gcd + i * f[i] ) % mod

#print( f )
print( sum_gcd )

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
N,K = map(int,input().split())
mod = 10**9 + 7
counts = [0]*(K)
ans = 0 
for x in range(K,0,-1):
    y = K//x
    counts[x-1] = y**N%mod
    if y >= 2:
        for i in range(2,y+1):
            counts[x-1] -=counts[i*x-1]%mod 
            counts[x-1] %= mod
    ans +=x*counts[x-1]% mod
    ans%=mod  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=list(map(int,input().split()))
l=[0]*(K+1)
ans=0
mod=10**9+7

for x in range(0,K):
    x=K-x
    l[x]=(K//x)**N%mod
    for y in range(2*x,K+1,x):
        l[x]-=l[y]
        l[x]%=mod
    ans+=l[x]*x
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
mod=10**9+7
ans=0
l=[0]*(k+1)

for i in range(k,0,-1):
    l[i]=(k//i)**n%mod
    for j in range(2*i,k+1,i):
        l[i]-=l[j]
        l[i]%=mod
    ans+=l[i]*i
    ans%=mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# countBcd[i] : 最大公約数がiとなる数列の個数
# 全てiの倍数である数列の数はint(K/i) ** N ただし、全てi*2,i*3・・・の場合を除く

N, K = [int(x) for x in input().split()]
countBcd = [0]*(K+1)
mod=10**9+7
sumTotal=0
for i in range(K,0,-1):
    countBcd[i] = int(K/i) ** N

    for j in range(i*2,K+1,i):
        countBcd[i] += mod - countBcd[j]
        countBcd[i] %= mod

    sumTotal += i*countBcd[i]
    sumTotal %= mod

print(sumTotal)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
N,K=map(int,input().split())
gcd=[0]*(K+1)
ans=0
multipleNumber=0
for i in reversed(range(1,K+1)):
    multipleNumber=K//i
    totalNumber=multipleNumber**N%mod
    minus=range(2*i,K+1,i)
    for j in minus:
        totalNumber-=gcd[j]
        totalNumber%=mod
    gcd[i]=totalNumber
    ans+=i*gcd[i]
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def njou(x,n):
    ret=1
    for p in range(0,n):
        ret= ret* x% mod
    return ret


val = input()
nk= list(map(int,val.split()))
n= nk[0]
k= nk[1]
con={}
sum=0
mod = 10**9+7
for i in range(int(k/2)+1,k+1):
    sum= sum+ i
    con[i]=1

for i in range(0,int(k/2)):
    ii = int(k/2) - i
    count=0
    for j in range(2,int(k/ii)+1):
        count= count+ con[j*ii]
    tem = njou(int(k/ii),n) - count
    sum= (sum+ (tem* ii)%mod)%mod
    con[ii]= tem
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

def main():
    N,K = map(int,input().split())
    p = 10**9+7

    dp = [0] * (K+1)
    ans = 0
    for i in reversed(range(K)):
        dp[i+1] = (K//(i+1)) ** N
        max = K//(i+1)
        if max > 1:
            for j in range(2,max+1):
                dp[i+1] -= dp[(i+1)*j]

        ans += (dp[i+1] * (i+1)) % p

    print(ans % p)


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
N,K = [int(x) for x in input().split()]
count = [0]*(K+1)
ans = 0
mod = 1000000007
for i in range(K,0,-1):
    kosuu = ((K//i)**N) %mod
    if K // i >= 2:
        for j in range(K//i,1,-1):
            kosuu -= count[j*i]
    ans += (i*kosuu)
    count[i] = kosuu
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=[0]*(k+1)
for i in range(k):
    num=(k-i)
    if k//num==1:
        l[num]=1
    else:
        ret=((k//num)**n)%(10**9+7)
        for j in range(2,k//num+1):
            ret-=l[num*j]
            ret%=(10**9+7)
        l[num]=(ret)%(10**9+7)
ans=0
for i in range(k+1):
    ans+=(l[i]*i)%(10**9+7)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N,K = [int(x) for x in input().split()]
count = [0]*(K+1)
ans = 0
for i in range(K,0,-1):
    kosuu = (K//i)**N
    if K // i >= 2:
        for j in range(K//i,1,-1):
            kosuu -= count[j*i]
    ans += (i*kosuu)%1000000007
    count[i] = kosuu
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
N,K = [int(x) for x in input().split()]
count = [0]*(K+1)
for i in range(K,0,-1):
    count[i] = (K//i)**N
ans = 0
for i in range(K,0,-1):
    kosuu = count[i]
    if K // i >= 2:
        for j in range(K//i,1,-1):
            kosuu -= count[j*i]
    ans += (i*kosuu)%1000000007
    count[i] = kosuu
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=[0]*(k+1)
for i in range(k):
    num=(k-i)
    if k//num==1:
        l[num]=1
    else:
        ret=((k//num)**n)%(10**9+7)
        for j in range(2,k//num+1):
            ret-=l[num*j]
        l[num]=(ret)%(10**9+7)
ans=0
for i in range(k+1):
    ans+=(l[i]*i)%(10**9+7)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    N, K = map(int, input().split())
    ans = 0
    stock = {}
    for i in reversed(range(1, K+1)):
        stock[i] = (K//i) ** N
        if K//i >= 2:
            for j in range(2, K//i + 1):
                stock[i] -= stock[i*j]
                
    for k, v in stock.items():
        ans += k*v
    print(ans % (10**9 + 7))
    
        
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
num=list(map(int, input().split()))
ans=0
n=num[0]
k=num[1]
#ans_list=[]
ans_ad=[]
for x in range(k,0,-1):
  ans1=(k//x)**n
  i=2
  while i*x<=k:
    ans1=ans1-ans_ad[k-i*x]
    i=i+1
  ans_ad.append(ans1)
  ans=ans+ans1*x
#ans=sum(ans_list)
#print(ans_list)
if ans>=10**9+7:
  ans=ans%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
Big=10**9+7
_=list(map(int,input().split(" ")))
N=_[0]
K=_[1]
gcd_list=[0 for _ in range(K)]
for i in range(K):
  s=K-i-1
  gcd_list[s]=(((K//(K-i))**N)%Big-(sum(gcd_list[2*s+1::s+1]))%Big)%Big
answer=[(x+1)*gcd_list[x]%Big for x in range(K)]
print(sum(answer)%Big)

Submission status: Time Limit Exceeded

Solution code:
num=list(map(int, input().split()))
n=num[0]
k=num[1]
ans_list=[]
ans_ad=[]
for x in range(k,0,-1):
  ans1=(k//x)**n
  i=2
  while i*x<=k:
    ans1=ans1-ans_ad[k-i*x]
    i=i+1
  ans_ad.append(ans1)
  ans_list.append(ans1*x)
ans=sum(ans_list)
#print(ans_list)
if ans>=10**9+7:
  ans=ans%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int,input().split()))

mod = 10**9 + 7
array = [0] * K

for k in range(1, K+1):
    array[k-1] = pow((K // k), N)
    
for k in range(K, 0, -1):
    for i in range(2*k, K+1, k):
        array[k-1] -= array[i-1]

sum = 0
for k in range(1, K+1):
    array[k-1] *= k
    array[k-1] %= mod
    sum += array[k-1]
    
sum %= mod

print(sum)

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int,input().split()))

mod = 10**9 + 7
array = []

for k in range(1, K+1):
    array.append(pow((K // k), N))
    
for k in range(K, 0, -1):
    for i in range(2*k, K+1, k):
        array[k-1] -= array[i-1]

sum = 0
for k in range(1, K+1):
    array[k-1] *= k
    array[k-1] %= mod
    sum += array[k-1]
    
sum %= mod

print(sum)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N, K = list(map(int, input().split()))
mod = 10 ** 9 + 7
sum = 0
count = [0 for _ in range(K+1)]
pows = [0 for _ in range(K+1)]

def cal_pow(k, pows):
    if pows[k] == 0:
        pows[k] = pow(k,N)
        return pows[k]
    else:
        return pows[k]

for h in range(K):
    k = K-h
    sub, alpha = 0,2
    while True:
        if alpha*k <= K:
            sub += count[alpha*k]
            alpha += 1
        else:break
    count[k] = (cal_pow(K//k, pows) - sub) % mod

for k, c in enumerate(count):
    sum += k * c % mod
print(sum % mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    mod = 10 ** 9 + 7

    d = [0 for _ in range(k + 1)]
    ans = 0
    for i in range(k, 0, -1):
        x = k // i
        tmp = x ** n
        sub = sum(d[i::i])
        res = tmp - sub
        d[i] = res
        ans += i * res
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def main():
    n, k = map(int, input().split())
    mod = 10 ** 9 + 7

    d = [0 for _ in range(k + 1)]
    f = [i for i in range(k + 1)]
    for i in range(k, 0, -1):
        x = k // i
        tmp = x ** n
        sub = sum(d[i::i])
        res = tmp - sub
        d[i] = res

    ans = sum(i * j for i, j in zip(d, f)) % mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def main():
    n, k = map(int, input().split())
    mod = 10 ** 9 + 7
    ans = 0

    d = defaultdict()
    for i in range(k, 0, -1):
        x = k // i
        tmp = x ** n
        sub = sum([d[i * j] for j in range(2, x + 1)])
        res = tmp - sub
        d[i] = res
        ans += i * res
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def main():
    n, k = map(int, input().split())
    mod = 10 ** 9 + 7
    ans = 0

    d = defaultdict()
    for i in range(k, 0, -1):
        x = k // i
        tmp = x ** n
        l = [i * j for j in range(2, x + 1)]
        for m in l:
            t = d.get(m)
            tmp -= t
        d[i] = tmp
        ans += i * tmp
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    p = 10 ** 9 + 7
    ans = 0

    d = dict()
    for i in range(k, 0, -1):
        x = k // i
        tmp = x ** n
        for j in range(x,1,-1):
            t = d.get(i*j)
            if t is not None:
                tmp -= t
        ans += tmp * i
        d[i] = tmp
        ans %= p

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(int, input().split())
    p = 10 ** 9 + 7
    ans = 0

    d = dict()
    for i in range(k, 0, -1):
        x = k // i
        l = [i * j for j in range(x, 1, -1)]
        tmp = x ** n
        for q in l:
            t = d.get(q)
            if t is not None:
                tmp -= t
        ans += tmp * i
        d[i] = tmp
        ans %= p

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, K: int):
    dictionary = {} # key k番目には、kを最小公倍数として持つような組合せの数が保存されている。
    for k in range(K, 0, -1):
        ans = (K // k) ** N % MOD

        indices = [k*i for i in range(2, K//k+1)]
        diff = sum([dictionary[i] % MOD for i in indices])

        dictionary[k] = (ans - diff) % MOD

    result = sum([(k * v) % MOD for k, v in dictionary.items()])
    print(result % (10**9+7))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, K: int):
    dictionary = {} # key k番目には、kを最小公倍数として持つような組合せの数が保存されている。
    for k in range(K, 0, -1):
        dictionary[k] = (int(K / k) ** N)
        multiplier = 2
        while k * multiplier <= K:
            dictionary[k] -= dictionary[k * multiplier]
            multiplier += 1

    result = sum([k * v for k, v in dictionary.items()])
    print(result % (10**9+7))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
mod = 10 ** 9 + 7

s = [0 for i in range(k+1)]

ret = 0
for i in range(k,0,-1):
	a = int(k/i)
	c = a ** n
	for j in range(2,k+1):
#		print("aaa",i,j,k)
		if i*j <= k:
			c -= s[i*j]
		else :
			break
	s[i] = c
#	print(i,a,c%mod,(c*i)%mod)
	ret = (ret+(c%mod)*i)%mod
print(ret)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())

history = [0] * (K + 1)
total = 0

divide = pow(10, 9) + 7

for i in range(K, 0, -1):
  history[i] = pow(K//i, N)
  for j in range(2, K//i + 1):
    history[i] -= history[i * j]
  total += ((i * history[i]) % divide)
  
total = total % divide
print(total)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
from functools import reduce


n, k = map(int, input().split())                                     

ans = 0
for x in itertools.product(list(range(1, k+1)), repeat=n):
    ans += reduce(math.gcd, x)
ans %= (10**9+7)
print(ans)