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
#input=sys.stdin.readline
#sys.setrecursionlimit(1000000)
mod=int(1000000007)
#I=lambda: map(int,input().split())

def bm(n,p):
    n,p=int(n),int(p)
    if p==0:
        return 1
    x=bm(n,p/2)
    x=(x*x)%mod
    if p%2==1:
        x=(x*n)%mod
    return x

dp=[0]*(100000+2)
ans=0
n,k=map(int,input().split())

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
mod = 10 ** 9 + 7
ans = 0
GCD = [0 for i in range(K+1)]
for i in range(K, 0, -1):
    # gcd(a1,a2,a3....an)=i の物の数
    S = pow(K//i, N, mod)
    for j in range(2, K//i + 1):
        S -= GCD[j*i]
    GCD[i] = S % mod
for i in range(1, K+1):
    ans += GCD[i]*i
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
class GCD:

    def __init__(self, N, K, MOD):
        self.N = N
        self.K = K
        self.MOD = MOD
        self.gcd_count_list = []
        self.gcd_count_list2 = [0]*self.K
        for d in range(1,self.K+1):
            self.gcd_count_list.append(self.gcd_count(d))
        self.gcd_count2()

    def gcd_count(self, d):
        """  d, 2d, 3d,... の最大公約数を持つ K 以下の整数 N 個の組の数　"""
        return pow(self.K//d,self.N,self.MOD)

    def gcd_count2(self):
        """  dの最大公約数を持つ K 以下の整数 N 個の組の数　"""
        res = []
        i = 1
        while K//i > 0:
            for j in range(K//(i+1)+1,K//i+1):
                self.gcd_count_list2[j-1] = self.gcd_count_list[j-1] \
                - sum(self.gcd_count_list2[j*k-1] for k in range(2, i+1))
            i += 1

    def solve(self):
        return sum(d*self.gcd_count_list2[d-1] for d in range(1,K+1))%MOD

N, K = map(int, input().split())
MOD = 10**9 + 7
g = GCD(N, K, MOD)
print(g.solve())

Submission status: Accepted

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

Submission status: Accepted

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

def pk(x,n,mod):
    if n == 0:
        return 1

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

    return K * x % mod


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

Submission status: Accepted

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

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

print(ans % mod)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
[N,K] = list(map(int,input().split()))
S = 0
out = [0]*(K+1)
p = 10**9+7
for i in range(K):
    X = K-i
    out[X] = pow(int(K/X),N,p)
    t=2
    while t*X<=K:
        out[X] = out[X]-out[t*X]
        t+=1
    S = (S + X*out[X])%p
print(S)

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

# 1-indexed
l = [0]*(K+1)
for i in range(1, K+1):
    p = pow(K//i, N, MOD)
    l[i] = p

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

r = 0
for i, l_i in enumerate(l):
    r = (r + (i*l_i) % MOD) % MOD

print(r)

Submission status: Accepted

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

# cnt(n): gcd = n となる数列の個数
cnt = [0] * (K + 1)

# A1,...,ANのすべてがxの倍数である数列の個数 = floor(k/x)^N個
for n in range(1, K + 1):
    cnt[n] = pow(K // n, N, MOD)

res = 0
for k in range(K, 0, -1):
    p = 2
    while p * k <= K:
        cnt[k] -= cnt[p * k]
        cnt[k] %= MOD
        p += 1
    res += cnt[k] * k
    res %= MOD

print(res)

Submission status: Accepted

Solution code:
import sys 
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7    
N, K = map(int, readline().split())
d = [0] * (K+1)
for i in range(K,0,-1):
    t = K // i
    cnt = pow(t,N,MOD)
    for j in range(2,t+1):
        cnt -= d[i*j]
        cnt %= MOD
    d[i] = cnt
ans = 0
for num,cnt in enumerate(d):
    ans += num * cnt
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def pow(a, n, mod):
    ret = 1
    pw = a
    while n > 0:
        if n & 1 == 1:
            ret *= pw
            ret %= mod
        n >>= 1
        pw *= pw
        pw %= mod
    return ret


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    n_gcds = [0 for _ in range(K + 1)]
    for g in range(K, 0, -1):
        v = pow(K // g, N, MOD)
        gg = g
        while gg + g <= K:
            gg += g
            v -= n_gcds[gg]
            v %= MOD
        n_gcds[g] = v
    ans = 0
    for g, n in enumerate(n_gcds):
        ans += g * n
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

print(ans%P)

Submission status: Accepted

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


dp = [0]*(k+1)
for i in reversed(range(1, k+1)):
    if not cnt[i]:
        continue
    tmp = cnt[i]
    for j in range(2, k+1):
        if k < i*j:
            break
        tmp -= dp[i*j]
        tmp %= MOD
    dp[i] = tmp

ans = 0
for i in range(1, k+1):
    ans += i*dp[i]
    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"))
    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 i in reversed(range(1, k+1)):
    temp = power(k//i, n, mod)
    j = i
    while j <= k:
        temp -= X[j]
        j += i
    ans += temp*i
    ans %= mod
    X[i] = temp
print(ans%mod)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
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 reversed(range(1, K + 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)

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)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = map(int, input().split())
M = 10**9+7
nums = [0]*(k+1) # gcd==kなる数列の個数
for i in range(k, 0, -1):
    nums[i] = pow(k//i, n, M)
    for j in range(2*i, k+1, i):
        nums[i] -= nums[j]
    nums[i] %= M
ans = sum(i*item for i,item in enumerate(nums))%M
print(ans)

Submission status: Accepted

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    


    def solve(n, k):
        ans = 0
        num_of_total_gcd = [0] * (k + 1)
        for m in range(k, 0, -1):
            cnt = pow(k//m, n, mod)
            for i in range(2, k+1):
                if m * i <= k:
                    cnt -= num_of_total_gcd[m * i]
                else:
                    break
            num_of_total_gcd[m] = cnt % mod
            ans = (ans + m * cnt) % mod
        return ans


    
    n, k = mi()
    print(solve(n, k))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
prime_mod = 10**9+7
countgcd = [0]*k
for idx in range(k, 0, -1):
  num_multiples = k//idx
  num_sequences = pow(num_multiples, n, prime_mod)
  overcount = sum(countgcd[j*idx-1] for j in range(2, num_multiples+1))
  overcount = overcount%prime_mod
  countgcd[idx-1] = (num_sequences-overcount)%prime_mod
  # print(idx, num_multiples, num_sequences, overcount, num_sequences-overcount)
final_sum = 0
for idx in range(1, k+1):
  final_sum = (final_sum + idx*countgcd[idx-1])%prime_mod
print(final_sum)

Submission status: Accepted

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

mod=10**9+7

A=[0]*K

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

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

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

print(s)

Submission status: Accepted

Solution code:

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

    for g in range(K, 0, -1):
        cnt[g] = pow(K//g, N, MOD) # (K//g)**N
        gg = g*2
        while gg <= K:
            cnt[g] -= cnt[gg]
            gg += g
    ans = 0
    for g in range(1, K+1):
        ans += cnt[g] * g
        ans %= MOD
    print(ans)    

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

cnt_l = [0]*(k+1)
MOD = 10**9+7

for i in range(k,0,-1):
    multi_cnt = k//i
    cnt = pow(multi_cnt,n,MOD)
    
    i_multi = i+i
    while i_multi <= k:
        cnt -= cnt_l[i_multi]
        i_multi+=i

    cnt_l[i] = cnt%MOD

ans = 0
for i, cnt in enumerate(cnt_l):
    ans += i*cnt
    ans %= MOD

# print(cnt_l)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
MOD = 10**9+7
ls = [0]*(K+1) #個数
for i in range(1, K+1)[::-1]:
  ls[i] =  pow(K // i, N, MOD)
  if K // i != 1:
    a = K // i
    for j in range(2, a+1):
      ls[i] -= ls[i*j]  
    
ans = 0
for i in range(1, K+1):
  ans += i * ls[i]
  ans %= MOD  
print(ans)

Submission status: Accepted

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    N,K=map(int,input().split())
    # gcd=i
    dp=[0]*(K+1)
    MOD=10**9+7
    for i in range(K,0,-1):
        x=(K//i)
        dp[i]=pow(x,N,MOD)
        # (x**N)%MOD、pow(x,N)%MODはTLEE
        for j in range(2,x+1):
            dp[i]-=dp[i*j]
            dp[i]%=MOD
    ans=0
    for i in range(K+1):
        ans+=i*dp[i]
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
mod = 10**9 + 7
# For each X, in 1<= X <= K, let us find the number of sequences {A1, A2, .., An} with GCD = X. 

# The necessary and sufficient condition of the greatest common divisor being a multiple of X
# is that all the A1, ..., AN are multiples of X. The number of such sequences is (floor(K/X))^N.
# The necessary and sufficient condition of it being **exactly** X is that it is a multiple of X, but
# not 2X, 3X.... If they are calculated in the decreasing order of X, it can be found by subtracting
# the number of those of 2X, 3X

# Let dp[i] store the number of sequences whose GCD is i.
dp = [0]*(k+1)
for i in range(k, 0, -1):
    # no. of sequences whose gcd is a multiple of i.
    dp[i] = pow(k//i, n, mod)

    # no. of sequences whose gcd is exactly i. 
    for j in range(2*i, k+1, i):
        dp[i] -= dp[j]

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

Submission status: Accepted

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

#k以下のn個の数字

ans=[0]*(k+1)
p=10**9+7
result=0
for i in range(k):
    num=k-i

    ans[num]=pow(k//num,n,p)
    j=2
    while num*j<=k:
        ans[num]-=ans[num*j]
        j+=1
    result+=((ans[num]*num)%p)    
    #print(num,ans)
print(result%p)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def solve(N: int, K: int):
    ret = 0
    counts = [0] * (K + 1)
    for i in range(1, K + 1)[::-1]:
        c = K // i
        cnt = pow(c, N, MOD)
        j = 2
        while i * j <= K:
            cnt -= counts[i * j]
            j += 1
        ret += cnt * i
        ret %= MOD
        counts[i] = cnt
    #print(counts)
    print(ret)
    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:
n,k = map(int,input().split())
mod = 10**9+7
"""
dp[i] := gcd(a1,...,an) = i となるものがいくつあるか
"""
dp = [0 for _ in range(k+1)]
subdp = [0 for _ in range(k+1)]
for i in range(1, k+1)[::-1]:
	target = pow(k//i, n, mod)
	for j in range(2*i, k+1, i):
		target -= dp[j]
	dp[i] = target
ans = 0
for i in range(k+1):
	ans = (ans + dp[i]*i) % mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N,K = getNM()
ans = 0
rec = [0] * (K + 1)

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, K = getNM()
memo = [-1] * (K + 1)

# 2の倍数だけで作った組み合わせ - ４の倍数だけで作った組み合わせ - ６の...
def rec(x):
    if memo[x] >= 0:
        return memo[x]
    multi = 0
    # x * 2, x * 3...について
    for i in range(x * 2, K + 1, x):
        multi += rec(i)
    memo[x] = pow(K // x, N, mod) - multi
    res = memo[x]
    return res

ans = 0
rec(1)
for i in range(1, K + 1):
    ans += i * memo[i]
print(ans % mod)

Submission status: Accepted

Solution code:
# E - Sum of gcd of Tuples (Hard)
MOD = 10**9+7

def pow_mod(x,n):
    if n==0:
        return 1
    elif n%2==0:
        return (pow_mod((x**2)%MOD,n//2))%MOD
    else:
        return (x*pow_mod((x**2)%MOD,n//2))%MOD

N,K = map(int,input().split())
ans = 0
rec = [0]*(K+1)
for X in range(K,0,-1):
    rec[X] = pow_mod(K//X,N)
    for i in range(2,K//X+1):
        rec[X] = (rec[X]-rec[i*X])%MOD
    ans = (ans+X*rec[X])%MOD
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

n, k = map(int, input().split())
num = [0]*k
for i in reversed(range(1, k+1)):
    count = pow(k//i, n, MOD)
    for j in range(2, (k//i)+1):
        count = (count - num[j*i - 1])%MOD
    num[i-1] = count

# print(num)
print(functools.reduce(lambda s, x: ((x[0]+1) * x[1] + s)%MOD, enumerate(num), 0))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
num=[0]*k
ans=0

def njo(arg,n):
  if n==0:
    return 1
  elif n%2==0:
    return njo((arg**2)%1000000007,n//2)
  else:
    return arg*njo((arg**2)%1000000007,n//2)

for i in range(k):
  test=k-i
  num[test-1]=njo(k//test,n)
  mul=test*2
  while mul<=k:
    num[test-1]-=num[mul-1]
    mul+=test

  ans+=num[test-1]*test
  
while ans<0:
  ans+=1000000007
print(str(ans%1000000007))

Submission status: Accepted

Solution code:
def modpow(val, n, mod):
    ret = 1
    while n:
        if n & 1:
            ret = (ret * val) % mod
        val = (val * val) % mod
        n = n >> 1
    return ret


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

my_dict = dict()
ret = 0

for i in range(k, 0, -1):
    tmp = modpow(k // i, n, mod)
    cnt = 2
    while True:
        val = i * cnt
        if val > k:
            break
        else:
            cnt += 1
            tmp -= my_dict[val]
    my_dict[i] = tmp
    ret += tmp * i % mod

print(ret % mod)

Submission status: Accepted

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

c=0
for i in range(len(D)):
  c+=D[i]*i
print(c%mod)

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()))

MOD = 10 ** 9 + 7
# gcdがNから順に数える、resetを用意、約数をそれぞれ引く

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

N, K = lr()
answer = 0
reset = [0] * (K+1)
for x in range(K, 0, -1):
    #gcdがx
    nums = K // x
    add = pow(nums, N, MOD)
    add -= reset[x]
    answer += add * x
    answer %= MOD
    divs = make_divisors(x)
    for d in divs:
        reset[d] += add

print(answer%MOD)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
gcddic = {}
mod_n = (10**9+7)
for i in range(K,0,-1):
    x = pow((K//i),N,mod_n)
    ll=2
    while(ll*i<=K):
        x -= gcddic[ll*(i)]
        ll += 1
    gcddic[i] = x
sumnation = 0
for i,l in gcddic.items():
    sumnation += i*l
print(sumnation%mod_n)

Submission status: Accepted

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

    M={}

    mod=pow(10,9)+7
    res=0
    for i in range(K,0,-1):
        syou=K//i
        mc=pow(syou,N,mod)
        if syou>=2:
            for sub_m in range(2,syou+1):
                mc-=M[sub_m*i]
        res+=(i*mc)%mod
        M[i]=mc

    print(res%mod)

if __name__=="__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
res = 0
cnt = [0] * (k + 1)
M = int(1e9) + 7

def pow(b, e, m):
    res = 1
    while e:
        if e & 1: res = res * b % m
        e >>= 1
        b = b * b % m
    return res

for i in reversed(range(1, k + 1)):
    t = k // i
    cnt[i] = pow(t, n, M)
    for j in range(i + i, k + 1, i):
        cnt[i] -= cnt[j]

    res = (res + cnt[i] * i) % M

print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N,K=LI()

BUF=[0]*(K+1)
for i in reversed(range(1, K+1)):
    pat = POW(K//i, N)
    for j in range(2, K+1):
        if i*j <= K:
            pat -= BUF[i*j]
        else:
            break
    # print("pat:{} i:{}".format(pat, i))
    BUF[i] = pat

res = 0
for i, j in enumerate(BUF):
    res += (i*j) % DVSR
print(res%DVSR)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, K = LI()

# 逆に考える
"""
X = gcd(A_1, A_2,...A_K)
となるようなXを考えると溶ける
X = 3の時その個数は
[K/3]**N
"""

x_cnt = [0] * (K + 1)
for x in range(K, 0, -1):
    # print(x)
    tmp = pow(K // x, N, mod)
    for j in range(x + x, K+1, x):
        tmp -= x_cnt[j]
    x_cnt[x] = tmp

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

Submission status: Accepted

Solution code:
'''
@sksshivam007 - Template 1.0
'''
import sys, re, math
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))[::-1]
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))

INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

a = [0]*(k+1)

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

print(final%mod)

Submission status: Accepted

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