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:
import sys

sys.setrecursionlimit(1000000)

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


cache = {}
def solve(N, K):
    M = pow(10, 9) + 7
    ans = 0
    for i in range(K, 0, -1):
        P = pow(K // i, N, M)
        j = i + i
        while j <= K:
            P -= cache[j]
            j += i
        while P < 0:
            P += M

        cache[i] = P
        ans += i * P
        ans %= M
    return ans

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

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

Submission status: Accepted

Solution code:
def main():
    MOD = 10 ** 9 + 7

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

    ctr = [0] * (K + 1)
    for g in range(K, 0, -1):
        cnt = pow(K // g, N, MOD)

        c = 2
        while c * g <= K:
            cnt = (cnt - ctr[c * g]) % MOD
            c += 1
        ctr[g] += cnt

    ans = 0
    for g, cnt in enumerate(ctr, 0):
        ans = (ans + g * cnt) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 10**9+7


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

    baisuu = [[] for _ in [0]*(k+1)]
    tree = [0]*(k+1)

    for i in range(1, k+1):
        j = 2*i
        while j <= k:
            baisuu[i] += [j]
            j += i
        tree[i] = pow(len(baisuu[i])+1, n, mod)
    for i in range(k, 0, -1):
        for j in baisuu[i]:
            tree[i] -= tree[j]
        tree[i] %= mod
    ans = 0
    for i, j in enumerate(tree):
        ans = (ans+i*j) % mod
    print(ans)


main()

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

count = [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):
    count[i] -= count[j]

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

print(sum_)

Submission status: Accepted

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd

from decimal import *
import copy
from bisect import *
import time
import sys
import math
input=lambda :sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
N,K=map(int,input().split())
mod=10**9+7
"""fac=[1,1]
for i in range(2,2*K+1):
    fac.append(fac[-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]
#print(fac)
#print(ifac)"""
def H(a,b):
    return(comb(a+b-1,a))
def comb(a,b):
    return(fac[a]*ifac[a-b]*ifac[b]%mod)


dp=[1 for i in range(K+1)]
for i in range(1,len(dp))[::-1]:
    n=(len(dp)-1)//i
    z=pow(n,N,mod)
    for m in range(i,len(dp),i):
        z-=dp[m]

    dp[i]+=z
    dp[i]%=mod
print(sum([dp[i]*i%mod for i in range(len(dp))])%mod)

Submission status: Accepted

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

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

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

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

print(ans%M)

Submission status: Accepted

Solution code:
from numpy import array


MOD = 10 ** 9 + 7

def solve(n, k):
    is_prime = array([True] * (k+1))
    is_prime[:2] = False
    for i in range(2, k+1):
        if i**2 > k: break
        if is_prime[i]:
            is_prime[i**2::i] = False
    primes = [i for i, _ in enumerate(is_prime) if is_prime[i]]
    
    res = [0] + [pow(k//i, n, MOD) for i in range(1, k+1)]

    for p in primes:
        for i in range(1, k//p+1):
            res[i] -= res[i*p]
            
    return sum(i*res[i] for i in range(k+1)) % MOD


def test():
    ...

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()

dp = [0]*(K+1)  # dp[i] := gcdの結果がiになるのが何通りあるか
ans = 0
for i in range(K, 0, -1):
	n = K//i
	dp[i] = pow(n, N, mod)
	for j in range(2, n+1):
		dp[i] -= dp[j*i]
		dp[i] %= mod
	ans += dp[i]*i
	ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
MOD = 10**9+7
dp = [0]*(k+1)
for i in range(k, 0, -1):
    """最大値だけの場合
    例) 3 4 → gcd(4 4 4)=4
    """
    dp[i] = pow((k//i), n, MOD)
    """2*iからk+1まで差iに関して
    例) 3 4 → gcd(a, b, c)=2になるのは
    (a,b,c)=(2or4,2or4,2or4)((a,b,c)=(4,4,4)を除く)
    """
    for j in range(i+i, k+1, i):
        dp[i] -= dp[j]
ans = sum([i*dp[i] for i in range(k+1)])
ans %= MOD
print(ans)

Submission status: Accepted

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

for i in range(K,0,-1):
    x = K//i
    a = pow(x, N, mod)
    cnt = 2
    while i*cnt <= K:
        a -= dp[i*cnt]
        cnt += 1
    a %= mod
    dp[i] = a
    ans += a*i
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import math
N, K = map(int,input().split())
MOD = 10**9 + 7
ans = 0
if K == 1:
    print(1)
else:
    ans = 0
    a = [0]*(K+1)
    for k in range(K,0,-1):
        s = K//k
        t = k*2
        u = 0
        while t <= K:
            u += a[t]
            t += k
        ans += k*(pow(s,N,MOD)-u)
        ans %= MOD
        a[k] = pow(s,N,MOD)-u
    print(ans)

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)
    j = 2
    while i * j <= K:
        memo[i] -= memo[i * j]
        j += 1
    ans += memo[i] * i
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

n, k = map(int, input().split())
x = [0 for _ in range(k + 1)]

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

Submission status: Accepted

Solution code:
N, K = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
gcd_comb = [0]*(K+1)
for i in range(K, 0, -1):
    gcd_comb[i] = pow(K // i, N, mod)
    gcd_comb[i] -= sum(gcd_comb[i + i : K + 1 :i])
    gcd_comb[i] %= mod
ans = 0
for i, n in enumerate(gcd_comb):
    if not i:
        continue
    ans = (ans + i * n) % mod
print(ans)

Submission status: Accepted

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

print(ans%MOD)

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:
import sys
def input(): return sys.stdin.readline().rstrip()

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
Mod = 10 ** 9 + 7

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
n, k = map(int, input().split())
MOD = 10**9+7
dp = np.zeros(k+1, dtype=np.int64)
for i in range(k, 0, -1):
  dp[i] = pow((k//i), n, MOD)
  dp[i] -= dp[i+i::i].sum()
j = np.arange(k+1)
ans = (j*dp).sum() % MOD
print(ans)

Submission status: Accepted

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

num = [0] * (k+1)
for i in range(k, 0, -1):
    x = pow(k//i, n, mod) - sum(num[::i])
    num[i] = x

print(sum(i*j%mod for i, j in enumerate(num))% mod)

Submission status: Accepted

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

class FLT:
    def __init__(self, mod=10**9+7):
        self.mod = mod

    def rep_sqr(self, base, k):
        ans = 1
        while k > 0:
            if k & 1:
                ans = ans * base % self.mod
            base = base * base % self.mod
            k >>= 1
        return ans

    def inv(self, a):
        """ 逆元を取る """
        return self.rep_sqr(a, self.mod-2)


def gcd_list(numbers):
    return reduce(gcd, numbers)

def euler_phi(n):
    phi = n
    for i in set(prime_factorize(n)):
        phi *= (1 - (1 / i))
    return int(phi)

def prime_factorize(n):
    # Return list of prime factorized result
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n, k = map(int, input().split())
MOD = 10**9 + 7
flt = FLT(MOD)
memo = [-1 for _ in range(k+1)]
ans = 0
for i in range(1, k+1):
    d = k // i
    ans += flt.rep_sqr(d, n) * euler_phi(i)
print(ans % MOD)

Submission status: Accepted

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

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)

def is_prime(n):
	for i in range(2, int(-(-n**0.5//1))+1):
		if n % i == 0:
			return False
	return True

def comb(n, r):
	return fact(n) // fact(n-r) // fact(r)

fact_memo = [1, 1]
def fact(n):
	if len(fact_memo) > n:
		return fact_memo[n]
	else:
		for i in range(len(fact_memo), n+1):
			fact_memo.append(fact_memo[i-1] * i)
		return fact_memo[n]


def main():
	log = Logger(1)
	n, k = map(int, sys.stdin.readline().split())
	ans = 0
	mod = 10 ** 9 + 7
	a = [0]*(k+1)
	for i in range(1, k+1):
		a[i-1] = pow(k//i, n, mod)
	ans = 0
	for i in list(range(1, k+1))[::-1]:
		for j in range(1, k//i):
			a[i-1] -= a[i-1 + i * j]
		ans += a[i-1] * i
		ans %= mod
	print(ans)



main()

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
from math import gcd
import bisect
import copy
from itertools import permutations,accumulate,combinations,product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

Submission status: Accepted

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

class FLT:
    def __init__(self, mod=10**9+7):
        self.mod = mod

    def rep_sqr(self, base, k):
        ans = 1
        while k > 0:
            if k & 1:
                ans = ans * base % self.mod
            base = base * base % self.mod
            k >>= 1
        return ans

    def inv(self, a):
        """ 逆元を取る """
        return self.rep_sqr(a, self.mod-2)


def gcd_list(numbers):
    return reduce(gcd, numbers)

def euler_phi(n):
    phi = n
    for i in set(prime_factorize(n)):
        phi *= (1 - (1 / i))
    return int(phi)

def prime_factorize(n):
    # Return list of prime factorized result
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n, k = map(int, input().split())
MOD = 10**9 + 7
flt = FLT(MOD)
memo = [-1 for _ in range(k+1)]
ans = 0
for i in range(1, k+1):
    d = k // i
    if memo[d] == -1:
        memo[d] = flt.rep_sqr(d, n)
    ans += memo[d] * euler_phi(i)
print(ans % MOD)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

# grobalにmdを設定すること
class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7

def main():
    n,k=MI()
    dp=[mint(0) for _ in range(k+1)]
    for a in range(k,0,-1):
        dp[a]+=pow(k//a,n,md)
        for b in range(2*a,k+1,a):
            dp[a]-=dp[b]
    ans=0
    for a in range(1,k+1):
        ans+=dp[a]*a
    print(ans)

main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
MOD = 10**9+7
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 = sum([i*dp[i] for i in range(k+1)])
ans %= MOD
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd
import math
n, k= map(int, input().split())
mod = 10**9+7
#全ての倍数の数を求める
ans = 0
count = [0 for i in range(k+1)]
for i in range(k,0,-1):
    num = k // i
    count[i] = pow(num,n,mod) 
    for j in range(i*2,k+1,i):
        count[i] -= count[j]
    ans += (count[i] * i)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    if k == 2:
        print((pow(2,n,mod)+1)%mod)
    elif k == 3:
        print((pow(3,n,mod)+3)%mod)
    elif k == 4:
        print((pow(4,n,mod)+pow(2,n,mod)+4)%mod)
    elif k == 5:
        print((pow(5,n,mod)+pow(2,n,mod)+8)%mod)
    else:
        f = [-1]*(k+1)
        p = 2
        while p <= k:
            x = 2*p
            while x <= k:
                f[x] -= f[p]
                x += p
            p += 1
        ans = 0
        p = [1]
        for i in range(1,k+1):
            p.append(pow(k//i,n,mod))
        for i in range(1,k+1):
            res = p[i]
            x = 2*i
            j = 2
            while x <= k:
                res += p[x]*f[j]
                x += i
                j += 1
            ans += i*res
            ans %= mod
        print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
MOD=10**9+7

def Eratosthenes(N):
    """
    Eratosthenesの篩: N以下の素数のリストを返す
    """
    N+=1
    is_prime_lst = [True]*N
    m = int(N**0.5)+1
    for i in range(3,m,2):
        if is_prime_lst[i]:
            is_prime_lst[i*i::2*i]=[False]*((N-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,N,2) if is_prime_lst[i]]

def bpm(m,n,mod):
    """
    Bisection power method : 二分累乗法
    """
    if n==0:
        return 1
    elif n%2:
        k=bpm(m,n//2,mod)
        return k*k*m%mod
    else:
        k=bpm(m,n//2,mod)
        return k*k%mod

def main():
    N,K=map(int,input().split())
    Primes=Eratosthenes(K)
    tmp=[0]+[bpm(K//i,N,MOD) for i in range(1,K+1)]
    for p in Primes:
        for j in range(p,K+1,p):
            tmp[j//p] -= tmp[j]
    print(sum(a*b for a,b in enumerate(tmp))%MOD)

main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def solve(n, k):
    # primes
    is_prime = [1] * (k + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for p in range(2, k + 1):
        if p * p > k:
            break
        if is_prime[p]:
            for q in range(p * p, k + 1, p):
                is_prime[q] = 0
    primes = [p for p in range(k + 1) if is_prime[p]]

    res_arr = [0] + [pow(k // i, n, MOD) for i in range(1, k + 1)]
    # print(res_arr)
    for p in primes:
        for i in range(1, k // p + 1):
            res_arr[i] -= res_arr[i * p]
    # print(res_arr)
    res = sum([i * res_arr[i] for i in range(k + 1)]) % MOD
    # print(res)
    return res


def main():
    n, k = map(int, input().split())
    res = solve(n, k)
    print(res)


def test():
    assert solve(3, 2) == 9
    assert solve(3, 200) == 10813692
    # assert solve(100000, 100000) == 742202979


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

n,k = LI()
f = [-1]*(k+1)
p = 2
while p <= k:
    x = 2*p
    while x <= k:
        f[x] -= f[p]
        x += p
    p += 1
ans = 0
p = [1]
for i in range(1,k+1):
    p.append(pow(k//i,n,mod))
for i in range(1,k+1):
    res = p[i]
    x = 2*i
    j = 2
    while x <= k:
        res += p[x]*f[j]
        x += i
        j += 1
    ans += i*res
    ans %= mod
print(ans%mod)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    f = [-1]*(k+1)
    p = 2
    while p <= k:
        x = 2*p
        while x <= k:
            f[x] -= f[p]
            x += p
        p += 1
    ans = 0
    p = [1]
    for i in range(1,k+1):
        p.append(pow(k//i,n,mod))
    for i in range(1,k+1):
        res = p[i]
        x = 2*i
        j = 2
        while x <= k:
            res += p[x]*f[j]
            x += i
            j += 1
        ans += i*res
        ans %= mod
    print(ans%mod)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N, K = read_values()
    C = [0] * (K + 1)

    for M in range(K, 1, -1):
        c = K // M
        C[M] = pow(c, N, mod)
        for r in range(2 * M, K + 1, M):
            C[M] -= C[r]
            C[M] %= mod

    C[1] = pow(K, N, mod) - sum(C) % mod
    C[1] %= mod
    print(sum(i * k for i, k in enumerate(C)) % mod) 


if __name__ == "__main__":
    main()

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 = (ans + b[i]) % mod

print(ans)

Submission status: Accepted

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

N,K = Ints()

mod = 10**9+7

One = [1,1]
R = 1

def divisor(M):
    A = []
    for i in range(1,int(M**0.5)+1):
        if M%i == 0:
            A.append(i)
            if M//i !=  i:
                A.append(M//i)
    #A.sort()
    return A

for i in range(2,K+1):
    tmp = 0
    tmp += pow(i,N,mod)
    tmp -= pow(i-1,N,mod)
    #print(divisor(i))
    for j in divisor(i):
        if j!=i:
            tmp -= One[j]
    #R += tmp%mod
    #R %= mod
    One.append(tmp%mod)
#print(One)
ans = 0
Rone = [0]
for i in range(1,K+1):
    Rone.append((Rone[-1]+One[i])%mod)

#print(Rone)
for i in range(1,K+1):
    ans += i*Rone[K//i]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
mod = 7 + 10 ** 9

def solve():
    N, K = map(int,input().split())
    count = [0] * (K + 1)
    ans = 0
    for i in reversed(range(1, K + 1)):
        upper = K // i
        count[i] += pow(upper, N, mod)
        count[i] %= mod
        ans += (count[i] * i) % mod
        ans %= mod
        for j in range(2, i + 1):
            if j ** 2 > i: break
            if i % j == 0:
                count[j] += (mod - count[i])
                count[j] %= mod
                if j ** 2 != i:
                    count[i // j] += (mod - count[i])
                    count[i // j] %= mod
        count[1] += (mod - count[i])
        count[1] %= mod
    print(ans)
        
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def solve(n, k):
    if k == 1:
        return 1

    MOD = 10 ** 9 + 7

    ans = (k // 2 + 1 + k) * (k - k // 2) // 2 % MOD  # k/2～k の和
    cnt = {1: 1}

    def get(d):
        if d in cnt:
            return cnt[d]
        result = pow(d, n, MOD)
        result -= d - d // 2
        for i in range(2, d // 2 + 1):
            result -= get(d // i)
        result %= MOD
        cnt[d] = result
        return result

    for i in range(1, k // 2 + 1):
        ans += i * get(k // i)
        ans %= MOD

    return ans


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

Submission status: Accepted

Solution code:
import math
mod = 10**9+7

n,k = map(int,input().split())
cnt = [0]*(k+1)
ans = 0
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]
        if cnt[i] < 0:
            cnt[i] += mod
    ans += cnt[i]*i
    if ans > mod:
        ans %= mod
print(ans)

Submission status: Accepted

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

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)

    ni = i + i
    while ni <= K:
        c -= CNT[ni]
        ni += i

    ans += c * i
    ans %= MOD
    num += c
    CNT[i] = c

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

def func(n):
    r = n
    for i in range(2, n + 1):
        if i ** 2 > n:
            break

        if n % i == 0:
            r -= r // i
            while n % i == 0:
                n //= i
        
    if n > 1:
        r -= r // n
    return r


MOD = 10 ** 9 + 7
ans = 0
for i in range(1, K + 1):
    ans += func(i) * pow(K // i, N, MOD)
print(ans % MOD)

Submission status: Accepted

Solution code:
MOD = int(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


N, K = map(int, input().split())
tot = [0]*(K+1)

for i in range(K,0,-1):
    tot[i] = pow_mod(K//i, N, MOD)
    s = 2
    while s*i <= K:
        tot[i] -= tot[s*i]
        s += 1
        
ans = 0
for i in range(K+1):
    ans += ((tot[i]%MOD)*i)%MOD

print(ans%MOD)

Submission status: Accepted

Solution code:
def divisors(n):
    res = []
    for d in range(1, int(n**0.5)+1):
        if n%d==0:
            res.append(d)
            res.append(n//d)
    res = sorted(set(res))
    return res

# 素因数分解
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

N, K = map(int, input().split())
invK = modinv(K)
P = [0] * (K+1)
mod = 10**9+7
for i in range(1, K+1):
    p = pow(K//i * invK, N, mod)
    P[i] = p
KN = pow(K, N, mod)
ans = 0


# https://kazuma8128.hatenablog.com/entry/2018/07/29/231819
for i in range(K, 1, -1):
    #print(i, divisors(i))
    for d in divisors(i):
        if d!=i:
            P[d] -= P[i]
for i, p in enumerate(P[1:], 1):
    n = p * KN % mod
    #print(i, n)
    ans = (ans + n * i) % mod
print(ans)