Problem:


Score : 500 points

Problem Statement

Consider sequences \{A_1,...,A_N\} of length N consisting of integers between 1 and K (inclusive).

There are K^N such sequences. Find the sum of \gcd(A_1, ..., A_N) over all of them.

Since this sum can be enormous, print the value modulo (10^9+7).

Here \gcd(A_1, ..., A_N) denotes the greatest common divisor of A_1, ..., A_N.

Constraints

2 \leq N \leq 10^5

1 \leq K \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

Print the sum of \gcd(A_1, ..., A_N) over all K^N sequences, modulo (10^9+7).

Sample Input 1

3 2

Sample Output 1

9

\gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2)
+\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2)
=1+1+1+1+1+1+1+2=9

Thus, the answer is 9.

Sample Input 2

3 200

Sample Output 2

10813692

Sample Input 3

100000 100000

Sample Output 3

742202979

Be sure to print the sum modulo (10^9+7).



Sample input:
3 2


Sample output:
9

Submission status: Time Limit Exceeded

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

mod = 10**9+7

all_num = k**n
ans = 0

dp = [0]*(k+1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)

div_cache = {}


def primes(N):
    if N in div_cache:
        return div_cache[N]
    ret = set()

    for i in range(1, N):
        if N % i == 0:
            ret.add(i)
            if i != 1:
                ret.add(N // i)
    div_cache[N] = ret
    return ret


# assert(primes(1) == set())
# assert(primes(2) == {1})
# assert(primes(10) == {1, 2, 5})
# assert(primes(20) == {1, 2, 4, 5, 10})

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


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

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

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

    # print(data)
    return ans


# assert(solve(3, 2) == 9)
# assert(slowsolve(3, 2) == 9)
# assert(slowsolve(3, 3) == 30)
# assert(solve(3, 3) == slowsolve(3, 3))
# print("collect")
# print(slowsolve(2, 6))
# print("wrong")
# print(solve(2, 6))
# assert(solve(6, 6) == slowsolve(6, 6))
# assert (solve(3, 200) == 10813692)
# print("OK")
# assert (solve(100000, 100000) == 742202979)
# print("OK!!!!")

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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from itertools import combinations_with_replacement, permutations

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


answer = 0

for c in combinations_with_replacement(range(1, K + 1), N):
    n = c[0]
    for v in c[1:]:
        n = gcd(n, v)
    answer += n * len(set(permutations(c)))

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from itertools import product
from functools import reduce
K, N = map(int, input().split())
List = list(product(list(range(1,N+1)),repeat = K))
NewList= 0
for i in range(len(List)):
    Number = reduce(gcd, List[i])
    NewList += Number
print(NewList)

Submission status: Time Limit Exceeded

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

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

for i in range(K,0,-1):
    tot[i] = ((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: Time Limit Exceeded

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

def nextLine(): return next(stdin)
def nextStrList(): return nextLine().split()
def nextIntList(): return [int(_) for _ in nextStrList()]


# def comp0(n,k):
# 	import itertools
# 	import math
# 	s=0
# 	for a,b,c in itertools.product(range(1,k+1), repeat=n):
# 		g=math.gcd(math.gcd(a,b),c)
# 		s+=g
# 	return s

from collections import Counter
import math
def comp(n,k):
	mod=1000000007
	count=Counter(range(1,k+1))
	for ni in range(2, n+1):
# 		print(ni, count)
		nextCount=Counter()
		for ki in range(1, k+1):
			for g,c in count.items():
				nextG=math.gcd(g, ki)
				nextCount[nextG]=(nextCount[nextG]+c)%mod
		count=nextCount
	s=0
	for g,c in count.items():
		s=(s+g*c)%mod
	return s

def main():
	n,k=nextIntList()
# 	n,k=100000,100000
# 	n,k=3,200
	
	s=comp(n,k)
	print(s)
# 	s=comp0(n,k)
# 	print(s)
	
if __name__=="__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools

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

n, k = readInt()
ans = 0
# print(n,k)
l = list(itertools.product(range(1,k+1),repeat=n))
for i in l:
    x = 0
    # print(i)
    for j in i:
        # print(j)
        # print(j,i[0])
        if x==0:
            g = j
            x += 1
        g = math.gcd(j,g)
        # print(g)
    ans += g
    # print(g,i)
# print(l)
ans = ans % (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
dp = [[0]*k for _ in range(n)]
dp[0] = [1]*k

gcd = [[0]*k for _ in range(k)]
for i in range(k):
    for j in range(k):
        if i == j:
            gcd[i][j] = i+1
        else:
            if i > j:
                gcd[i][j] = gcd[i-j-1][j]
            else:
                gcd[i][j] = gcd[i][j-i-1]
        
for i in range(1,n):
    for j in range(k):
        if dp[i-1][j] != 0:
            for l in range(k):
                dp[i][gcd[j][l]-1] += dp[i-1][j]

ans = 0
mod = 10**9+7
for i,j in enumerate(dp[n-1]):
    ans += (i+1)*j
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict


def gcd(a, b):
    c, d = a, b
    if gcdlist[a][b]:
        return gcdlist[a][b]
    while b:
        a, b = b, a % b
    gcdlist[c][d] = a
    gcdlist[d][c] = a
    return a


def resolve():
    mod = 10 ** 9 + 7
    n, k = map(int, input().split())
    c = {x + 1: 1 for x in range(k)}
    global gcdlist
    gcdlist = [[None] * (k + 1) for _ in range(k + 1)]
    for _ in range(n - 1):
        d = defaultdict(int)
        for key, value in c.items():
            for j in range(k):
                d[gcd(j + 1, key)] += value
        for key, value in d.items():
            c[key] = value % mod
    ans = 0
    for key, v in c.items():
        ans += key * v
        ans %= mod
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

mod = 10**9 + 7

n, k = map(int, input().split())
a = np.arange(1, k+1)
b = np.array(list(itertools.product(*[a for i in range(n)])))
c = np.gcd.reduce(b, axis =1)
print(sum(c)%mod)

Submission status: Time Limit Exceeded

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

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

for i in range(K,0,-1):
    tot[i] = (K//i)**N
    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: Time Limit Exceeded

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
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 * Y ** N) % mod
    #print(i,X,Y,Z)
    ans = (ans + Z) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n,k = map(int,input().split())
x = [1]*(k+1)
y = [0]
for i in range(1,k+1):
    t = [0]
    for j in range(1,k+1):
        v = math.gcd(i,j)
        t.append(v)
    y.append(t)
for i in range(n-1):
    z = [0]*(k+1)
    for j in range(1,k+1):
        for c in range(1,k+1):
            z[y[j][c]] += x[j]
    x = z
p = 0
for i in range(1,k+1):
    p += (x[i]*i)%1000000007
print(p)

Submission status: Time Limit Exceeded

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

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

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


    ans += i*mm
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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


ans=0
for i in range(k,0,-1):
    toori=(k//i)**n

    dp[i-1]+=toori

    x=divisor_enumetarion(i)
    for j in x:
        dp[j-1]-=dp[i-1]

    ans+=dp[i-1]*i
#    print(dp)
#    print(i,dp[i-1])
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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

import itertools
import math
from functools import reduce

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

lis = list(range(1,K+1))
S = [gcd_list(team) for team in itertools.product(lis, repeat = N)]

print(sum(S) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k = map(int,input().split())
data = [0] * (k+1)
for i in range(k,0,-1):
  tmp =  (k//i) ** n
  for j in range(i+i,k+1,i):
    tmp -= data[j]
  data[i] = tmp % mod
ans = 0
for i,di in enumerate(data):
  ans += i * di
  ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
t = input()
t = t.split()
n = int(t[0])
k = int(t[1])
nn = [1]*n
ans = 0
while True:
  g = math.gcd(nn[0], nn[1])
  for i in range(2,n):
    g = math.gcd(g, nn[i])
  ans += g
  br = True
  for i in range(n):
    if nn[i] != k:
      br = False
      break
  if br:
    break
  for i in range(n):
    if nn[i] == k:
      nn[i] = 1
    else:
      nn[i] += 1
      break
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Accepted

Solution code:
import sys
import math


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    mod = 10 ** 9 + 7

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

    C =[0] *(K+1)

    for k in range(K,1,-1):
        num = K//k
        count = pow(num,N,mod)
        while num>1:
            count -= C[num*k]
            count %=mod
            num-=1
        C[k] =count
    ans =0
    for i in range(K+1):
        ans += i*C[i]
        ans %=mod
    ans += pow(K,N,mod) -sum(C)

    print(ans%mod)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def solve(N, K):
    ans = 0
    numExact = [0] * (K + 1)
    for g in reversed(range(1, K + 1)):
        # Count number of sequences where every element is a multiple of g
        # The gcd of such sequence is at least g
        numGreaterEq = pow(K // g, N, MOD)
        # But we want exact, so subtract the sequences where the gcd is a multiple of g
        numGreater = 0
        for multipleG in range(2 * g, K + 1, g):
            numGreater += numExact[multipleG]
        numExact[g] = numGreaterEq - numGreater
        ans += g * numExact[g]
        ans %= MOD

    return ans


if False:
    import random
    from itertools import product
    from math import gcd

    random.seed(0)
    for _ in range(10000):
        N = random.randint(1, 1)
        K = random.randint(1, 10)

        brute = 0
        for arr in product(range(1, K + 1), repeat=N):
            g = 0
            for x in arr:
                g = gcd(g, x)
            brute += g
        brute = brute % MOD

        ans = solve(N, K)
        # print(N, K, ans, brute)
        assert ans == brute


N, K = [int(x) for x in 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, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, 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, insort, insort_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 TUPLE(): return tuple(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 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()

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

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, 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, insort, insort_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 TUPLE(): return tuple(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 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()

gcd_cnt = [0]*(K+1)

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

ans = 0
for i, x in enumerate(gcd_cnt):
	ans += i*x
	ans %= mod

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

l = [0]*(k+1)

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
n, k = map(int, input().split())
mod = 10**9+7

d = [-1 for _ in range(k+1)]
d[k] = 1 

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

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

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
mod=10**9+7
X=[0]+[pow(K//d,N,mod) for d in range(1,K+1)]
'''
Y=[[] for i in range(K+1)]
for i in range(1,K+1):
    for j in range(i,K+1,i):
        Y[j].append(i)
'''
#print(X)
isPrime=[1 for i in range(K+1)]
isPrime[0]=0;isPrime[1]=0
for i in range(K+1):
    if isPrime[i]==0:
        continue
    for j in range(2*i,K+1,i):
        isPrime[j]=0
Mebius=[1 for i in range(K+1)]
Mebius[0]=0
for i in range(2,K+1):
    if isPrime[i]==0:
        continue
    for j in range(i,K+1,i):
        Mebius[j]*=-1
for i in range(2,K+1):
    for j in range(i*i,K+1,i*i):
        Mebius[j]=0
Z=[0 for i in range(K+1)]
for i in range(1,K+1):
    for j in range(i,K+1,i):
        Z[i]+=X[j]*Mebius[j//i]
ans=0
for i in range(1,K+1):
    ans+=Z[i]*i
    ans%=mod
print(ans)
'''
P(G%d==0)
Gがd,2d,3d,...の可能性がある
P(d)-P(2d)-P(3d)-P(5d)+P(6d)-P(7d)
'''

Submission status: Accepted

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

a = [0]*(k+1)

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

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

print(ans % mod)

Submission status: Accepted

Solution code:
import numpy as np
from numba import jit

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

@jit
def main():
  mod=10**9+7
  L=np.zeros(k+1,dtype='int64')
  ans=0
  for x in range(k,0,-1):
    lx=pow((k//x),n,mod)
    cnt=1
    while x*(cnt+1)<=k:
      cnt+=1
      lx-=L[x*cnt]
    L[x]=lx%mod
    ans+=(L[x]*x)%mod
  return ans%mod

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

Submission status: Accepted

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

for i in range(k,0,-1):
  lst[i]+=pow(k//i,n,mod)
  if k//i==1:
    continue
  else:
    for j in range(2,k//i+1):
      lst[i]-=lst[i*j]
      
for i in range(1,k+1):
  ans+=(i*lst[i])%mod
  ans%=mod
  
print(ans)

Submission status: Accepted

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

mod = 10**9+7

def power(a, n, mod):
    bi=str(format(n,"b")) #2進数
    res=1
    for i in range(len(bi)):
        res=(res*res) %mod
        if bi[i]=="1":
            res=(res*a) %mod
    return res

X = [0]*(k+1)

ans = 0
for g in reversed(range(1, k+1)):
    temp = power(k//g, n, mod)
    j = g
    while j <= k:
        temp -= X[j]
        j += g
    ans += temp*g
    X[g] = temp
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
MOD = 1000000007
cnt = [0] * (k + 1)
for i in range(1, k + 1):
    cnt[i] = pow(k // i, n, MOD)

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
MOD = 1_000_000_007
gcd_cnt = [0] * (K + 1)
for g in range(K, 0, -1):
    gcd_cnt[g] = pow(K // g, N, MOD)
    for g_mul in range(2, K // g + 1):
        gcd_cnt[g] -= gcd_cnt[g * g_mul]

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

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

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

cnt = [0] * (K + 1)

ans = 0
total = 0
for i in range(K, 0, -1):
    t = K // i
    now = my_pow(t, N, MOD)
    for j in range(i*2, K + 1, i):
        now -= cnt[j]
    cnt[i] = now
    ans += (now * i) % MOD
print(ans % MOD)

Submission status: Accepted

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


INF=10**20
def main():
    N,K=mi()
    MOD = 10**9+7

    ans = 0
    dic = {} 
    for x in range(K,0,-1):  # gcd = x となるA1~AN(<=K)を探す
        p_count = K//x
        count = pow(p_count,N,MOD)

        i = 2
        while x*i <= K:
            if not x*i in dic: break
            count -= dic[x*i]
            count %= MOD
            i += 1

        count %= MOD
        dic[x] = count
        
        ans += count * x
        ans %= MOD
        # print(x,count)
    
    print(ans)








if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0
A = [0 for _ in range(K+1)]
for i in range(1,K+1):
  ans += pow(K//i, N, MOD) * (i - A[i])
  ans %= MOD
  #print(ans, i)
  
  j = 2*i
  while j <= K:
    A[j] += i - A[i]
    j += i
    
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def main():
    N, K = (int(i) for i in input().split())
    g = [0]*(K+1)
    for k in range(1, K+1)[::-1]:
        cnt = K//k
        g[k] += pow(cnt, N, MOD)
        p = k
        while p + k <= K:
            p += k
            g[k] -= g[p]
        g[k] %= MOD
    ans = 0
    for i, g in enumerate(g[1:], start=1):
        ans += i*g
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

divisor_lst = [i - 1 for i in range(1, k + 1)]
divisor_lst[0] = 1

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

ans = 0
for num in range(1, k + 1):
    ans += pow(k // num, n, MOD) * divisor_lst[num - 1]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
#from line_profiler import LineProfiler
 
N, K = map(int, input().split())
mod = 10**9 + 7
def main():
  b = N
  blis = []
  c = 0
  while b >0:
    if b & 1 == 1:
      blis.append(c)
    c += 1
    b >>= 1


  def modpow(a, blis= blis, c = c):
    if a == 1:
      return 1
    else:
      res = 1
      li = []
      for _ in range(c):
        li.append(a%mod)
        a = a*a%mod
      for item in blis:
        res = res *li[item] %mod
      return res

    
  fact_count = [0 for _ in range(K+1)]
  for k in range(1, K+1):
    fact_count[k] = K//k

  ans = 0
  count = [0 for _ in range(K+1)]
  for k in range(K, 0, -1):
    x = 1*fact_count[k]
    cc = modpow(x)
    j = 2*k
    l = 2
    while(j<=K):
      cc -= count[j]
      l += 1
      j = k*l
    count[k] = cc
    cc = cc*k%mod
    ans += cc
    ans %= mod
  print(ans)
if __name__ == '__main__':
  main()
#prof = LineProfiler()
#prof.add_function(main)
#prof.runcall(main)
#prof.print_stats()

Submission status: Accepted

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

  
fact_count = [0 for _ in range(K+1)]
for k in range(1, K+1):
  fact_count[k] = K//k

ans = 0
count = [0 for _ in range(K+1)]
for k in range(K, 0, -1):
  c = pow(fact_count[k], N, mod)
  j = 2*k
  l = 2
  while(j<=K):
    c -= count[j]
    l += 1
    j = k*l
  count[k] = c
  c = c*k%mod
  ans += c
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

N, K  = list(map(int, input().split()))
ans = [0 for i in range(K+1)]

for i in range(K,0,-1):
    a = pow((K // i), N, mod)
    for j in range(2,K+1):
        if i*j <= K:
            a = (a - ans[i*j]) % mod
        else:
            break
    ans[i] = a % mod

# print(ans)

b = [i*ans[i] % mod for i in range(K+1)]
print(sum(b) % mod)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

class Eratosthenes:
    # https://cp-algorithms.com/algebra/prime-sieve-linear.html
    def __init__(self, n):
        primes = []
        lp = [0] * (n + 1)

        for i in range(2, n + 1):
            if lp[i] == 0:
                primes.append(i)
                lp[i] = i

            for pj in primes:
                if pj > lp[i] or i * pj > n:
                    break
                lp[i * pj] = pj
        self.primes = primes
        self.lp = lp

    def is_prime(self, x):
        return self.lp[x] == x

    def factrization(self, x):
        ret = []
        while x > 1:
            ret.append(self.lp[x])
            x //= self.lp[x]
        return ret

def main():
    N, K = LI()

    era = Eratosthenes(K)
    count = [0] * (K + 1)

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

    for i in range(1, K + 1)[::-1]:
        divs = era.factrization(i)
        candedates = [l for l in set(reduce(lambda x, y:x * y, ll, 1) for r in range(1, len(divs) + 1) for ll in itertools.combinations(divs, r))]
        for v in candedates:
            count[i // v] -= count[i]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def power(x, n, mod):
    ans = 1
    while n > 0:
        if n % 2 == 1:
            ans = ans * x % mod
        n //= 2
        x = x * x % mod
    return ans

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

mod = 10 ** 9 + 7

count = [0] * k
for i in range(k, 0, -1):
    count[i-1] = power(k // i, n, mod)
    j = i * 2
    while j <= k:
        count[i-1] -= count[j-1]
        j += i

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

Submission status: Accepted

Solution code:

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

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

for x in reversed(range(1, K + 1)):
    ctr[x] = pow(K // x, N, MOD)
    for y in range(2 * x, K + 1, x):
        ctr[x] -= ctr[y]

ans = 0
for n in range(1, K + 1):
    ans += n * ctr[n]
    ans %= MOD

print(ans)

Submission status: Accepted

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


def a(n):
    if n in memo:
        return memo[n]
    else:
        ret = pow(n, N, MOD)
        for i in range(2, n+1):
            ret -= a(n//i)
        memo[n] = ret
        return ret


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

Submission status: Accepted

Solution code:
def divisor(i):
    cnt = 0
    y = i ** (1 / 2)
    for j in range(1, int(y) + 1):
        if i % j == 0:
            cnt += (x[j] + x[i // j])
    if y % 1 == 0:
        cnt -= x[int(y)]
    return cnt

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

Submission status: Accepted

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

mod = 10**9 + 7
cnt = [0]*(k + 1)
ans = 0
for i in range(k, 0, -1):
    cnt[i] = (pow(k//i, n, mod) - sum(cnt[2*i:k+1:i])) % mod
    ans = (ans + i*cnt[i]) % mod

print(ans)

Submission status: Accepted

Solution code:

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

MOD = 10 ** 9 + 7

ctr = [0] * (K + 1)
for n in reversed(range(1, K + 1)):
    ctr[n] = pow(K // n, N, MOD)
    for j in range(2 * n, K + 1, n):
        ctr[n] -= ctr[j]

ans = 0
for n in range(1, K + 1):
    ans += n * ctr[n]
    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)
  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:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, k = map(int, input().split())
    mod = 10 ** 9+ 7
    table = [0]*(k+1)
    ans= 0
    for i in range(k, 0, -1):
        table[i] = pow(k//i, n, mod)
        j = 2
        while i*j <= k:
            table[i] -= table[i*j]
            table[i] %= mod
            j += 1
        ans += i*table[i]
        ans %= mod
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

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