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())
gcds = []


def power_func(a,n,p):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res

mod = 10**9+7
for i in range(k):
    div = k//(k-i)
    count = power_func(div,n, mod)
    for j in range(1,div):
        count = count - gcds[k-((k-i)*(j+1))]
    gcds.append(count)

total = 0

for i in range(k):
    total = (total + (gcds[i]*(k-i)%mod))%mod
print(total)

Submission status: Accepted

Solution code:
def f1(n):
    divs = []
    for i in range(1, int(n ** 0.5) + 1):  # range(n, int(n ** 0.5) - 1, -1)とすると非常に遅い！！
        if n % i == 0:
            divs.append(i)
            j = n // i
            if i != j:
                divs.append(j)
    return divs


MOD = 10 ** 9 + 7

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

X = [0] * (K + 1)

for i in range(K, 0, -1):
    num1 = K // i
    var = pow(num1, N, MOD)
    var -= X[i]
    ans += var * i
    ans %= MOD

    divs = f1(i)
    for d in divs:
        X[d] += var
        X[d] %= MOD
    

print(ans)

Submission status: Accepted

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):
    y = k//i
    z = pow(y, n, mod)
    j = 2
    while j*i<=k:
        z -= memo[j*i]
        z %= mod
        j += 1
    memo[i] = z
    result = (result+z*i)%mod
print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!python3

MOD = 10 ** 9 + 7

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


def modpow(x, y):
    res = 1
    while y > 0:
        if y & 1:
            res = res * x % MOD
        x = x * x % MOD
        y >>= 1
    return res


def solve(w, x):
    s = 0
    n = K // x
    for i in range(n, 1, -1):
        y = x * i
        if w[y] == 0:
            solve(w, y)
        s = (s + w[y]) % MOD
    w[x] = modpow(n, N) - s


def main():
    w = [0] * (K + 1)
    for i in range(2, K + 1):
        if w[i]:
            continue
        solve(w, i)
    w[1] = modpow(K, N) - sum(w[2:]) % MOD
    
    ans = 0
    for i in range(1, K + 1):
        ans = (ans + w[i] * i) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
##################################
# University of Wisconsin-Madison
# Author: Yaqi Zhang
##################################
# This module contains ...
##################################

# standard library
import sys
sys.setrecursionlimit(10**9)

MOD = int(1e9 + 7)


def main():
    """1~K"""
    n, k = map(int, input().split())
    dp = [-1] * (k + 1)
    # gcd == i
    for x in range(k, 0, -1):
        cnt = k // x
        if cnt == 1:
            dp[x] = 1
        else:
            dp[x] = pow(cnt, n, MOD)
            for i in range(2, cnt + 1):
                dp[x] = (dp[x] - dp[x * i]) % MOD
    ans = 0
    for i in range(1, k + 1):
        ans = (ans + i * dp[i]) % MOD
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
MOD=int(1e9)+7
dp=[0]*(K+1)
for ii in range(K):
    i=K-ii
    dp[i]+=pow(K//i,N,MOD)
    j=2*i
    while j<=K:
        dp[i]=(dp[i]-dp[j]+MOD)%MOD
        j+=i
ans=0
for i in range(1,K+1):
    ans+=dp[i]*i
    ans%=MOD
print(ans)

Submission status: Accepted

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

def f(n):
  if n == 1:
    return 1
  else:
    a = n
    m = n
    for i in range(2,math.floor(math.sqrt(n))+1):
      if m % i == 0:
        a = a*(i-1)//i
        while m % i == 0:
          m = m // i
        if m == 1:
          break
    if m != 1:
      return a*(m-1)//m
    else:
      return a
      
    
ans = 0  
for i in range(1,K+1):
  ans = (ans + (pow(K//i,N,mod)*f(i))) % mod

print(ans)

Submission status: Accepted

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

M = int(K ** .5)
f_l = [0] * (M+1)  # f(k)
f_h = [0] * (M+1)  # f(K//d)

def f(k):
  return f_l[k] if k <= M else f_h[K//k]

def compute_f(k):
  x = pow(k, N, MOD)
  sq = int(k ** .5)
  for d in range(2, k+1):
    n = k // d
    if n <= sq:
      break
    x -= f(n)
  for n in range(1, sq+1):
    cnt = k//n - k//(n+1)
    x -= f_l[n] * cnt
  return x

for k in range(1, M+1):
  f_l[k] = compute_f(k)

for d in range(M, 0, -1):
  f_h[d] = compute_f(K//d)

answer = 0

for k in range(1, M+1):
  low_d = K // (k+1) + 1
  high_d = K // k
  items = high_d - low_d + 1
  coef = (low_d + high_d) * items // 2
  answer += coef * f_l[k]
  
for d in range(1, M+1):
  if K // d <= M:
    break
  answer += d * f_h[d]

answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

ans = 0
count = [-1] * (K + 1)
for i in range(K, 0, -1):
    count[i] = pow(K // i, N, MOD) - sum(count[i + i :: i])
    ans += count[i] * i
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from math import gcd 
N,K=map(int,input().split())

mod=10**9+7

A=[0]*K

for i in range(K,0,-1):
    a=K//i
    b=pow(a,N,mod)
    A[i-1]=b

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

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

print(s)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
INF=10**9+7
baisu= [[] for _ in [0]*(k+1)]
D=[0]*(k+1)
ans=0
for d in range(1,k+1):
    baisu[d]=[d*i for i in range(2,k//d+1)]
    D[d]=pow(k//d,n,INF)

for d in range(k,0,-1):
    for b in baisu[d]:
        D[d]-=D[b]
    D[d]%=INF
for i,x in enumerate(D):
    #ans+=(i*x)%INFだとだめだった  ansを%INF
    ans=(ans+i*x)%INF
    
#print(baisu)
#print(D)
print(ans)

Submission status: Accepted

Solution code:
def divisors(n):
    ret=[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            ret.append(i)
            if i!=n//i:
                ret.append(n//i)
    return ret

mod=10**9+7    
n,k=map(int,input().split())
cnt=[0]*(k+1)
for i in range(k,1,-1):
    divs=divisors(i)
    cnt[i]+=pow(k//i,n,mod)
    for val in divs:
        if val==i:
            continue
        else:
            cnt[val]-=cnt[i]
cnt[1]+=pow(k,n,mod)
ans=0
for i in range(1,k+1):
    ans+=i*(cnt[i])%mod
    ans%=mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()

ans = 0
A = [0] * (K+1)
for x in range(K, 1, -1):
    a = K // x
    A[x] = pow(a, N, MOD)
    i = x
    while i + x <= K:
        i += x
        A[x] -= A[i]
    A[x] %= MOD
    ans += A[x] * x
    ans %= MOD
ans += pow(K, N, MOD) - sum(A)
ans %= MOD
print(ans)

Submission status: Accepted

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 = pow(num_of_mul, N, MOD)

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

Solution code:
M=10**9+7
n,k=map(int,input().split())
d=[0]*(k+1)
a=0
for i in range(k,0,-1):d[i]=pow(k//i,n,M)-sum(d[::i]);a+=i*d[i]
print(a%M)

Submission status: Accepted

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

Submission status: Accepted

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

A = [0]*K #A[i-1]はgcdがiになるN個の数の組の個数
for i in range(K//2,K):
  A[i] = 1
for i in range(K//2,0,-1):#大きい方から攻める
  a = pow(math.floor(K//i),N,mod)
  for j in range(2,math.floor(K//i)+1):
    a -= A[i*j-1]
  A[i-1] = a
      
ans = 0  
for i in range(1,K+1):
  ans = (ans + (A[i-1]*i)) % mod

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = int(1e9+7)
def modpow(a, p, mod):  # return a**p (% MOD)
  res = 1
  while p > 0:
    if p & 1 > 0:
        res = res * a % mod
    a = a**2 % mod
    p >>= 1
  return res

N, K = map(int, input().strip().split())
res = [-1]*(K+1)  # res[x] := gcd(...)がxになるものの個数(%MOD)
for x in range(K, 0, -1):
  n = K//x  # 1~Kの中に、xの倍数がいくつあるか
  if n == 1: res[x] = 1
  else:
    res[x] = modpow(n, N, MOD)
    for i in range(2,n+1):
      res[x] = (res[x] - res[x*i]) % MOD

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

Submission status: Accepted

Solution code:
M=10**9+7
n,k=map(int,input().split())
d=[0]*-~k
a=0
for i in range(k,0,-1):d[i]=pow(k//i,n,M)-sum(d[::i]);a+=i*d[i]
print(a%M)

Submission status: Accepted

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

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

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

ans = sum(ans)%mod

print(ans)

Submission status: Accepted

Solution code:
def divisor_enumetarion(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.remove(n)
    return divisors
    
n,k=map(int,input().split())
 
dp=[0]*k
mod=10**9+7
 
ans=0
for i in range(k,0,-1):
    toori=pow(k//i,n,mod)
 
    dp[i-1]+=toori
 
    x=divisor_enumetarion(i)
    for j in x:
        dp[j-1]-=dp[i-1]%mod
 
    ans+=(dp[i-1]*i)%mod
print(ans%mod)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N,K = list(map(int, input().split()))

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

for i in range(K):
    n = K - i
    yakusu = K//n
    s = pow(yakusu,N,1000000007)
    for j in range(2*n,K+1,n):
        s -= S[j]
    S[n] = s%1000000007
    ans[n] = s*n%1000000007



print(sum(ans)%1000000007)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

def modPow(a, b, mod):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%mod

        a = (a**2)%mod
        b //= 2

    return x



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

X = [0]*(K+1)
for i in range(1, K+1):
    X[i] = modPow(K//i, N, MOD)

for i in range(K, 0, -1):
    for j in range(i*2, K+1, i):
        X[i] -= X[j]

    X[i] %= MOD

print(sum(i*X[i] for i in range(1, K+1))%MOD)

Submission status: Accepted

Solution code:
from collections import deque, Counter
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7


def main():
    # N = int(input())
    N, K = [int(a) for a in input().split()]

    ts = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        m = K // k
        ts[k] = pow(m, N, M)
        for k2 in range(k * 2, K + 1, k):
            ts[k] -= ts[k2]
        ts[k] = ts[k] % M
    print(sum([a * i for i, a in enumerate(ts)]) % M)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
mod = 10**9+7

def main():
	n,k = MI()
	dp=[0]*(k+1)
	ans=0
	def g(x, n, mod):
		if n == 0:
			return 1
		K = 1
		while n > 1:
			if n % 2 != 0:
				K *= x
			x *= x%mod
			K %= mod
			n //= 2
		return K * x

	for i in range(k,0,-1):
		dp[i]=g(k//i,n,mod)
		for j in range(i*2,k+1,i):
			dp[i]-=dp[j]
			dp[i]%=mod
		dp[i]=(dp[i]%mod+mod)%mod
		ans+=i*dp[i]%mod
	print(ans%mod)
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,k = list(map(int,input().split()))
MOD = 10**9+7

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

for i in range(1,k):
    for j in range(i*2,k+1,i):
        L[j]-=L[i]
ans = 0
for i in range(1,k+1):
    ans = (ans+pow(k//i,n,MOD)*L[i])%MOD
print(ans)

Submission status: Accepted

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

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

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

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

print(s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

n, k = list(map(int, input().split()))
c = {i: pow(k//i, n, mod) for i in range(1, k+1)}
for i in range(k, 0, -1):
    for j in range(2*i, k+1, i):
        c[i] -= c[j]
_sum = 0
for x in range(1, k+1):
    _sum += c[x] * x % mod
print(_sum % mod)

Submission status: Accepted

Solution code:
def e_sum_of_gcd_of_tuples_hard(MOD=10**9 + 7):
    N, K = [int(i) for i in input().split()]
    ans = [0] * (K + 1)
    for i in range(K, 0, -1):
        multiple = K // i
        ans[i] = pow(multiple, N, MOD)
        # i の値を K から小さくしていかないと、この処理が誤りとなる
        for j in range(2 * i, K + 1, i):
            ans[i] -= ans[j]  # i の倍数 (2倍以上) の分を引く
        ans[i] %= MOD
    return sum([i * ans[i] for i in range(K + 1)]) % MOD

print(e_sum_of_gcd_of_tuples_hard())

Submission status: Accepted

Solution code:
M=10**9+7
n,k=map(int,input().split())
d=[0]*-~k
a=0
for i in range(k,0,-1):
    t=c=0
    for j in range(i,k+1,i):
        c+=1
        t+=d[j]
    d[i]=pow(c,n,M)-t
    a=(a+i*d[i])%M
print(a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from math import gcd

MOD = 10**9+7

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

c = [0]*(k+1)

for i in range(k,1,-1):
    tmp = pow(k//i,n,MOD)
    for j in range(i*2,k+1,i):###
        tmp -= c[j]
    c[i] = tmp%MOD
    res = (res+c[i]*i)%MOD

res = (res+pow(k,n,MOD)-sum(c))%MOD

print(res)

Submission status: Accepted

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()
mod = 1000000007

#n乗に**nを使うとTLEになる.powを使いましょう
eqi = [pow(K//(i+1), n, mod) 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] -= sum(eqi[1:])
        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):
        eqi[i-1] -= eqi[m*i - 1]
    eqi[i-1] %= mod
ans = 0
for i in range(K):
    ans += ((i+1)*eqi[i])%mod
print(ans%mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 10**9+7

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

print(sum([i * ans[i] for i in range(K+10)])%MOD)

Submission status: Accepted

Solution code:
from collections import *
import sys
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

N, K = nl()

MOD = 10**9 + 7
su = 0


sm = 0
muls = [0]*(K+1)
for k in range(K, 0, -1):
    sels = K//k
    pw = pow(sels, N, MOD)
    for mk in range(2*k, K+1, k):
        pw -= muls[mk]
    muls[k] = pw%MOD
    sm += pw*k%MOD

print(sm%MOD)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()
mod = 10**9+7
dp = [1]*(k+1)

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

ans = 0

for k,v in enumerate(dp):
    ans += k*v
    ans %= mod

print(ans)

Submission status: Accepted

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

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 = pow(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)
# print((np.arange(k+1) * nums).sum()%M)

Submission status: Accepted

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 = pow(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: Accepted

Solution code:
n, k = [int(_) for _ in input().split()]
d = {}
ans = 0
for i in range(k, 0, -1):
    # res = (k // i) ** n
    res = pow(k//i,n,(10**9+7))
    t = 2
    while i * t in d:
        res -= d[i * t]
        t += 1
    res = res % (10**9+7)
    d[i] = res
    ans += res * i
    ans = ans % (10**9+7)
print(ans)

Submission status: Accepted

Solution code:
#pow(a,b,mod)
#np.gcd.outer
#s.count, s.replace, s.index
from math import gcd
from functools import reduce
from itertools import product ##for i in z for j in z -> for i,j in product(z,z)   ||  for i,j in product(z,repeat=2)
#slice operation: sum(ans[slice(i*2,k+1,i)]) = sum(ans[i*2:k+1:i])

n,k=map(int,input().split(' '))
 
mod=10**9+7
 
ar=list(range(1,k+1))
ar.reverse()
 
ans=[0]*(k+1)
for i in ar:
	ava=(k-i)//i+1
	ans[i]=pow(ava,n,mod)-sum(ans[i*2:k+1:i])
print(sum(i*x for i,x in enumerate(ans))%mod)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))

    count = [0] * (k + 1)

    for x in range(k, 0, -1):
        c = k // x
        cx = pow(c, n, MOD)

        y = 2

        while x * y <= k:
            cx -= count[x * y]
            cx %= MOD
            y += 1

        count[x] = cx

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#pow(a,b,mod)
#np.gcd.outer
#s.count, s.replace, s.index
from math import gcd
from functools import reduce
from itertools import product ##for i in z for j in z -> for i,j in product(z,z)   ||  for i,j in product(z,repeat=2)


n,k=map(int,input().split(' '))
 
mod=10**9+7
 
ar=list(range(1,k+1))
ar.reverse()
 
ans=[0]*(k+1)
for i in ar:
	ava=(k-i)//i+1
	ans[i]=pow(ava,n,mod)-sum(ans[slice(i*2,k+1,i)])
print(sum(i*x for i,x in enumerate(ans))%mod)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
M = 1000000007


def main(N=None, K=None):
    if not N or not K:
        N, K = map(int, input().split())
    ans = 0
    gcds = {}
    for X in range(K, 0, -1):
        gcds[X] = int(pow(K//X, N, M))
        n = 1
        while True:
            n += 1
            if n*X > K:
                break
            gcds[X] -= gcds[n*X]
        ans += gcds[X]*X
    ans %= M
    print(ans)
    return ans


if __name__ == "__main__":
    # assert main(3, 2) == 9
    # assert main(3, 200) == 10813692
    # assert main(100000, 100000) == 742202979
    main()

Submission status: Accepted

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):#大きいほうから順に考える
    memo[i] = pow(K // i, N, mod)#最大公約数がiの倍数となる数列の個数
    j = 2#最初は２から
    while i * j <= K:#そのうち最大公約数がi以外のやつを引いていく
        memo[i] -= memo[i * j]
        j += 1
    ans += memo[i] * i#gcdの値*個数を足していく
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,boundary=1,search=[],replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,boundary=1,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
def show2d(g,h,w):
    for i in range(h):show(g[i*w:i*w+w])

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

## return prime factors of N as dictionary {prime p:power of p}
## within 2 sec for N = 2*10**20+7
def primeFactor(N):
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret


## return the list of prime numbers in [2,N], using eratosthenes sieve
## within 2sec for N = 1.2*10**7
def PrimeNumSet(N):
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList:
        if seachList[0] <= Max:
            break
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

## retrun LCM of numbers in list b
## within 2sec for no of B = 10*5  and  Bi < 10**6
def LCM(b,mo=10**9+7):
    prs=PrimeNumSet(max(b))
    M=dict(zip(prs,[0]*len(prs)))
    for i in b:
        dc=primeFactor(i)
        for j,k in dc.items():
            M[j]=max(M[j],k)
    
    r=1
    for j,k in M.items():
        if k!=0:
            r*=pow(j,k,mo)
            r%=mo
    return r

show_flg=False
show_flg=True

n,k=LI()
c=[0]*(1+k)

for i in range(k,0,-1):
    x=k//i
    c[i]=pow(x,n,mo)
    j=2
    while j*i<=k:
        c[i]-=c[i*j]
        c[i]%mo
        j+=1

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

print(ans)

Submission status: Accepted

Solution code:
def is_prime(num):
    if num == 1:
        raise ValueError("error!")
    d = 2
    while d * d <= num:
        if num % d == 0:
            return False
        d += 1
    return True
    
n, k = list(map(int, input().split()))
mod = 10 ** 9 + 7

n_power_table = [-1] * (k+1)
for i in range(k+1):
    n_power_table[i] = pow(i, n, mod)

# 素数リストを作っておく
prime_list = []
for i in range(2, k+1):
    if is_prime(i):
        prime_list.append(i)

prime_2_list = []
prime_3_list = []
prime_4_list = []
prime_5_list = []
prime_6_list = []

ll = len(prime_list)
for i, p1 in enumerate(prime_list):
    for j in range(i+1, ll):
        p2 = prime_list[j]
        if p1*p2 > k:
            break
        prime_2_list.append(p1*p2)
        for v in range(j+1, ll):
            p3 = prime_list[v]
            if p1*p2*p3 > k:
                break
            prime_3_list.append(p1*p2*p3)
            # print(p1, p2, p3)
            for w in range(v+1, ll):#enumerate(prime_list[v+1:]):
                p4 = prime_list[w]
                if p1*p2*p3*p4 > k:
                    break
                prime_4_list.append(p1*p2*p3*p4)
                for x in range(w+1, ll):#, p5 in enumerate(prime_list[w+1:]):
                    p5 = prime_list[x]
                    if p1*p2*p3*p4*p5 > k:
                        break
                    prime_5_list.append(p1*p2*p3*p4*p5)
                    for y in range(x+1, ll):#, p5 in enumerate(prime_list[w+1:]):
                        p6 = prime_list[y]
                        if p1*p2*p3*p4*p5*p6 > k:
                            break
                        prime_6_list.append(p1*p2*p3*p4*p5*p6)

prime_2_list.sort()
prime_3_list.sort()
prime_4_list.sort()
prime_5_list.sort()
prime_6_list.sort()

# prime_3_list = []
# for i, p1 in enumerate(prime_list):
#     for j, p1_ in enumerate(prime_2_list):
#         if p1*p1_ > k:
#             break
#         prime_3_list.append(p1*p1_)

# list(set(prime_3_list)).sort()

# print(prime_3_list)

ans = 0
temp = 0

for g in range(1, k+1):
    # kosuu は、gcd = gとなる組み合わせの個数
    p = k // g
    
    kosuu = n_power_table[p]

    for prime in prime_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]
    
    for prime in prime_2_list:
        if prime > p:
            break
        kosuu += n_power_table[p//prime]
    
    for prime in prime_3_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]

    for prime in prime_4_list:
        if prime > p:
            break
        kosuu += n_power_table[p//prime]

    for prime in prime_5_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]

    for prime in prime_6_list:
        if prime > p:
            break
        kosuu += n_power_table[p//prime]

    kosuu %= mod
    ans += g * kosuu
    # print(g, kosuu)
    temp += kosuu

print(ans% mod)
# print(temp)

Submission status: Accepted

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