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:
def fac(n):
    global f
    rtn = {}
    while 1 < n:
        p = n // f[n]
        if p in rtn:
            rtn[p] += 1
        else:
            rtn[p] = 1
        if f[n] == 1:
            break
        n //= p
    return rtn

def div(n):
    dic = fac(n)
    rtn = [1]
    for k, v in dic.items():
        l = len(rtn)
        for i in range(l):
            for j in range(1, v + 1):
                rtn.append(rtn[i] * k**j)
    return rtn

n, k = map(int, input().split())
m = int(1e9 + 7)
f = [1 for _ in range(100001)]
for i in range(2, 100001):
    if f[i] == 1:
        for j in range(2, 100000 // i + 1):
            if f[i * j] == 1:
                f[i * j] = j

cnt = [0 for _ in range(k + 1)]
for i in range(k, 0, -1):
    cnt[i] += pow(k // i, n, m)
    ds = div(i)
    for d in div(i)[:-1]:
        cnt[d] -= cnt[i]
        cnt[d] %= m
for i in range(2, k + 1):
    cnt[i] *= i
    cnt[i] %= m
ans = sum(cnt) % m
print(ans)

Submission status: Accepted

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


def pow_mod(x, n, mod):
    if n > 1:
        return pow_mod(pow(x,2) % mod, n//2, mod) * pow(x, n%2) % mod
    else:
        return x


pow_n = [-1] * (k+1)
for i in range(1,k+1):
    if pow_n[k//i] == -1:
        pow_n[k//i] = pow_mod(k//i, n, mod)

ans = 0
c = [0] * (k+1)
for i in range(k, 0, -1):
    count = pow_n[k//i]
    for j in range(2, k//i+1):
        count -= c[i*j]
        count %= mod
    c[i] = count
    ans += count * i
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

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

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


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

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

answer = sum(i * x for i, x in enumerate(A))
print(answer % MOD)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def phi(n):
    r = n
    i = 2
    while i * i <= n:
        if n % i == 0:
            r -= r // i
            while n % i == 0:
                n //= i
        i += 1
    if n > 1:
        r -= r // n
    return r


n, k = map(int, input().split())
ans = 0
for i in range(1, k + 1):
    ans += phi(i) * pow(k // i, n, MOD)
print(ans % MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

class E :
    def __init__ (self) :
        self.MOD = int(1e9+7)

    def e(self, n, k) :
        if k == 1 :
            return (n*(n+1))//2 
        
        ans = 0

        dp = dict()
        for i in range(1, n+1) :
            dp[i] = pow( n//i, k, self.MOD)

        for i in range(1, n+1)[::-1] :
            for j in range(i+i,n+1,i) :
                dp[i] -= dp[j]
            
        for i in range(1, n+1) : 
            ans = (ans + dp[i]*i) % self.MOD
        
        return ans

if __name__ == "__main__" :
    k, n = map(int, input().split(" "))
    print(E().e(n, k))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


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


def gcd(a, b):
    # greatest common divisor
    while b > 0:
        a, b = b, a % b

    return a


MOD = 10**9 + 7


def POW(a, p):
    if a == 1 or p == 0:
        return 1

    if p == 1:
        return a
    else:
        return (POW(a, p // 2)**2 * (a**(p % 2))) % MOD


def ShinKosuu(k, kosuu, shinkosuu):
    ret = kosuu[k]
    for t in range(k * 2, K + 1, k):
        ret -= shinkosuu[t]
    return ret


def main():

    ans = 0
    kosuu = [0] * (K + 1)
    shinkosuu = [0] * (K + 1)
    for k in range(K, 0, -1):
        kosuu[k] = POW(K // k, N)
        shinkosuu[k] = ShinKosuu(k, kosuu, shinkosuu)
        ans = (ans + k * shinkosuu[k]) % MOD
    # print(kosuu)

    print(ans)


if __name__ == '__main__':
    N, K = inpl()
    main()

Submission status: Accepted

Solution code:
mod=10**9+7

from functools import lru_cache

@lru_cache()
def pow(N,K):
    if K==0:
        return 1
    elif K==1:
        return N
    if K%2==0:
        return (pow(N,K//2)*pow(N,K//2))%mod
    else:
        return (N*pow(N,K-1))%mod



def f(N,K,i):
    if table[K]>0 and i==1:
        return table[K]

    if K==i:
        return 1
    elif K==1:
        return 1

    if i==1:
        sigma=0
        for j in range(2,K+1):
            sigma+=f(N,K//j,1)
            sigma=sigma%mod
        retval=(pow(K,N)-sigma)%mod
        table[K]=retval
        return retval

    else:
        return f(N,K//i,1)%mod


def calc(N,K):
    retval=0
    for i in range(1,K+1):
        retval+=i*f(N,K,i)
        retval=retval%mod
    return retval

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

table=[-1 for i in range(K+1)]
table[1]=1


print(calc(N,K))

Submission status: Accepted

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

a = 10**9+7
count = [0 for i in range(k)]
sum = 0

res = n
e = []
while res != 0:
    e.append(res%2)
    res = res // 2

def exp(m, e, a):
    sum = 0
    ans = 1
    t = m
    for i in e:
        ans = (ans*(t**i))%a
        t = (t**2)%a
    return ans

for i in range(k, 0, -1):
    count[i-1] = exp(k//i, e, a)
    j = 2
    while i*j <= k:
        count[i-1] -= count[i*j-1]
        j += 1
    count[i-1] %= a
    sum += (i*count[i-1])%a

sum %= a
print(sum)

Submission status: Accepted

Solution code:
def main():
    mod=10**9+7
    def square(x,y):
        ret=1
        xx=x
        while y:
            if y%2==1:
                ret=ret*xx%mod
            xx=xx**2%mod
            y//=2
        return ret
    n,k=map(int,input().split())
    ans=0
    dp=[0]*(k+1)
    for i in range(k,0,-1):
        x=square(k//i,n)
        for j in range(2,k//i+1):
            x=(x-dp[i*j])%mod
        dp[i]=x
        ans=(ans+x*i)%mod  
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, k = LI()
    dp = [0] * (k + 1)
    for i in range(k, 0, -1):
        if i < 3:
            dp[i] += pow(k // i, n, mod)
            dp[i] %= mod
            if i != 1:
                dp[1] -= dp[i]
                dp[1] %= mod
        else:
            dp[i] += pow(k // i, n, mod)
            dp[i] %= mod
            j = 2
            while j ** 2 <= i:
                if i % j == 0:
                    dp[j] -= dp[i]
                    dp[j] %= mod
                    m = i // j
                    if m != j:
                        dp[m] -= dp[i]
                        dp[m] %= mod
                j += 1
            dp[1] -= dp[i]
            dp[1] %= mod
    ans = 0
    for i in range(k + 1):
        ans += i * dp[i]
        ans %= mod
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#Walayn3al mok a pc dlmard
#python d zab
mod=1000000007
def p(a,b):
    if b==0:
        return 1
    z=p(a,b//2)
    z%=mod
    if b%2==1:
        return (a*z*z)%mod
    else:
        return (z*z)%mod
n,k=map(int,input().split())
dp=[0]*(k+3)


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

Submission status: Accepted

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


# nの約数列挙
def divisor(n):
    ans = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ans.append(i)
            if i**2 == n:
                continue
            ans.append(n // i)
    return ans  # sortされていない


MOD = 10 ** 9 + 7

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

    c -= CNT[i]

    num += c

    f = divisor(i)
    for n in f:
        CNT[n] += c

    ans += c * i
    ans %= MOD


al = pow(K, N, MOD)
ans += al - num
ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
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)
    # divisors.sort()
    return divisors
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
N,K = map(int,input().split())
ans = K ** N
divdic = {1:1} 
for i in range(2,K+1):
    A = make_divisors(i)
    A.remove(i)
    X = i
    for j in A:
        X -= divdic[j]
    divdic[i] = X
    Y = K // i
    Z = X * (power_func(Y,N,mod)) % mod
    #print(i,X,Y,Z)
    ans = (ans + Z) % mod
print(ans)

Submission status: Accepted

Solution code:
import bisect
import collections
import functools
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


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


def llmi(n):
    return [lmi() for _ in range(n)]


# pattern of x で割れる
@functools.lru_cache(maxsize=None)
def f(x):
    return K//x
    a = 0
    for i in range(1, K + 1):
        if i % x == 0:
            a += 1
    return a % ACMOD


@functools.lru_cache(maxsize=None)
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 frozenset(divisors)


@functools.lru_cache(maxsize=None)
def get_diff(x):
    """
    xで割れるときにいくら増加するか
    2 -> 1 でカウント済みなので1
    """
    if x == 1:
        return 1
    ans = x
    for v in make_divisors(x):
        if v != x:
            ans -= get_diff(v)
    return ans % ACMOD


@functools.lru_cache(maxsize=None)
def pow(base_val, pow_val):
    if pow_val == 1:
        return base_val
    if pow_val == 0:
        return 1
    t = pow(base_val, pow_val // 2) % ACMOD
    return (t * t % ACMOD * (base_val if pow_val % 2 else 1)) % ACMOD


# for i in range(1, 100000):
#     get_diff(i)
#
# print("ok")
N, K = lmi()

ans = 0
for i in range(1, K + 1):
    ans += (pow(f(i), N) % ACMOD) * get_diff(i) % ACMOD
    # print(i,f(i), get_diff(i))

print(ans % ACMOD)

Submission status: Accepted

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

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

  divisors.sort()
  return divisors
  
def powmod(a,p):
  if p==0:
    return 1
  elif p==1:
    return a
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD

div_table=[0,1]
for i in range(2,K+1):
  divlist=make_divisors(i)
  dv=i
  for d in divlist:
    if d<i:
      dv-=div_table[d]
  div_table.append(dv)
#print(div_table)
    
answer=0
for i in range(1,K+1):
  k=div_table[i]
  pm=powmod(K//i,N)
  answer+=k*pm
  answer%=MOD
  
print(answer)

Submission status: Accepted

Solution code:
M = 1000000007

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

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

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

print(S)

Submission status: Accepted

Solution code:
mod = 10**9+7
N,K = map(int,input().split())
p = [1]*(10**5+1)
for i in range(1,10**5+1):
    p[i] = pow(i,N,mod)
memo = [-1]*(K+1)
memo[1] = 1
def f(k):
    if memo[k] != -1:
        return memo[k]
    res = p[k]
    for n in range(2,k+1):
        res -= f(k//n)
    res %= mod
    memo[k] = res
    return res
ans = 0
for n in range(1,K+1):
    ans += n*f(K//n)
    ans %= mod

print(ans)

Submission status: Accepted

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

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

    if sum(cont) % MOD != pow(K,N,MOD):
        ans -= sum(cont) % MOD - pow(K,N,MOD)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10**9+7
N, K = map(int, input().split())
count = 0
ans = pow(K, N, MOD)
dictionary = [0 for _ in range(K+1)]
for i in range(K-1):
    j = K-i
    tmp = K // j
    tmp2 = pow(tmp, N, MOD)
    tmp2 -= sum(dictionary[::j])
    dictionary[j] = tmp2
    ans = (ans + (j-1) * tmp2)%MOD
    #print(tmp2, j)
#print(dictionary)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

div = [set() for _ in range(K+1)]
for i in range(2, K+1):
    for j in range(2*i, K+1, i):
        div[j].add(i)

pattern = [0]*(K+1)
for x in range(2, K+1)[::-1]:
    pattern[x] = (pattern[x] + pow(K//x, N, MOD)) % MOD
    for d in div[x]:
        pattern[d] = (pattern[d] - pattern[x] % MOD) % MOD
    pattern[1] = (pattern[1] - pattern[x]) % MOD
    
    ans = (ans + (pattern[x] * x) % MOD) %MOD

ans = (ans + (pow(K, N, MOD) + pattern[1]) % MOD ) % MOD

print(ans)

Submission status: Accepted

Solution code:
mod=1000000007
def powmod(a, n):
    global mod
    res = 1
    tmp=a
    while n>0:
        if n & 1 == 1:
            res = (res * tmp) % mod
        n=n//2
        tmp = tmp * tmp % mod
    return res
n,k=map(int, input().split())
appear_num = [0] * k
ans = 0
for gcm in range(k,0,-1):
    multi_num = k // gcm
    appear_num[gcm-1] = powmod(multi_num, n)
    for i in range(2, multi_num+1):
        appear_num[gcm-1] += mod - appear_num[i*gcm-1]
        appear_num[gcm-1] %= mod
    ans += gcm*appear_num[gcm-1]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def linput():
    return [int(x) for x in input().split()]

mod = 10**9 + 7

n, k = linput()

cnt = [0] * (k + 1)

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

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

ans = 0
#約数の列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


for i in range(k, 0, -1):
    ans += cnt[i] * i
    ans %= mod
    d = make_divisors(i)
    for j in d:
        cnt[j] -= cnt[i]

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def make_divisors(n): # nの約数を列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

# 最大公約数が1から順番に数える
MOD = 10 ** 9 + 7
N, K = lr()
answer = 0
reset = [0] * (K+1)
for i in range(1, K+1):
    num = K // i
    cmb = pow(num, N, MOD)
    arr = make_divisors(i)
    x = i
    for a in arr[:-1]:
        x -= reset[a]
    reset[i] = x
    answer += x * cmb

print(answer % MOD)

Submission status: Accepted

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

MOD = 10**9 + 7


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


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

d = {}


def func1(kk):
    # 1-kをn個並べる時、gcdが1となる通り数
    if kk == 1:
        return 1
    if kk in d:
        return d[kk]

    cnt = 0
    for x in range(2, kk + 1):
        y = kk // x
        cnt += func1(y)

    d[kk] = (MOD + pow(kk, n, MOD) - cnt) % MOD
    return d[kk]


ans2 = 0
cnt = 0
for x in range(2, k + 1):
    y = k // x
    if y > 1:
        cnt = func1(y)
        ans2 += cnt * x % MOD
        ans2 %= MOD
    else:
        ans2 += x
        ans2 %= MOD

ans1 = func1(k)
ans = ans1 + ans2
ans %= MOD
# print(ans1, ans2)
print(ans)

Submission status: Accepted

Solution code:

mod = 10**9 + 7

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

ans = pow(K, N, mod)
cnts = [0] * (K + 1)
for k in range(K, 0, -1):
    r = K // k
    if r == 1:
        cnt = 1
        ans += (k - 1) * 1
    else:
        cnt = pow(r, N, mod)
        for c in range(2, r + 1):
            cnt -= cnts[k * c]
        cnt %= mod
        ans += (k - 1) * cnt

    cnts[k] = cnt
    ans %= mod

print(ans)

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 math
import collections
def main():

    N, K = map(int, input().split())
    mod = pow(10, 9) + 7

    p = collections.defaultdict(int)

    def fast_pow(x, y, mod):
        if y == 0: return 1
        if y % 2 == 0: return pow(fast_pow(x, y//2, mod), 2) % mod
        if y % 2 == 1: return (x * pow(fast_pow(x, y//2, mod), 2)) % mod

    ans = 0
    for i in range(K, 0, -1):
        v = fast_pow(K//i, N, mod) % mod
        u = v - p[i]
        tmp = (u * i) % mod
        for j in range(1, int(math.sqrt(i))+1):
            if i % j == 0:
                p[j] += u
                p[j] %= mod
                if i//j != j:
                    p[i//j] += u
                    p[i//j] %= mod
        ans += tmp
        ans %= mod
        # print(i, ans)
    return ans

if __name__ == '__main__':
    print(main())

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(dp)
#    print(i,dp[i-1])
print(ans%mod)

#gcdがiの時だけを考え通りを引いて1を足す

Submission status: Accepted

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

L=[0 for i in range(N+1)]
E=[1 for i in range(N+1)]
E[0]=0
E[1]=0
for i in range(2,N+1):
    if E[i]==1:
        for j in range(2,N+1):
            if i*j>=N+1:
                break
            E[i*j]=0
#print(E)
L[1]=N
#print(L)
for i in range(2,N+1):
    L[i]=N//i
#print(L)
l=[0 for i in range(N+1)]
mod=10**9+7
ans=0
for i in range(N):
    cnt=pow(L[N-i],K,mod)
    for j in range(2,N+1):
        if (N-i)*j>=N+1:
            break
        cnt-=l[(N-i)*j]
    l[N-i]=(cnt%mod)
    ans+=(cnt%mod)
#print(l)
#print(ans)
ANS=0
for i in range(len(l)):
    ANS+=i*l[i]
    ANS%=mod
print(ANS)
#print(l)

Submission status: Accepted

Solution code:
import sys
import time
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math

import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21


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

    # divisors.sort()
    return divisors

def tasikame(n):
    ans = 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n + 1):
                tmp = math.gcd(i, j)
                ans += math.gcd(tmp, k)

    return ans


def main():
    n, k = getlist()
    ans = 0
    kumi = [0 for i in range(k+1)]
    for ii in range(k):
        i = k - ii
        cand = k // i
        # 総数　ほう助なし
        tmp = pow(cand, n, MOD)
        # ttmp = i
        # print(tmp)
        # child = make_divisors(i)
        # for ch in child:
        #     kumi[ch] += tmp
        # while(True):
        #     ttmp += i
        #     if ttmp > k:
        #         break
        #     tmp -= kumi[ttmp]
            # print(tmp)
        tmp -= kumi[i]
        child = make_divisors(i)
        for ch in child:
            kumi[ch] += tmp
        # tmp -= (cand - 1) ** n
        ans += (tmp * i) % MOD
        ans %= MOD
        kumi[i] = tmp
        # print(i, ans, tmp, n)
    print(ans)
    # print(tasikame(k))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

s = sum(cnt)
ans = pow(k,n,mod) - s
for i in range(k+1):
    ans += i*cnt[i]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))


#処理内容
def main():
	N, K = getlist()
	ans = 0
	L = [0] * (K + 1)
	for i in range(K):
		x = K - i
		val = pow(int(K // x), N, con)
		for j in range(2, int(K // x) + 1):
			val -= L[x * j]
		L[x] = (val % con)

	for i in range(1, K + 1):
		ans += L[i] * i
		ans %= con

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

mod = 1000000007
ans = 0
dp = [0]*(k+1)

for i in range(k, 0, -1):
    x = k//i
    dp[i] += pow(x, n, mod)
    dp[i] %= mod
    # for c in dp:
    #     print(c, end=' ')
    # print()
    ans += dp[i]*i
    ans %= mod

    j = 2
    divisor = [1]
    while j*j <= i:
        if i%j == 0:
            divisor.append(j)
            if j != i//j:
                divisor.append(i//j)
        j += 1

    for d in divisor:
        dp[d] -= dp[i]
        dp[d] = (dp[d]+mod)%mod


ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

ans = 0

#M = np.zeros(K+1, dtype=int)
M = [0 for _ in range(K+1)]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
N,K = map(int,input().split())
res = np.zeros(K+1, dtype=np.int64)
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)
    divisors.sort()
    return np.array(divisors, dtype=np.int64)

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

Submission status: Accepted

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

    i = 2
    while k * i <= K:
        dp[k] -= dp[k*i]
        i += 1
    # print(k, dp)
    ans += k * dp[k]
    ans %= MOD
# print(dp)
print(ans)

Submission status: Accepted

Solution code:
def divisor(x):
    div = []
    for i in range(1,int(x**0.5)+1):
        if x%i == 0:
            div.append(i)
            if x != i**2: div.append(x//i)
    
    return div

MOD = 1000000000 + 7

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

count = [0] * k

for i in range(k):
    count[i] = pow(k//(i+1),n,MOD)
    
for i in range(k,0,-1):
    for j in divisor(i):
        if j<i:
            count[j-1] -= count[i-1]
            count[j-1] %= MOD

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

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

MOD = 1000000007

def smax(a,b):
    if a>b:
        return a
    else:
        return b

def smin(a,b):
    if a<b:
        return a
    else:
        return b


def main():
    N,K = list(map(int,readline().split()))
    DP = [0]*(K+1)
    ans = 0
    pow_list = [pow(i,N,MOD) for i in range(1,K+1)]
    for i in range(K):
        x = K-i
        DP[x] = pow_list[int(K/x)-1]
    #print(DP)
    for s in range(K):
        i = K-s
        x = int(K/i)
        #checked = [False]*x
        val = DP[i]
        #print(ans,i)
        for j in range(1,x):
            val += MOD - DP[i*(j+1)]
            val %= MOD
            """
            if checked[j]==False:
                ans += MOD - (DP[i*(j+1)]*i)%MOD
                ans %= MOD
                #print(ans,j,checked)
                k = j+1
                while k < x+1:
                    if checked[k-1]:
                        print(k)
                        ans += DP[i*k]*i
                        ans %= MOD
                    checked[k-1] = True
                    k += j+1
            """
        ans += val*i
        ans %= MOD
        DP[i] = val
    print(ans)
        

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 1000000007  # type: int


def solve(N: int, K: int):
    count = [0]*(K+1)

    answer = 0
    for k in range(K,0,-1): #kの倍数のもの
        d = K//k
        if k == 1:
            answer += pow(K,N,MOD)-sum(count) 
        else:
            count[k] = pow(d,N,MOD)
            i = 2
            while k*i <= K:
                count[k] -= count[k*i]
                i += 1
            answer += count[k]*k
        answer %= MOD
    print(answer)
    return


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:
#!/usr/bin/env python3
import sys
import functools
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, K: int):

    def NN(a):
        return K//a

    @functools.lru_cache(maxsize=None)
    def f(a):
        ans = pow(NN(a), N, MOD)
        for i in range(2, K+1):
            if i*a > K:
                break
            ans -= f(i*a)
            ans %= MOD
        return ans % MOD

    ans = 0
    for i in range(1, K+1):
        # print(i*f(i))
        ans += i*f(i)
        ans %= MOD
    print(ans)

    return


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:
from math import gcd
N,K = map(int,input().split())
MOD = 10**9+7

dp = [1] * (K+1)
for n in range(K//2,0,-1):
    p = pow(K//n,N,MOD)
    for m in range(2*n,K+1,n):
        p -= dp[m]
    dp[n] = p%MOD

ans = 0
for i,n in enumerate(dp):
    ans += i*n
    ans %= MOD
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10 ** 9 + 7

def make_divisors(N) :
  divisors = []
  for i in range(1, N + 1) :
    if i * i > N :
      break
    if N % i == 0:
      divisors.append(i)
      if i != N // i:
        divisors.append(N // i)

  return divisors

cnt = [0] * (K + 1)

ret = 0
for i in range(K, 0, -1) :
  cnt[i] += pow(K // i, N, mod)
  ret += i * cnt[i] % mod
  ret %= mod
  for j in make_divisors(i) :
    if j == i :
      continue
    cnt[j] -= cnt[i]

print(ret)