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: Time Limit Exceeded

Solution code:
n, k = (int(x) for x in input().split())

c = {} 
t = 0
for x in range(k, 0, -1):
    q = k // x
    c[x] = q ** n - sum(c[x * y] for y in range(2, q + 1))
    t += c[x] * x
    t = t % 1000000007

print(t)

Submission status: Time Limit Exceeded

Solution code:
n, k = (int(x) for x in input().split())

c = {} 
t = 0
for x in range(k, 0, -1):
    c[x] = (k // x) ** n
    c[x] = c[x] - sum(c[x * y] for y in range(2, k // x + 1))
    s = c[x] * x
    t += s
    t = t % 1000000007

print(t)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

m = 1000000007

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

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

for i in range(k, 0, -1):
    c[i] = ((k // i) ** n) % m
    for j in range(2, k + 1):
        if i * j > k:
            break
        else:
            c[i] = (c[i] - c[i * j] + m) % m

s = 0
for i in range(1, k + 1):
    s = (s + i * c[i]) % m

print(s)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
S=0
l=[0 for _ in range(K)]
for i in range(K):
    j=K-i
    v=(K//j)**N-l[j-1]
    for w in range(j//2):
        if j%(w+1)==0:
            l[w]+=v
    S+=j*v
print(S%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
S=0
l=[0 for _ in range(K)]
for i in range(K):
    j=K-i
    u=K//j
    v=u**N-l[j-1]
    for w in range(j):
        if j%(w+1)==0:
            l[w]+=v
    S+=j*v
print(S%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(i) for i in input().split(' ')]
MOD = 10 ** 9 + 7

COUNT = {}
for i in range(K,0,-1):
    whole = (K//i)**N

    c = 2
    while i * c <= K:
        whole -= COUNT[i*c]
        c += 1

    COUNT[i] = whole % MOD

SUM = 0
for k, v in COUNT.items():
    SUM += k * v
    SUM %= MOD

print(SUM)

Submission status: Time Limit Exceeded

Solution code:

# -*- coding: utf-8 -*-

import math
N, K=map(int, input().split())


count=0
lis=[[0 for i in range(K)] for k in range(K)]
l0=[1 for i in range(K)]

ans=0

sq=int(K**0.5)
for i in range(1,K+1):
    for j in range(i+1,K+1):
        k=math.gcd(i,j)
        lis[i-1][j-1] =k
#print(lis)
#print("fin")
for i in range(2,N+1):
    l1=[0 for i in range(K)]
    for n in range(K):
        l1[n]+=l0[n]
        for j in range(n+1, K):
            k=lis[n][j]
            l1[k-1]+=l0[n]+l0[j]
    
    l0=l1.copy()
    #print(l0)


for i in range(1,K+1):
    ans+=i*l0[i-1]
#print(l0)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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

for x in reversed(range(1,k+1)):
    num= k//x

    c = num**n
    for j in range(2,num+1):
        c-= cnts[x*j]
    cnts[x]=c

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

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
ans=0
l=[0]

for i in range(K+1):
  if i!=0:
    a=i
    for j in range(int(i**0.5)+1):
      if i!=1 and j!=0 and i%j==0:
        a-=l[j]
        if j!=1 and int(i/j)!=j:
          a-=l[int(i/j)]
    l.append(a%(10**9+7))
    ans+=l[i]*((int(K/i)**N)%(10**9+7))
    ans%=(10**9+7)

print(str(ans))

Submission status: Time Limit Exceeded

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

def power(a,x): #a**xの計算
    T=[a]
    while 2**(len(T))<mod: #a**1,a**2.a**4,a**8,...を計算しておく
        T.append(T[-1]**2%mod)
    b=bin(x) #xを2進数表記にする
    ans=1
    for i in range(len(b)-2):
        if int(b[-i-1])==1:
            ans=ans*T[i]%mod
    return ans

for i in range(k):
    cnt=power(k//(k-i),n)
    now=(k-i)*2
    while now<=k:
        cnt-=A[now-1]
        now+=k-i
    A[k-i-1]=cnt

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

Submission status: Time Limit Exceeded

Solution code:
a= list(map(int,input().split()))
N = a[0]
K = a[1]

a = [0]*K

for i in range(K):
    x = K-i-1
    a[x] = (K//(x+1))**N

    t = 2
    while t*(x+1)<=K:
        a[x] = a[x] - a[t*(x+1)-1]
        t = t+1

s = 0
for i in range(K):
    s = s + (i+1)*a[i]

ans = s%(10**9+7)

print(ans)

Submission status: Time Limit Exceeded

Solution code:

mod=10**9+7


n,k=map(int,raw_input().split())
ans=0
cnt=0
xd=[0 for i in range(k+1)]
for i in range(k,0,-1):
    xd[i]=pow(k/i,n)
    for j in range(2*i,k+1,i):
        xd[i]=(xd[i]-xd[j]+mod)%mod
for i in range(1,k+1):
    ans=(ans+xd[i]*i)%mod
print ans

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, K = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
dd = defaultdict(int)

ans = 0
for i in range(K, 0, -1):
    dd[i] = (K // i) ** N
    for temp in range(i * 2, K + 1, i):
        dd[i] -= dd[temp]
    ans += dd[i] * i
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

dic = {} #ここに結果を保存していく。
ans = 0
moddo = 10**9+7

for i in range(k):
    t = k - i #これで大きいほうから順にとる。
    if t > k/2: #tがk/2より大きいときはすべてtじゃないと最大公約数はtにならない。
        dic[t] = 1
        ans += t
    else:
        temp = (math.floor(k/t)**n)%moddo
        #print(temp)
        fac = 2
        while fac*t <= k:
            temp -= dic[fac*t]
            fac += 1
        dic[t] = temp%moddo
        ans = (ans+((temp*t)%moddo))%moddo

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
MOD=10**9+7
ans=0
baig=[0]*(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))

Submission status: Time Limit Exceeded

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

baig=[0]*(10**5+1)
exg=[0]*(10**5+1)

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

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

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
mod=10**9+7
GCD=[0 for _ in range(K+1)]
for i in range(1,K+1):
    k=K//i
    GCD[i]=(k**N)%mod

ans=0
for i in range(K,0,-1):
    for j in range(2,K//i+1):
        GCD[i]-=GCD[i*j]
    ans+=(GCD[i]*i)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
md = pow(10,9) + 7

cnt_memo = [0]*(K+1)
cnt_R_memo = [0]*(K+1)

def main():
    ret = 0
    for k in range(1,K+1):
        cnt_R_memo[k]=pow(K//k,N)%md
    for k in range(K,0,-1):
        cnt_memo[k]=(cnt_R_memo[k] - sum(cnt_memo[2*k::k]))%md
        ret += (cnt_memo[k]*k)%md
    print(ret%md)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
md = pow(10,9) + 7

cnt_memo = [0]*(K+1)
cnt_R_memo = [0]*(K+1)

def main():
    ret = 0
    for k in range(1,K+1):
        cnt_R_memo[k]=pow(K//k,N)%md
    for k in range(K,0,-1):
        cnt_memo[k]=(cnt_R_memo[k] - sum(cnt_memo[2*k::k]))%md
        ret += (cnt_memo[k]*k)%md
    print(ret%md)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
dp = [0]*(K+1)
MOD = 10**9+7
ans = 0
for X in range(K,0,-1):
  m = (K//X)**N%MOD
  x = 2*X
  while x<=K:
    m -= dp[x]
    m %= MOD
    x += X
  ans += X*m
  ans %= MOD
  dp[X] = m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

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

dic = {} #ここに結果を保存していく。
ans = 0
moddo = 10**9+7

for i in range(k):
    t = k - i #これで大きいほうから順にとる。
    if t > k/2:
        dic[t] = 1
        ans += t
    else:
        temp = (math.floor(k/t)**n)%moddo
        #print(temp)
        fac = 2
        while fac*t <= k:
            temp -= dic[fac*t]
            fac += 1
        dic[t] = temp
        ans = (ans+((temp*t)%moddo))%moddo

#for i in range(1,k+1):
#    ans += i*dic[i]
#    if ans >= moddo:
#        ans = ans%moddo
    
        
#print(dic)
#print(sum(dic.values()))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

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

dic = {} #ここに結果を保存していく。
ans = 0
moddo = 10**9+7

for i in range(k):
    t = k - i #これで大きいほうから順にとる。
    if t > k/2:
        dic[t] = 1
        ans += t
    else:
        temp = math.floor(k/t)**n
        #print(temp)
        fac = 2
        while fac*t <= k:
            temp -= dic[fac*t]
            fac += 1
        dic[t] = temp
        ans = (ans+((temp*t)%moddo))%moddo

#for i in range(1,k+1):
#    ans += i*dic[i]
#    if ans >= moddo:
#        ans = ans%moddo
    
        
#print(dic)
#print(sum(dic.values()))
print(ans)

Submission status: Time Limit Exceeded

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

def gcd1_tuples(k):
    if gcd1_tuples.memo[k] != -1:
        return gcd1_tuples.memo[k]
    else:
        tmp = pow(k, N, mod)
        for j in range(2, k+1):
            tmp -= gcd1_tuples(k//j)
            tmp %= mod
        return tmp

gcd1_tuples.memo = [-1] * (K+1)
gcd1_tuples.memo[1] = 1

s = 0
for i in range(1, K+1):
    s += gcd1_tuples(K//i) * i
    s %= mod

print(s)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

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

dic = {} #ここに結果を保存していく。

for i in range(k):
    t = k - i #これで大きいほうから順にとる。
    if t > k/2:
        dic[t] = 1
    else:
        temp = math.floor(k/t)**n
        #print(temp)
        fac = 2
        while fac*t <= k:
            temp -= dic[fac*t]
            fac += 1
        dic[t] = temp
ans = 0
moddo = 10**9+7
for i in range(1,k+1):
    ans += i*dic[i]
    if ans >= moddo:
        ans = ans%moddo
    
        
#print(dic)
#print(sum(dic.values()))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
mod = 10**9+7
v = [0]*(k+1)
ans = 0
for i in range(k,0,-1):
    if v[i] == 0:
        v[i] = ((k//i)**n-sum(v[i::i])) % mod
        ans += v[i]*i
        ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
mod = 10**9+7
v = [0]*(k+1)
ans = 0
for i in range(k,0,-1):
    if v[i] == 0:
        v[i] = ((k//i)**n-sum(v[i::i])) % mod
for i in range(k+1):
    ans += v[i]*i
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

gcd1_tuples = [0] * (K+1)

for i in range(1, K+1):
    gcd1_tuples[i] = pow(i, N, mod)
    for j in range(2, i+1):
        gcd1_tuples[i] -= gcd1_tuples[i//j]
    gcd1_tuples[i] %= mod

s = 0
for i in range(1, K+1):
    s += gcd1_tuples[K//i] * i
    s %= mod

print(s)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
D=[0]*(K+1)
for i in range(1,K+1):
  a=K//i
  D[i]=a**N
ans=0
for i in range(K,0,-1):
  a=K//i
  for j in range(1,a+1):
    if j!=1:
      D[i]-=D[i*j]
  ans+=i*D[i]
  ans%=10**9+7
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
D=[0]*(K+1)
for i in range(1,K+1):
  a=K//i
  D[i]=a**N
ans=0
for i in range(K,0,-1):
  a=K//i
  for j in range(1,a+1):
    if j!=1:
      D[i]-=D[i*j]
  ans+=i*D[i]
  ans%=10**9+7
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

mod = 10**9+7

all_num = k**n
ans = 0

dp = [0]*(k+1)

for i in range(k):
    tmp = k-i
    #print(tmp)
    #print(tmp,tmp,tmp)
    kazu = 1
    kakeru = 2
    heru = 0
    #print(tmp,k)
    for i in range(k//tmp-1):
        #print(i)
        heru += dp[tmp*kakeru]
        kazu += 1
        kakeru += 1
    """
    while tmp * kakeru <= k:
        heru += dp[tmp*kakeru]
        kazu += 1
        kakeru += 1
        #print(tmp*kakeru,k)
    """ 
    
    if tmp == 1:
        ans += all_num
        ans %= mod
        break
    kazu = pow(kazu,n,mod)-heru
    #kazu = kazu**n-heru
    ans += tmp*(kazu)
    all_num -= (kazu)
    #print(tmp,kazu,n,heru)
    dp[tmp] = kazu
    ans %= mod
    #print(ans,tmp,kazu)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
[N,K] = [int(x) for x in input().split()]
l = [0 for i in range(K)]
for i in reversed(range(K)):
    m = int(K/(i+1))
    l[i] = (m**N)%(10**9+7)
    for j in range(2,m+1):
        l[i] -= l[(i+1)*j-1]
ans = 0
for i in range(K):
    ans += l[i]*(i+1)
    ans = ans%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
[N,K] = [int(x) for x in input().split()]
l = [0 for i in range(K)]
for i in reversed(range(K)):
    m = int(K/(i+1))
    l[i] = m**N
    for j in range(2,m+1):
        l[i] -= l[(i+1)*j-1]
ans = 0
for i in range(K):
    ans += l[i]*(i+1)
    ans = ans%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

mod = 10**9+7

all_num = k**n
ans = 0

dp = [0]*(k+1)

for i in range(k):
    tmp = k-i
    #print(tmp)
    #print(tmp,tmp,tmp)
    kazu = 1
    kakeru = 2
    heru = 0
    #print(tmp,k)
    while tmp * kakeru <= k:
        heru += dp[tmp*kakeru]
        kazu += 1
        kakeru += 1
        #print(tmp*kakeru,k)
        
    
    if tmp == 1:
        ans += all_num
        ans %= mod
        break
    ans += tmp*(kazu**n-heru)
    all_num -= (kazu**n-heru)
    #print(tmp,kazu,n,heru)
    dp[tmp] = kazu**n-heru
    ans %= mod
    #print(ans,tmp,kazu)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
H=[0]*(K+1)

ans=0
i=K
while i>=1:
    H[i]=(K//i)**N
    j=2
    while j*i<=K:
        H[i]-=H[j*i]
        j+=1
    ans+=H[i]*i
    i-=1

print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
N,K=map(int,input().split())
Ans=[1 for k in range(K)]
c=K
Ans[0]=pow(K,N,mod)
for k in range(2,(K+1)//2+1):
    d=K//k
    if c==d:
        Ans[k-1]=Ans[k-2]
    else:
        Ans[k-1]=pow(d,N,mod)
        c=d
for j in range(K,1,-1):
    for l in range(j//2,0,-1):
        if j%l==0:
            Ans[l-1]-=Ans[j-1]
for j in range(K):
    Ans[j]*=j+1
print(sum(Ans)%mod)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
N,K=map(int,input().split())
Ans=[1 for k in range(K)]
c=K
for j in range(N):
    Ans[0]=Ans[0]*(K)%mod
for k in range(2,(K+1)//2+1):
    d=K//k
    if c==d:
        Ans[k-1]=Ans[k-2]
    else:
        Ans[k-1]=pow(d,N,mod)
        c=d
for j in range(K,1,-1):
    for l in range(j//2,0,-1):
        if j%l==0:
            Ans[l-1]-=Ans[j-1]
for j in range(K):
    Ans[j]*=j+1
print(sum(Ans)%mod)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
N,K=map(int,input().split())
Ans=[1 for k in range(K)]
c=K
for j in range(N):
    Ans[0]=Ans[0]*(K)%mod
for k in range(2,(K+1)//2+1):
    d=K//k
    if c==d:
        Ans[k-1]=Ans[k-2]
    else:
        for j in range(N):
            Ans[k-1]=Ans[k-1]*d%mod
        c=d
for j in range(K,1,-1):
    for l in range(j//2,0,-1):
        if j%l==0:
            Ans[l-1]-=Ans[j-1]
for j in range(K):
    Ans[j]*=j+1
print(sum(Ans)%mod)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
mod = 10**9+7
result = 0
memo = [0 for _ in range(k+1)]
for i in range(k, 0, -1):
    z = 1
    y = k//i
    for j in range(n):
        z = (z*y)%mod
    j = 2
    while j*i <= k:
        z -= memo[j*i]
        j += 1
    memo[i] = z
    result = (result+z*i)%mod
print(result)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)
    def __int__(self):
        return self.x

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __mod__(self, other):
        return (
            ModInt(
                other.x
            ) if isinstance(other, ModInt) else
            other
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
    
    def __iadd__(self,other):
        self.x += other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self

    def __isub__(self,other):
        self.x += ModInt(MOD - other.x) if isinstance(other, ModInt) else ModInt(MOD - other)
        return self

    def __imul__(self, other):
        self.x *= other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self
    
    def factorical(self,n):
        tmp = ModInt(1)
        for i in range(n):
            tmp *= (i+1)
        return tmp
    
    #m:int MOD
    def modinv(self,a,m=MOD):
        b = m
        u = 1
        v = 0
        while(b):
            t = a//b
            a -= t * b
            a,b = b,a
            u -= t * v
            u,v = v,u
        return ModInt(u)

    def comb(self,n,r):
        n = int(n)
        r = int(r)
        if r > n or n < 0 or r < 0:
            return 0
        m = n+1
        nterms = min(r, n-r)
        numerator = ModInt(1)
        denominator = ModInt(1)
        for j in range(1, nterms + 1):
            numerator *= m - j
            denominator *= j
        return numerator * self.modinv(denominator.x)


if __name__ == "__main__":
    N, K = map(int,input().split())

    ans = ModInt(0)
    gcd_equal_i = [0]*(K+1) #gcd(A) == i なるAの作り方がgcd_equal_i[i]個

    for D in range(K, 0, -1):
        num_of_mul = K // D
        tmp = num_of_mul**N

        i = 2
        while D*i <= K:
            tmp -= gcd_equal_i[D*i]
            i += 1
        
        gcd_equal_i[D] = tmp


    for i in range(K+1):
        ans += i*gcd_equal_i[i]

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 +7

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

ans = 0
gcd_equal_i = [0]*(K+1) #gcd(A) == i なるAの作り方がgcd_equal_i[i]個

for D in range(K, 0, -1):
    num_of_mul = K // D
    tmp = num_of_mul**N

    i = 2
    while D*i <= K:
        tmp -= gcd_equal_i[D*i]
        i += 1
    
    gcd_equal_i[D] = tmp
    ans += D*tmp
    ans %= MOD


print(ans)

Submission status: Time Limit Exceeded

Solution code:
#original submission: https://atcoder.jp/contests/abc162/submissions/11865868

MOD = 10**9 +7

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

ans = 0
gcd_equal_i = [0]*(K+1) #gcd(A) == i なるAの作り方がgcd_equal_i[i]個

for D in range(K, 0, -1):
    num_of_mul = K // D
    tmp = num_of_mul**N

    i = 2
    while D*i <= K:
        tmp -= gcd_equal_i[D*i]
        i += 1
    
    gcd_equal_i[D] = tmp
    ans += D*tmp
    ans %= MOD


print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
s = 10**9 + 7
t = K // 2

T = [1]*K

ans = 0
for i in range(t):
    i = t - i -1
    T[i] = (K // (i+1))**N % s
    j = 2
    while (i+1)*j < K+1:
        T[i] = (T[i]- T[(i+1)*j-1]) % s
        j += 1
    ans += T[i]*(i+1) %s

ans = (ans + (K+t+1)*(K-t)//2) % s

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

import numpy as np
M = int(10**9)+7
n,k = [int(c) for c in input().split()]
nums = [0]*(k+1)
nums = np.zeros((k+1), dtype=int)
for i in range(k, 0, -1):
    tmp = ((k // i) ** n) % M
    tmp -= nums[(2*i)::i].sum()
    nums[i] += tmp
    
# print(sum((i)*nums[i]%M for i in range(len(nums)))%M)
print((np.arange(k+1) * nums).sum()%M)

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces

n, K = na()


eqi = [0 for i in range(K)]#eqi[i] = (gcd(A_1,A_2,...,A_N) = i となる組の数)

for i in range(K,0,-1):
    if i == 1:
        eqi[i-1] = K**n - sum(eqi)
        break
    #A_1,A_2,...,A_Nのすべてがiの倍数になる組の数
    tmp = (K//i)**n
    #A_1,A_2,...,A_Nのすべてがm*iの倍数になる組の数を引く(n = {2,3,4,...})
    for m in range(2,(K//i)+1):
        tmp -= eqi[m*i - 1]
    eqi[i-1] = tmp%(10**9 + 7)
ans = 0
for i in range(K):
    ans += ((i+1)*eqi[i])%(10**9 + 7)
print(ans%(10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
M = int(10**9)+7
n,k = [int(c) for c in input().split()]
nums = [-1]*(k+1)
for i in range(k, 0, -1):
    tmp = ((k // i) ** n) % M
    tmp -= sum(nums[(2*i)::i])
    nums[i] = tmp
print(sum((i)*nums[i]%M for i in range(len(nums)))%M)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split(' '))
mod =10**9+7
dp=[pow(K//i,N,mod) for i in range(1,K+1)]
for i in range(K,1,-1):
    tmp=[1]
    for j in range(2,int(pow(i+1,0.5))+1):
        if i%j==0:
            tmp.append(j)
            if i != j*j:
                tmp.append(i//j)
    for k in tmp:
        dp[k-1] -=dp[i-1]
ans = 0
for n,i in enumerate(dp):
    ans += (n+1)*i
    ans %=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
li = [0 for _ in range(K)]

mod = 10**9+7
ans = 0
for i in range(K,0,-1):
    mm = K//i
    mm = mm**N

    for j in range(2,(K//i)+1):
        mm -= li[i*j-1]    
    li[i-1] = mm


    ans += i*mm
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7

memo = [0] * (K + 1)
ans = 0
for i in range(K, 0, -1):
    tmp = (K // i) ** N
    j = 2
    while i * j <= K:
        tmp -= memo[i * j]
        j += 1
    memo[i] = tmp
ans = 0
for i in range(1, K+1):
    ans += (memo[i] * i) % mod
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

    ans = 0
    memo = [0] * (K+1)
    def getLarge(x):
        if x == 1:
            return sum(memo)
        else:
            return sum(memo[x::x])

    for i in range(K, 0, -1):
        Ki = K // i
        c = Ki ** N - getLarge(i) % MOD
        memo[i] = c
        ans += i * c
        ans %= MOD
    print(ans % MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

    ans = 0
    memo = [0] * (K+1)
    def getLarge(x):
        if x == 1:
            return sum(memo)
        else:
            return sum(memo[x::x])

    for i in range(K, 0, -1):
        Ki = K // i
        c = Ki ** N - getLarge(i)
        memo[i] = c
        ans += i * c % MOD
    print(ans % MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp = [0] * (K + 1)
ans = 0
for k in range(K, 0, -1):
    num = K // k
    dp[k] = pow(num, N)
    for n in range(2, num+1):
        if n*k <= K:
            dp[k] -= dp[n*k]
            dp[k] %= MOD

    ans += dp[k] * k % MOD
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7


def mod_pow(m, p):
    if p == 1:
        return m % mod
    return (mod_pow(m, p // 2) % mod) * (mod_pow(m, p - p // 2) % mod)


n, k = map(int, input().split())
gcd_dp = [0] * (k + 1)

for i in range(k, 0, -1):
    gcd_dp[i] = mod_pow(k // i, n)
    a = 2
    while i * a <= k:
        gcd_dp[i] -= gcd_dp[i * a]
        a += 1

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

n, k = map(int, input().split())
gcd_dp = [0] * (k + 1)

for i in range(k, 0, -1):
    gcd_dp[i] = (k // i) ** n
    a = 2
    while i * a <= k:
        gcd_dp[i] -= gcd_dp[i * a]
        a += 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)

div_cache = {}
def primes(N):
    if N in div_cache:
        return div_cache[N]
    ret = set()
    for i in range(1, min(int(pow(N, 0.5) + 1), N)):
        if N % i == 0:
            ret.add(i)
            if i != 1:
                ret.add(N // i)
    div_cache[N] = ret
    return ret


cache = {}
def solve(N, K):
    M = pow(10, 9) + 7
    ans = 0
    for i in range(1, K + 1):
        P = pow(K // i, N, M)
        ans += i * P

        affect = {}
        def past(p, sign):
            nonlocal ans
            prim = primes(p)
            for p in prim:
                affect.setdefault(p, 0)
                affect[p] += p * sign
                if p != 1:
                    for k, v in cache[p].items():
                        affect.setdefault(k, 0)
                        affect[k] -= v

        past(i, -1)
        cache[i] = affect
        for v in affect.values():
            ans += v * P
            ans %= M

        ans %= M
    return ans

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    print(solve(N, K))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
s = 10**9 + 7
t = K // 2

T = [1]*K

for i in range(t):
    i = t - i -1
    T[i] = (K // (i+1))**N % s
    j = 2
    while (i+1)*j < K+1:
        T[i] = (T[i]- T[(i+1)*j-1]) % s
        j += 1

ans = 0
for i in range(K):
    ans = (ans + (i+1)*T[i]) % s

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)

div_cache = {}
def primes(N):
    if N in div_cache:
        return div_cache[N]
    ret = set()
    for i in range(1, min(int(pow(N, 0.5) + 1), N)):
        if N % i == 0:
            ret.add(i)
            if i != 1:
                ret.add(N // i)
    div_cache[N] = ret
    return ret



def slowsolve(N, K):
    import itertools
    import math
    data = {}
    s = 0
    KK = [i for i in range(1, K + 1)]
    for p in itertools.product(KK, repeat=N):
        cdi = p[0]
        for c in p:
            cdi = math.gcd(cdi, c)
        s += cdi
        data.setdefault(cdi, 0)
        data[cdi] += 1
    print(data)
    return s


def solve(N, K):
    M = pow(10, 9) + 7
    ans = 0
    for i in range(1, K + 1):
        P = pow(K // i, N, M)
        ans += i * P

        def past(prim, sign):
            nonlocal ans
            ans += sum(prim) * P * sign
            ans %= M
            for p in prim:
                if p != 1:
                    past(primes(p), sign * -1)

        past(primes(i), -1)
        ans %= M
    return ans


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    print(solve(N, K))

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split()))
l = [0 for i in range(k)]
ans = 0
M = 10**9 + 7

def dev(n):
    dl = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            dl.append(i)
            if i != n // i:
                dl.append(n//i)
    dl.sort()
    return dl

for i in range(k, 0, -1):
    a=k//i
    b=a**n
    l[i-1] += b
    d=dev(i)
    for m in d:
        if m != i:
            l[m-1] -= l[i-1]

for i in range(1, k+1):
    ans+=i*l[i-1]

print(ans%M)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=[0 for _ in range(k)]
res=0
mod=1000000007
for i in range(k):
  g=k-i
  if g*2>k:
    a[g-1]=1
    res+=1
  elif g!=1:
    cnt=(k//g)**n
    for j in range(g*2,k+1,g):
      cnt-=a[j-1]
    a[g-1]=cnt
    res+=cnt
  elif g==1:
    a[0]=k**n-res
ans=0
for i in range(k):
  ans+=a[i]*(i+1)
  if ans>=mod:
    ans%=mod



#print(a)
print(ans)