Problem:


Score : 500 points

Problem Statement

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

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

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

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

Constraints

2 \leq N \leq 10^5

1 \leq K \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

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

Sample Input 1

3 2

Sample Output 1

9

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

Thus, the answer is 9.

Sample Input 2

3 200

Sample Output 2

10813692

Sample Input 3

100000 100000

Sample Output 3

742202979

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



Sample input:
3 2


Sample output:
9

Submission status: Accepted

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

# dp[i] := gcdがiになるようなものの通り数
dp = [0] * (K + 1)
for k in reversed(range(1, K + 1)):
    cnt = pow(K // k, N, MOD)
    for i in range(2, K + 1):
        if i * k > K:
            break
        cnt -= dp[i * k]
    dp[k] = cnt

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

Submission status: Accepted

Solution code:
from collections import Counter


def read():
    N, K = list(map(int, input().strip().split()))
    return N, K


def n_gcd(k, N, K, cache, MOD=10**9+7):
    if cache[k] != -1:
        return cache[k]
    n = pow(K // k, N, MOD)
    for j in range(2*k, K+1, k):
        n -= n_gcd(j, N, K, cache)
        n %= MOD
    cache[k] = n
    return n


def solve(N, K, MOD=10**9+7):
    cache = [-1 for k in range(K+1)]
    ans = 0
    for k in range(K, 0, -1):
        ans += n_gcd(k, N, K, cache) * k
        ans %= MOD
    return ans

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def pow(x, n):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = ans*x
      ans %= mod
    x = x*x
    x %= mod
    n = n >> 1
  return ans % mod

nums = [0 for _ in range(10**5 + 1)]

def f(i, N, K):
    # i no baisuu
    # i = K, K-1, ..., 1
    cnt = pow(K // i, N)
    # subtract 2i, 3i, 4i, ...
    j = i
    while j + i <= K:
        cnt -= nums[j+i]
        j += i
    nums[i] = cnt
    return nums[i]

def main():
    N, K = LI()
    cnt = 0
    for i in range(1, K+1)[::-1]:
        cnt += (i * f(i, N, K) % mod)
        cnt %= mod
    print(cnt)

main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
mod = 10**9+7
N, K = map(int, input().split())
ans = 0
cnt = np.zeros(K+1, np.int64)
for X in reversed(range(1,K+1)):
	a = K // X
	cnt[X] = pow(a,N,mod)
	x = 2
	res = 0
	while True:
		tmp = X * x
		if tmp > K:
			break
		res += cnt[tmp]
		res %= mod
		x += 1

	cnt[X] -= res
	cnt[X] %= mod
	ans += cnt[X] * X
	ans %= mod

print(ans)

Submission status: Accepted

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

print(answer)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

A = [0] * (K + 1)
for d in range(1, K + 1):
    A[d] = pow(K // d, N, MOD)  # 1～Kにdの倍数はK//D個あり、その組み合わせは最大 (K//d)**N ある
# print(A)

for d in range(K, 0, -1):
    for i in range(2, K // d + 1):
        A[d] -= A[d * i]    # dが約数だが最大公約数では無い組み合わせ（dの2～(K//d)倍の組み合わせ）を除外
# print(A)

ans = sum(d * x for d, x in enumerate(A))
ans %= MOD
print(ans)

Submission status: Accepted

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

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

for x in range(k,0,-1):
    for b in range(2, k//x+1):
        al[x] -= al[x*b]

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

Submission status: Accepted

Solution code:
a= list(map(int,input().split()))
N = a[0]
K = a[1]

a = [0]*K
mod = 10**9+7

for x in range(K,0,-1):
    a[x-1] = pow(K//x, N,mod)
    for t in range(2,K//x+1):
        a[x-1] -= a[t*x-1]

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

ans = s%mod

print(ans)

Submission status: Accepted

Solution code:

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

MOD = 10**9+7


gcd_dict = {}
for i in range(K, 0, -1):

    number = pow((K//i), N, MOD)
    number %= MOD
    counter = 2
    while True:
        if counter*i in gcd_dict:
            number -= gcd_dict[counter*i]
            counter += 1
        else:
            gcd_dict[i] = number % MOD
            break

print(sum([i*j for i, j in gcd_dict.items()]) % MOD)

Submission status: Accepted

Solution code:
import copy

MOD = 10 ** 9 + 7

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

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

    n //= 2

  return (x * K) % mod

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

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

Submission status: Accepted

Solution code:
MOD = int(1e+9 + 7)
N, K = map(int, input().split())
 
cnt = [0] * (K + 1) # 要素が全てXの倍数となるような数列の個数をXごとに求める
for x in range(1, K + 1):
    cnt[x] = pow(K // x, N, MOD)
for x in range(K, 0, -1): # 2X, 3Xの個数を求めてひく
    for i in range(2, K // x + 1):
        cnt[x] -= cnt[x * i]
ans = 0
for k in range(K+1):
    ans += cnt[k] * k
ans = ans % MOD
print(ans)

Submission status: Accepted

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

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

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

cnt = [0] * (K + 1)

def calc(x):
    M = K // x
    c = pow(M, N, MOD)
    for i in range(x + x, K + 1, x):
        c -= cnt[i]
    cnt[x] = c
    return c * x

ans = 0
for x in range(1, K + 1)[::-1]:
    ans = (ans + calc(x)) % MOD
print(ans)

Submission status: Accepted

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

L=[0]*(K+1)
for i in range(1,K+1)[::-1]:
    minus=0
    count=2
    while True:
        if count*i<=K:
            minus+=L[count*i]
            minus=minus%P
            count+=1
        else:
            break

    L[i]=(pow(K//i,N,P)-minus)%P

ans=0
for j in range(1,K+1):
    ans+=j*L[j]
    ans=ans%P

print(ans)

Submission status: Accepted

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

patterns = [0] * k
total = 0

for i in range(k, 0, -1):
    # gcdがちょうどi ⇔ すべての要素がiの倍数
    # かつ　すべての要素が2i, 3i, ...の倍数でない
    tmp = pow(k // i, n, MOD)

    for j in range(2*i, k+1, i):
        tmp -= patterns[j-1]
    
    patterns[i-1] = tmp
    total += i * tmp
    total %= MOD

print(total)

Submission status: Accepted

Solution code:
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


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


def main():
    N, K = wi()
    mod = 10 ** 9 + 7
    res = 0
    d = [0]*K

    for i in range(K, 0, -1):
        n = pow(K//i, N, mod)

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

        d[i-1] = n
        res += n*i
        res %= mod
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 1000000007

def pow_mod(x, y):
    res = 1
    while y > 0:
        if y % 2:
            res *= x
            res %= mod
        x *= x
        x %= mod
        y //= 2
    return res

def divs(x):
    res = []
    for i in range(1, x+1):
        if i * i > x:
            break
        if x % i != 0:
            continue
        res.append(i)
        if i != x // i:
            res.append(x // i)
    return res

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

num = [0] * 100010
for g in range(1, K+1):
    num[g] = pow_mod(K // g, N)


for x in range(K, 0, -1):
    div = divs(x)
    for i in div:
        if i == x:
            continue
        num[i] += mod - num[x]
        num[i] %= mod

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

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    MOD = 10**9 + 7
    cnt = [0 for _ in range(K)] # k番目の要素はgcd(A)==k+1(x)となるような数列Aの個数
    ans = 0

    for k in range(K)[::-1]:
        x = k+1

        ### gcd(A)がxの倍数となるような数列Aの個数
        cnt[k] = pow((K//x), N, MOD) # (K//x)**Nでは計算量がかかる
        cnt[k] %= MOD
        ### gcd(A)が2x, 3x...となる数列Aの個数を引く。
        for j in range(2*x, K+1, x):
            cnt[k] -= cnt[j-1]
            cnt[k] %= MOD

        ans += cnt[k]*x
        ans %= MOD
    print(ans)
main()

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
 
sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

MOD = 10 ** 9 + 7
N, K = map(int, input().split())
count = Counter()
for i in reversed(range(1, K + 1)):
    c = pow(K // i, N, MOD)
    j = 2
    while i * j <= K:
        c -= count[i * j]
        j += 1
    count[i] = c
print(sum(i * j for i, j in count.items()) % MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9+7
N, K = map(int, input().split())  # N個の整数列, 要素は1~Kの値を取る
# 数列の最大公約数がk(1<=k<=K)の通りを考える
ans = 0
cnt = [0]*(K+1)
for k in reversed(range(1, K+1)):
    cnt[k] = pow((K//k), N, MOD)
    tmp = k * 2  # 2倍したもの
    while tmp <= K:
        cnt[k] -= cnt[tmp]
        tmp += k
for i in range(K+1):
    ans += cnt[i]*i
    ans %= MOD
print(ans)

Submission status: Accepted

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

for i in range(K, 0, -1):
    n = pow(K//i, N, p)

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

    d[i-1] = n
    res += n*i
    res %= p

print(res)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from bisect import bisect_left,bisect_right
from collections import deque

    
def main():
    n,k = map(int,input().split())
    ans = 0
    G = [0] * (1 + k)
    for g in range(k,0,-1):
        ret = pow((k//g),n,MOD)
        for j in range(2 * g,k + 1,g):
            ret -= G[j]
        G[g] = ret
        ans += ret * g
        ans %= MOD
    
    print(ans) 

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
n,k = map(int,input().split())
m = 10**9 + 7
gcds = np.zeros(k+1, int)
ans = 0

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

Submission status: Accepted

Solution code:
from collections import defaultdict

N, K = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
dd = defaultdict(int)

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

Submission status: Accepted

Solution code:
import numpy as np
n,k = map(int,input().split())
m = 10**9 + 7
gcds = np.zeros(k+1, int)

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

Submission status: Accepted

Solution code:
import math

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

dic = {} #ここに結果を保存していく。
ans = 0
moddo = 10**9+7

for i in range(k):
    t = k - i #これで大きいほうから順にとる。
    if t > k/2: #tがk/2より大きいときはすべてtじゃないと最大公約数はtにならない。
        dic[t] = 1
        ans += t
    else:
        temp = pow(k//t,n,moddo)
        #print(temp)
        fac = 2
        while fac*t <= k:
            temp -= dic[fac*t]
            fac += 1
        dic[t] = temp%moddo
        ans = (ans+((temp*t)%moddo))%moddo

print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007
def mod_pow(x , y):
    if y == 0:
        return 1
    if y == 1:
        return x
    r = mod_pow(x , y // 2)
    r2 = (r * r) % MOD
    if y % 2 == 0:
        return r2 % MOD
    else:
        return (r2 * x) % MOD

N , K = map(int , input().split())
result = 0
memo = {}
for g in range(K , 0 , -1):
    comb = mod_pow(K // g , N)
    for j in range(2 , K // g + 1):
        comb = (comb - memo[j * g] + MOD) % MOD
    memo[g] = comb
    result = (result + comb * g) % MOD
print(result)

Submission status: Accepted

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

mod=10**9+7

pow_table={}
def eco_pow(x):
    if x in pow_table:
        return pow_table[x]
    else:
        pow_table[x]=pow(x,n,mod)
        return pow_table[x]
    
ans=0
res_dic={}
for i in range(k):
    now=k-i
    all_now_res=eco_pow(k//now)
    del_now_res=0

    for q in range(2*now,k+1,now):
        #print(now,q)
        del_now_res+=res_dic[q]

    res_dic[now]=(all_now_res-del_now_res)%mod
    #print(res_dic[now])
    ans+=res_dic[now]*now
    ans%=mod

print(ans)

Submission status: Accepted

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

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

for x in range(K,0,-1):
  num[x]=pow(K//x,N,DIV)
  for temp in range(x*2,K+1,x):
    num[x]-=num[temp]
  ans += num[x] * x
  ans %= DIV

print(ans)

Submission status: Accepted

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

cnt = dict(zip(range(1,k+1), [0] * k))
for i in range(1, k+1)[::-1]:
    cnt[i] = pow((k // i), n, 10**9+7)

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

print(ans % (10 ** 9 + 7))

Submission status: Accepted

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

ns = [0] * n
ans = 0

def modpow(a,n,mod=1000000007):
    if n==0:
        return 1
    elif n%2==0:
        return modpow(a*a%mod, n//2, mod)
    else:
        return a * modpow(a,n-1,mod) % mod

for i in range(n,0,-1):
    # ns[i-1] = ((n//i)**k) % (10**9+7)
    ns[i-1] = modpow(n//i,k)
    for j in range(2*i,n+1,i):
        ns[i-1] -= ns[j-1]
    ans += (i * ns[i-1])%(10**9+7)
    ans %= (10**9+7)

print(ans)

Submission status: Accepted

Solution code:
import math

def pow(p,n):
    bin_n=bin(n)[2:][::-1]
    tmp=p;pn=1
    for i in range(len(bin_n)):
        if bin_n[i]=="1": pn=(pn*tmp)%mod
        tmp=tmp*tmp%mod
    return pn


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

ans=[0]*(k+1)
for i in range(k,0,-1):
    div=set()
    for x in range(1,int(i**0.5)+1):
        if i%x==0: div.add(x);div.add(i//x)
    ans[i]=pow(k//i,n)-sum([ans[j*i] for j in range(k//i,1,-1)])
    ans[i]%=mod
print(sum(ans[i]*i for i in range(k+1))%mod)

Submission status: Accepted

Solution code:
import math

def pow(p,n):
    bin_n=bin(n)[2:][::-1]
    tmp=p;pn=1
    for i in range(len(bin_n)):
        if bin_n[i]=="1": pn=(pn*tmp)%mod
        tmp=tmp*tmp%mod
    return pn


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

ans=[0]*(k+1)
for i in range(k,0,-1):
    div=set()
    for x in range(1,int(i**0.5)+1):
        if i%x==0: div.add(x);div.add(i//x)
    ans[i]=pow(k//i,n)-sum([ans[j*i] for j in range(k//i,1,-1)])
    ans[i]%=mod

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

gcd = [0] * k
for i in range(k):
    test = k - i
    temp = 0
    for j in range(k // test):
        if j == 0:
            temp2 = 1
            temp3 = [k // test]
            for l in range(len(bin(n)) - 2):
                temp3.append(temp3[-1] ** 2 % mod)
            test3 = bin(n)
            for l in range(len(test3) - 2):
                if test3[-1-l] == "1":
                    temp2 *= temp3[l]
                    temp2 %= mod
            temp += temp2
        else:
            test2 = test * (j + 1)
            temp -= gcd[test2 - 1]
    gcd[test - 1] = temp
ans = 0
for i in range(k):
    ans += gcd[i] * (i + 1)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt

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

fn=[0 for i in range(0,K+1)]
fn[0]=0
fn[1]=1
for i in range(2,K+1):
    I=int(sqrt(i))
    s=sum(fn[i//g] for g in range(1,I+1))
    t=0
    r=i//(I+1)
    for j in range(1,r+1):
        t=(t+(i//j-i//(j+1))*fn[j])%mod
    fn[i]=(pow(i,N,mod)-s-t)%mod

ans=0
for g in range(1,K+1):
    ans=(ans+g*fn[K//g])%mod

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


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

Submission status: Accepted

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

# List containing the number of sequences for each greatest common divisor.
num_sequence_list = [0] * (MaxNum + 1)

total_value = 0
for i_divisor in range(MaxNum, 0, -1):
    num_sequence = pow(MaxNum//i_divisor, NumSeq, mod)

    for j_multiple in range(2, MaxNum//i_divisor+1):
        num_sequence -= num_sequence_list[i_divisor*j_multiple]

    num_sequence_list[i_divisor] = num_sequence
    total_value += num_sequence * i_divisor

print(total_value % mod)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
mod = 10**9+7
# 最大公約数がx(1 <= x <= k)な数列の数
num_gcd_k = [0]*(k+1)
num_gcd_k[k] = 1
ans = 0
for i in range(k,0,-1):
    # total = ((k // i)**n)%mod
    total = pow(k//i,n,mod)
    m = 2
    while i*m <= k:
        total -= num_gcd_k[i*m]
        m += 1
    num_gcd_k[i] = total
    ans += i*total
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
md = pow(10,9) + 7

cnt_memo = [0]*(K+1)
cnt_R_memo = [0]*(K+1)

def main():
    ret = 0
    for k in range(1,K+1):
        cnt_R_memo[k]=pow(K//k,N,md)
    for k in range(K,0,-1):
        cnt_memo[k]=(cnt_R_memo[k] - sum(cnt_memo[2*k::k]))%md
        ret += (cnt_memo[k]*k)%md
    print(ret%md)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    ans += i*a2
    l[i] = a2
    ans %= mod
    
print(ans)

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from math import sqrt

def prime_division(x):
    q = int(sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

def divisorlist(z): # z : output of prime_division
    #ddprint(f"dvl {z}")
    if len(z)==1:
        return [z[0][0]**i for i in range(z[0][1]+1)]
    y = divisorlist(z[1:])
    s = []
    for i in range(z[0][1]+1):
        for j in y:
            s.append((z[0][0]**i)*j)
    return s

n,k = inm()
d = [0]*(k+1)
d[1] = pow(k,n,R)
sm = 0
for i in range(k,1,-1):
    d[i] = (d[i]+pow(k//i,n,R))
    ps = divisorlist(prime_division(i))
    for p in ps:
        if p!=i:
            d[p] = (d[p]-d[i])%R
    sm = (sm+d[i]*i)%R
#ddprint(d)
print((sm+d[1])%R)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()

def divisors(n):
    S,T=[],[]
    for i in range(1,int(n**.5)+1):
        if(n%i==0):
            S.append(i)
            T.append(n//i)
    T.reverse()
    return S+T if(S[-1]!=T[0]) else S+T[1:]

def resolve():
    n, k = map(int,input().split())
    C = [0] * (k + 1)
    for i in range(1, k + 1):
        C[i] = pow((k // i), n, MOD)

    for i in range(k, 1, -1):
        for d in divisors(i):
            if i == d:
                continue
            C[d] -= C[i]

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

    print(res)
resolve()

Submission status: Accepted

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

mod = 10**9+7

# i = 1, 2, ... k について最大公約数がiになる数列を数え上げる
count = [0 for _ in range(K+1)]
for i in range(K, 0, -1):
    count[i] = pow(K//i, N, mod)
    for j in range(2*i, K+1, i):
        count[i] -= count[j]

# それに数をかけて和を求める
ans = 0
for i, c in enumerate(count):
    ans += i*c % mod

print(ans % mod)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(sum(i*cnt[i] for i in range(1, k+1)) % m)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9 + 7

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

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

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

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

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,k = m()

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

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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

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

print(ans)

Submission status: Accepted

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

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

for i in range(k, 0, -1):
    tmp = pow(k // i, n, 10**9 + 7)
    for j in range(i, k+1, i):
        tmp -= ansl[j]
    ansl[i] = tmp % (10**9 + 7)

ans = 0
for i in range(1, k+1):
    ans += i * ansl[i]
    ans %= 10**9 + 7
print(ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

def main():
    mod = 1_000_000_007
    n, k = map(int, input().split())
    arrs = [0] * (k + 1)
    for i in range(k, 0, -1):
        arrs[i] = pow(k // i, n, mod)
        for j in range(i * 2, k + 1, i):
            arrs[i] -= arrs[j]
    ans = 0
    for i in range(1, k + 1):
        ans = (ans + arrs[i] * i % mod) % mod
    print(ans)

main()

Submission status: Accepted

Solution code:
# ABC162
n,k=map(int,input().split())
"""
3 2
->9
3 200
->10813692
100000 100000
->742202979
"""
ans = 0
xl=[0]*(k+1)
MOD = int(1e+9 + 7)

for x in range(k,0,-1):
    xl[x] = pow(k // x,n, MOD) 

for x in range(k,0,-1):
    xl[x] -= sum([xl[i*x] for i in range(2,1 + k//x)])

ans = 0
for i in range(k+1):
    ans += i * xl[i]

print(ans % MOD)

Submission status: Accepted

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

ans=0
MOD=10**9+7

cnt=[0]*(K+1)
for x in reversed(range(1,K+1)):
    cnt_tmp = pow(K//x,N,MOD)#xの倍数のみで作れるlen=Nの数列の総数
    t=1
    while (t+1)*x<=K:
        t+=1
        cnt_tmp -= cnt[x*t] #cnt_tmpのうち,gcd=2x,3x...になるものを除く

    cnt[x]=cnt_tmp
    ans += x*cnt_tmp
    ans%=MOD
print((ans+MOD)%MOD)

Submission status: Accepted

Solution code:
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())
mod=10**9+7
memo=[pow(k//i,n,mod) for i in range(1,k+1)] #gcdが1~kになる場合をメモする
for i in range(k-1,-1,-1):
    x=make_divisors(i+1)
    for j in x:
        if j!=i+1:
            memo[j-1]-=memo[i]
ans=0
for i in range(k):
    ans+=(memo[i]*(i+1))
    ans%=mod
print(ans)

Submission status: Accepted

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

ans=0
MOD=10**9+7

cnt=[0]*(K+1)
for x in reversed(range(1,K+1)):
    t = K//x
    cnt_tmp = pow(t,N,MOD)
    t=1
    while (t+1)*x<=K:
        t+=1
        cnt_tmp -= cnt[x*t]
    g = x*cnt_tmp %MOD
    cnt[x]+=cnt_tmp
    ans +=g
    ans%=MOD
print(ans)