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: Accepted

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, divide)
  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: Accepted

Solution code:
N, K = map(int, input().split())
mod = 10 ** 9 + 7
G = [1] * (K + 1)  #そのindexを最大公約数にもつ数列の数
ans = 0
for k in range(K, 0, -1):
    x = K // k
    t = int(pow(x, N, mod))
    for j in range(x - 1):
        t -= G[(j + 2) * k]
    G[k] = t
    ans += t * k
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
mod = int(1e9+7)
d = dict()
ans = 0
for X in range(K,0,-1):
  res = pow(K//X,N,mod)
  for k in range(2*X,K+1,X):
    res -= d[k]
  d[X] = res%mod
  ans += (res*X)%mod
  
print(ans%mod)

Submission status: Accepted

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

a = [0] *(k+1)

for x in range(1, k + 1):
    a[x] = pow(k // x, n, MOD)

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

answer = sum([i * x for i,x in enumerate(a)])

print(answer % MOD)

Submission status: Accepted

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

dp = [0 for _ in range(K + 1)]
res = 0

for i in range(1, K + 1)[::-1]:
    dp[i] += pow(K // i, N, MOD)
    for j in range(1, K // i):
        dp[i] -= dp[i * (j + 1)]
    res += i * dp[i]
    res %= MOD

print(res)

Submission status: Accepted

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

mod = 10 ** 9 + 7

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x % mod
        x = x * x % mod
        n //= 2

    return K * x % mod


memo = {}
ans = 0

for x in reversed(range(1, k + 1)):
    memox = pow_k((k // x), n)
    for i in range(2, k // x + 1):
        memox -= memo[i * x]
        memox %= mod
    memo[x] = memox
    ans += x * memox % mod
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
mod = 1000000007
ko = [0]*100005
ans = 0
for i in range(k,0,-1):
    baisu = k//i
    ko[i] = pow(baisu,n,mod)
    for j in range(2,baisu+1):
        ko[i] -= ko[i*j]
        ko[i] %= mod
    ans += ko[i] * i % mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#MLE注意！

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def modpow(a, n, mod):
    ans = 1
    while n > 0:
        if n&1:
            ans = ans * a % mod
        a = a * a % mod
        n = n >> 1
    return ans
for x in range(K,0, -1):
    a = int((K // x) % mod)
    b = modpow(a, N, mod)
    for i in range(2, K//x +1):
        b = (b - lis[x*i-1]) %mod
        if b < 0:
            b += mod
    lis[x-1] = b
    ans = (ans + b*x%mod) % mod
print(int(ans))

Submission status: Accepted

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

a = [1] * (k+1)
b = [ i for i in range(k+1) ]

for i in range(k//2,0,-1):
  cnt = pow( k // i , n, mod )
  for j in range(i*2,k+1,i):
    cnt = ( cnt - a[j] ) % mod
  a[i] = cnt
  b[i] = i * cnt % mod

ans = 0
for i in range(1,k+1):
  ans += b[i]
  if ans >= mod:
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
n, k = (int(x) for x in input().split())
c = {} 
t = 0
MOD = 1000000007
for x in range(k, 0, -1):
    q = k // x
    c[x] = pow(q, n, MOD) - sum(c[x * y] for y in range(2, q + 1))
    t += c[x] * x
    t = t % MOD
print(t)

Submission status: Accepted

Solution code:
n, k = (int(x) for x in input().split())
c = {} 
t = 0
MOD = 1000000007
for x in range(k, 0, -1):
    q = k // x
    c[x] = pow(q, n, MOD) - sum(c[x * y] for y in range(2, q + 1))
    t += c[x] * x
    t = t % 1000000007
print(t)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

c = [0] * (K + 1)
for i in range(K, 0, -1):
    t = pow(K // i, N, MOD)
    for j in range(2, K // i + 1):
        t -= c[i * j]
        t %= MOD
    c[i] = t

result = 0
for i in range(1, K + 1):
    result += c[i] * i
    result %= MOD
print(result)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

cache = {1: 1}
def f(k, n):
    if k in cache:
        return cache[k]
    result = pow(k, n, MOD)
    for i in range(2, k + 1):
        result -= f(k // i, n)
        result %= MOD
    cache[k] = result
    return result


result = 0
for i in range(1, K + 1):
    result += f(K // i, N) * i
    result %= MOD
print(result)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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

A = [0] + [pow(K // x, N, mod) for x in range(1, K + 1)]
for x in reversed(range(1, K + 1)):
    for i in range(2, K // x + 1):
        A[x] -= A[i * x]

print(sum(i * a for i, a in enumerate(A)) % mod)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

cache = {}
def f(k, n):
    if k == 1:
        return 1
    if k in cache:
        return cache[k]
    result = pow(k, n, MOD)
    for i in range(2, k + 1):
        result -= f(k // i, n)
        result %= MOD
    cache[k] = result
    return result


result = 0
for i in range(1, K + 1):
    result += f(K // i, N) * i
print(result % MOD)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

cache = {}
def f(k, n):
    if k == 1:
        return 1
    if k in cache:
        return cache[k]
    result = pow(k, n, MOD)
    for i in range(2, k + 1):
        result -= f(k // i, n)
        result %= MOD
    cache[k] = result
    return result


print(sum(f(K // i, N) * i for i in range(1, K + 1)) % MOD)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

cache = {}
def f(k, n):
    if k == 1:
        return 1
    if k in cache:
        return cache[k]
    result = pow(k, n, MOD)
    for i in range(2, k + 1):
        result -= f(k // i, n)
        result %= MOD
    cache[k] = result
    return result


result = 0
for i in range(1, K + 1):
    result += f(K // i, N) * i
    result %= MOD
print(result)

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 10 ** 9 + 7

cache = {}
def f(k, n):
    if k == 1:
        return 1
    if k in cache:
        return cache[k]
    result = pow(k, n, MOD)
    for i in range(2, k + 1):
        result -= f(k // i, n)
        result %= MOD
    cache[k] = result
    return result

result = 0
for i in range(2, K + 1):
    result += f(K // i, N) * i
result += f(K, N)
result %= MOD
print(result)

Submission status: Accepted

Solution code:
import math

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

cnt = [0]*(k+1)

for i in range(1, k+1):
    cnt[i] = pow(k//i, n, mod)

for i in range(k+1, 0, -1):
    j = 2
    while i*j <= k:
        cnt[i] -= cnt[i*j]
        cnt[i] %= mod
        j += 1

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import math

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

cnt = [0]*(k+1)

for i in range(1, k+1):
    cnt[i] = pow(math.floor(k/i), n, mod)

for i in range(k+1, 0, -1):
    j = 2
    while i*j <= k:
        cnt[i] -= cnt[i*j]
        cnt[i] %= mod
        j += 1

ans = 0

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

print(ans)

Submission status: Accepted

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

gcd = {}
s = 0

for x in range(K,0,-1):
  
    i = K // x
    tmp = pow(i,N,mod)  # 組み合わせ数
    
    if i > 1:
        for j in range(2,i+1):
            tmp -= gcd[j * x]
    
    gcd[x] = tmp
    s += (tmp * x) % mod
    s %= mod

print(s)

Submission status: Accepted

Solution code:
import sys
#import copy
#import numpy as np
#import itertools
#import collections
#from collections import deque
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
import functools

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

mod = 1000000007

def gcd(nums):
    return functools.reduce(euclid, nums)

def euclid(a, b):
    if b > a:
        a, b = b, a
    if b == 0:
        return a
    else:
        return euclid(b, a%b)

def main():
    # input
    N, K = map(int, readline().split())

    ans = 0
    count = [0] * K
    for X in range(K,0,-1):
        #tmp = ((K // X) ** N) % mod
        tmp = pow(K//X, N, mod)
        diff = count[X-1::X][1:]
        if len(diff) != 0:
            tmp = (tmp - sum(diff)) % mod
        count[X-1] = tmp

    ans = sum([((x+1)*count[x])%mod for x in range(K)])%mod
    #for X in range(K):
    #    ans = (ans + (X+1) * count[X]) % mod

    #print("end")
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
ans=0
xs=[0]*k
mod=10**9+7
for i in range(k-1,-1,-1):
    a=i+1
    xs[i]=pow(k//a,n,mod)
    for j in range(2,k+1):
        if a*j>k:
            break
        xs[i]-=xs[a*j-1]
        xs[i]=(xs[i]+mod)%mod

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

Submission status: Accepted

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

A = list(0 for _ in range(K + 1))
B = list(0 for _ in range(K + 1))

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

for i in range(K, 0, -1):
    a = 0
    for j in range(i * 2, K + 1, i):
        a += B[j]
    B[i] = A[i] - a
    B[i] %= MOD

for i in range(K + 1):
    ans += B[i] * i % MOD
    ans %= MOD
                       
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 10**9+7
arr = [pow(K//i, N, MOD) for i in range(1,K+1)]

for i in range(K//2,0,-1):
    arr[i-1] -= sum(arr[2*i-1:K:i]) % MOD
    arr[i-1] %= MOD
    
arr = [(i+1)*j%MOD for i,j in enumerate(arr)]

print(sum(arr)%MOD)

Submission status: Accepted

Solution code:
#ABC162-E Sum of gcd of Tuples(Hard)
"""
問題を「1~kまでの数字を用いた長さnの数列において、gcdがDになる数列はいくつあるか」
というふうに置き換える。(1<=D<=k)
更に制約を替えて、gcdが"Dの倍数"(但し,k以下)でも良いのでそれを全て求めよ、
というふうになった場合、全ての要素はD*n(nは整数,D*n<=k)となる。
この制約によって、そのような数列の数は(k/D)^nとして表せる。(これが大事)
例：
n = 3,k = 4の場合で、D(gcd)=2について求める
(4//2)**3 = 8※

そこで、大きい方からgcdがDになる数列の個数(これをメモ化)を求めていった場合、
Dの倍数がk以下であるならば、予めメモしておいたその値分を引いてやる。
これによって全ての通り数が求まる。
例の続き:
D=2について、D*n <= k という制約のもとでn=2が存在する。
D = 2*2 = 4の時の通り数は、4,4,4の1通り※なので、
D(gcd)=2となるパターン数は、※より、
8-1=7 となる。
(この7通りは2と4からなる数列で、全ての値が4になる場合を引いている)
"""
import sys
readline = sys.stdin.buffer.readline
n,k = map(int,readline().split())
mod = 10**9+7

ans = 0
count = [0]*(k+1)
for D in range(k,0,-1):
    mul = k//D #何倍まであり得るか(あり得るものをcountから引く)
    res = pow(mul,n,mod)
    for i in range(2,mul+1):
        res -= count[i*D]
    count[D] = res #個数
    ans += res*D #個数*値(求めたいのはgcdの合計値のため)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
mod = 10**9+7
arr = [0]*(k+1) ##arr[i]はgcdがiの個数
for i in range(k,0,-1):
    l = k//i
    arr[i] = pow(l,n,mod)
    for j in range(2,l+1):
        arr[i] -= arr[i*j]
        arr[i] %= mod
ans = 0
for i,a in enumerate(arr):
    ans+=i*a
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
INF=10**9+7
l=[0]*k
ans=0
for i in range(k-1,-1,-1):
    x=i+1
    temp=pow(k//x,n,INF)
    for j in range(2,k//x+1):
        temp=(temp-l[j*x-1])%INF
    l[i]=temp
    ans=(ans+x*temp)%INF
print(ans)

Submission status: Accepted

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)]
exactly=[0]*k
for i in range(k,0,-1):
    f=0
    for j in range(2*i,k+1,i):
        f+=exactly[j-1]
    exactly[i-1]=dp[i-1]-f
    exactly[i-1]%=mod
print(sum(i*exactly[i-1]%mod for i in range(1,k+1))%mod)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
l = [0 for i in range(k + 1)]
ans = 0
mod = 1000000007
for i in range(k, 0, -1):
    l[i] = pow(k // i, n, mod)
    tmp = 2 * i
    while tmp <= k:
        l[i] -= l[tmp]
        tmp += i
for i in range(k + 1):
    ans += i * l[i]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
MOD = 10**9+7
# g[i]:gcd(A1,A2,,,An)=iとなる数列の個数
g = [0 for _ in range(k)]
for i in range(k,0,-1):
  g[i-1] = pow(k//i,n,MOD)
  #ここまででg[x]=gcdがxの倍数となる数列の個数となっているので、
  #ここからgcdが2x,3x,,,となる数列の個数を引いていく。
  for j in range(2,k+1):
    if i*j > k:
      break
    g[i-1] -= g[i*j-1]
    g[i-1] %= MOD
#print(g)
ans = 0
for i in range(k):
  ans += (i+1)*g[i]
  ans %= MOD
print(ans)

Submission status: Accepted

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

# 最大公約数がその数になる組合せで場合わけ、後ろから埋めて重複を引く
for i in range(k,0,-1):
    m=k//i
    x[i]=pow(k//i,n,mod)
    for j in range(1,m):
        x[i]-=x[i*(j+1)]
        x[i]%=mod

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

print(ans)

Submission status: Accepted

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

cnt = [0] * (K + 1) # 要素が全てXの倍数となるような数列の個数をXごとに求める
for x in range(1, K + 1):
    cnt[x] = pow(K // x, N, MOD)
for x in range(K, 0, -1): # 2X, 3Xの個数を求めてひく
    for i in range(2, K // x + 1):
        cnt[x] -= cnt[x * i]
ans = 0
for k in range(K+1):
    ans += cnt[k] * k
ans = ans % MOD
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
res = [0]*(K+1)
ans = 0
MOD = 10**9+7
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)
    return divisors

for k in range(K,0,-1):
    y = make_divisors(k)
    s = K//k
    tmp = pow(s, N, MOD)
    val = tmp-res[k]
    ans += k*val
    for yy in y:
        res[yy] += val
print(ans%MOD)

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	#a = int(input())
	k, n = IN()
	#s = input()
	bb=[0]*n
	for i in range(n,0,-1):
		pattern = pow((n//i), k, mod)
		for b in range(2, n+1):
			if (i * b)-1 >= n:
				break
			pattern -= bb[(i*b)-1]
			pattern %= mod
		bb[i-1]=pattern
	ret=0
	#print(bb)
	for i, v in enumerate(bb):
		ret += v*(i+1)
		ret %=mod
	return ret
		
		
		
	
	
	ret=pow(b,c,mod)
	print(ret)
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

def pow_mod(a, n):
    if n == 1:
        return a
    half = pow_mod(a, n // 2)
    if n % 2 == 1:
        ret = half * a % MOD
        ret = ret * half % MOD
    else:
        ret = half * half % MOD
    return ret

ans_dict = dict()
for g in range(k, 0, -1):
    ans_dict[g] = pow_mod(k // g, n)
    for i in range(2, k + 1):
        if g * i <= k:
            ans_dict[g] -= ans_dict[g * i]
            if ans_dict[g] < 0:
                ans_dict[g] += MOD
            elif ans_dict[g] > g:
                ans_dict[g] -= MOD
        else:
            break

ans = 0
for g, v in ans_dict.items():
    ans += g * v
    ans %= MOD

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# n^p(mod m) -- START --
def powMod(n,p,m):
  if p==0:
    return 1
  if p%2==0:
    t=powMod(n,p//2,m)
    return t*t%m
  return n*powMod(n,p-1,m)%m
# n^p(mod m) --- END ---

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

  ret=0
  # print(ans)
  for i,x in enumerate(ans):
    ret+=x*i
    ret%=mod
  return ret

# main()
print(main())

Submission status: Accepted

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

cnt = [0] * (k + 1)
for num in range(1, k + 1):
    cnt[num] = pow((k // num), n, MOD)

for num in range(1, k + 1)[::-1]:
    for i in range(2, k // num + 1):
        cnt[num] -= cnt[num * i]
        cnt[num] % MOD

ans = 0
for num in range(1, k + 1):
    ans += cnt[num] * num
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# a = [sys.stdin.readline() for s in range(n)]
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
# d = collections.defaultdict(list)
# h = list() heapify(h)
import math
from functools import reduce
import sys
sys.setrecursionlimit(15000)

n,k = map(int,sys.stdin.readline().split())
dp = [0]*(k+1)
s = 0
#print("nk:",n,k)
l = 0
for x in range(1,k+1)[::-1]:
    dp[x] = pow(k//x,n,1000000007)
    j = 2
    #print(2*x,k+1,x)
    for j in range(2*x,k+1,x):
        #print("j",x,j,k,n)
        dp[x] -= dp[j]
    s = (s + (dp[x]*x))%1000000007
#return reduce(math.gcd, numbers)
#sum += gcd(a,b,c)
#print(sum(dp[n-1][j] for j in range(k)))
#print(dp)
print(s)

Submission status: Accepted

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

mx = [0]*(K+1)
ans = 0

for i in range(K, 0, -1):
    mx[i] = pow(K//i, N, MOD)
    for j in range(2*i, K+1, i):
        mx[i] -= mx[j]
    ans += i*mx[i]

print(ans%MOD)

Submission status: Accepted

Solution code:
MODINT = 10**9 + 7

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

ans = 0
q = [0] * (K + 1)

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

Submission status: Accepted

Solution code:
#メモ化再帰以外は実装が厳しい

n,k = map(int, input().split( ))
memo = [-1]*(k+1)
mod = 10**9+7
def rec(x):
    if memo[x]>=0:
        return memo[x]
    mult = 0
    for i in range(x*2,k+1,x):
        mult += rec(i)
    res = memo[x] = pow(k//x,n,mod) - mult
    return res
ans = 0
rec(1)
for i in range(1,k+1):
    ans += i*memo[i]
print(ans%mod)

Submission status: Accepted

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

ans = 0

"""
dp[i] =　gdc がi となる場合のgcdの総和
"""
dp = [0] * (k+100)
for i in range(k, 0, -1):
    dp[i] = pow(k//i, n, MODINT)
    for j in range(i*2, k+1, i):
        dp[i] -= dp[j]
    ans += (dp[i]*i)%MODINT
print(ans%MODINT)

Submission status: Accepted

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

MOD = 1000000007  # type: int


def solve(N: int, K: int):
    counts = [0] * (K+1)
    for i in range(K, 0, -1):
        c = pow(K//i, N, MOD)
        for j in range(i+i, K+1, i):
            c -= counts[j]
        counts[i] = c
    ans = 0
    for i, c in enumerate(counts):
        ans = (ans + (i * c) % MOD) % MOD
    print(ans)


# 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: Accepted

Solution code:
n, k = list(map(int, input().split()))
mod = int(1e9 + 7)

q = [0] * (k + 1)
for i in range(1, k+1)[::-1]:
    q[i] = pow(k//i, n, mod)
    for j in range(2, k // i + 1):
        if i * j > k:
            continue
        q[i] -= q[i * j]
s = 0
for i, qq in enumerate(q):
    s += i * qq
    s %= mod
print(s)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    r = 0
    D = [0] * (K + 1)
    for i in reversed(range(1, K + 1)):
        D[i] = pow(K // i, N, mod) - sum(D[::i])
    return sum(i * j for i, j in enumerate(D)) % mod

print(main())

Submission status: Accepted

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

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

    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: Accepted

Solution code:
import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    d = {}
    r = 0
    for i in range(K, 0, -1):
        l = make_divisors(i)
        x = K // i
        t = pow(x, N, mod)
        if i in d:
            t -= d[i]
        for j in l:
            if j not in d:
                d[j] = t
            else:
                d[j] += t
        r += t * i
        r %= mod
    return r % mod
print(main())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# E - Sum of gcd of Tuples (Hard)

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

for x in range(k, 0, -1):
    #X[x] = ((k//x)**n)%mod
    X[x] = pow(k//x, n, mod)
    for x_multi in range(x*2, k+1, x):
        X[x] -= X[x_multi]

print(sum((i*x)for i, x in enumerate(X))%mod)

Submission status: Accepted

Solution code:
def ff(n):
    i = 1
    r = set()
    while i * i <= n:
        if n % i == 0:
            r.add(i)
            if i != n // i:
                r.add(n // i)
        i += 1
    return sorted(r)

def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    T = [[] for _ in range(K + 1)]
    F = [ff(i) for i in range(K + 1)]
    for i, f in enumerate(F[1:], 1):
        for j in f:
            T[j].append(i)
    r = 0
    t = [0] * (K + 1)

    for i in reversed(range(1, K + 1)):
        q = (pow(len(T[i]), N, mod) - t[i]) % mod
        for j in F[i][:-1]:
            t[j] = (t[j] + q) % mod
        r = (r + i * q) % mod

    return r

print(main())

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
x = [0]*k
mod = 10**9+7
def power(a,n):
  ans = 1
  while n:
    if n%2:
      ans = (ans*a)%mod
    a = (a*a)%mod
    n >>= 1
  return ans%mod  
for i in range(k,0,-1):
  c = power(k//i,n)
  j = 2
  while i*j <= k:
    c -= x[i*j-1]
    j += 1
  x[i-1] = c
s = 0
for i in range(1,k+1):
  s = (s + i*x[i-1])%mod
print(s)

Submission status: Accepted

Solution code:
n,k=[int(x) for x in input().split()]
ans=0
l=[0]*(k+1)
i=k
mod=1000000007
while i>0:
    l[i]=pow(k//i,n,mod)
    j=2*i
    while j<=k:
        l[i]=(l[i]-l[j]+mod)%mod
        j+=i
    i-=1
for i in range(1,k+1):
    ans+=(l[i]*i)%mod
print(ans%mod)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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])
    return arr


n,k = get_nums_l()
MOD = 10**9+7

ans = 0
count = [0] * (k+1)
for x in range(k, 0, -1):
    count[x] = pow((k//x),n,MOD)

    for y in range(x*2, k+1, x):
        count[x] -= count[y]

print(sum([ x*i for i,x in enumerate(count) ]) % MOD)

Submission status: Accepted

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

for gcd in range(1, k + 1):
    cnt[gcd] = pow(k // gcd, n, MOD)

for gcd in range(k, 0, -1):
    for i in range(2, k // gcd + 1):
        cnt[gcd] -= cnt[gcd * i]

ans = sum([num * c for num, c in enumerate(cnt)]) % MOD
print(ans)

Submission status: Accepted

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

for i in range(K, 1, -1):
    cnt[i] = pow(K//i, N, MOD)
    
    for j in range(2*i, K+1, i):
        cnt[i] -= cnt[j]
        cnt[i] %= MOD
    
    ans += i*cnt[i]

ans += pow(K, N, MOD)-sum(cnt[2:])
ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, K = MAP()

mod = 10**9+7

cnt = [0]*K


for i in reversed(range(1, K+1)):
    a = pow(K//i, N, mod)
    cnt[i-1] = a

    b = 2
    while b*i <= K:
        cnt[i-1] -= cnt[b*i-1]
        b += 1

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

print(ans % mod)

Submission status: Accepted

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

out = 0
mod = 10**9+7

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
MOD = 10 ** 9 + 7
cnt = [0] * (K + 1)
for x in range(1, K + 1):
  cnt[x] = pow(K // x , N , MOD)

for x in range(K, 0, -1):
  for i in range(2, (K // x) + 1):
    cnt[x] -= cnt[x * i]
  #被りを消さなきゃいけない
ans = 0
for x in range(1, K + 1):
  ans += cnt[x] * x
print(ans % MOD)

Submission status: Accepted

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

out = 0
mod = 10**9+7

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

Submission status: Accepted

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

MOD = 10**9 + 7
A = [0] * (K + 1)

# 最大公約数がdの倍数の個数
for d in range(1, K + 1):
    A[d] = pow(K // d, N, MOD)

# ちょうどdになるためには
for d in range(K, 0, -1):
    # 2d,3d,...を引く
    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 status: Accepted

Solution code:
import math
N,K= map(int, input().split())
a=[0]*(K+1)
co=0
mod=(10**9+7)
for i in range(K,0,-1):

    b=K//i
    t=2*i
    m=0
    while t<=K:
        m=m+a[t]
        t+=i
    c=pow(b,N,mod)
    a[i]=c-m
    co+=(a[i]*i)%mod


print(co%mod)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
lst = [0] * (K + 1)
ans = 0
for i in range(K, 0, -1):
    tmp = K // i
    tmp = pow(tmp, N, MOD)
    for j in range(2 * i, K + 1, i):
        tmp -= lst[j]
    ans += (i * tmp)
    ans %= MOD
    lst[i] = tmp

print (ans)

Submission status: Accepted

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 = pow(num,n,mod)
    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: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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