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

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

Submission status: Accepted

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

for i in range(k, 0, -1):
    cnt[i] = pow((k // i), n, p)
    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))) % p)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    N,K=map(int,input().split())
    l=[0]*(K+1)
    ans=0
    for i in range(K,0,-1):
        tmp=pow(K//i,N,MOD)
        j=i*2
        while j<=K:
            if j>K:
                continue
            tmp-=l[j]
            tmp=(tmp+MOD)%MOD
            j+=i
        l[i]=tmp
        ans+=tmp*i
        ans%=MOD
    print(ans)
    
        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = [int(x) for x in input().split()]
mod = 1000000007
l = [pow(K//x, N, mod) for x in range(1, K+1)]
l.insert(0, 0)
ans = 0
for i in range(K, 0, -1):
    t = i * 2
    while(t <= K):
        l[i] -= l[t]
        t += i
for i in range(K+1):
    ans = (ans + l[i] * i) % 1000000007
if ans < 0:
    ans = 1000000007 - ans
print(ans)

Submission status: Accepted

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

As = [0]*(K+1)
X = K
while X>0:
    # 最大公約数がXの倍数となる数列の個数
    As[X] = pow((K//X),N,M)
    m = 2
    while m*X<=K:
        As[X] -= As[m*X]
        m += 1
    X -= 1
# print(As)
# print(sum(As))
c = 0
for i in range(1,K+1):
    c = (c+i*As[i]%M)%M
print(c)

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10 ** 9 + 7

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))



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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
gcd_num = [0 for i in range(k+1)]
c = 10**9 + 7
ans = 0
for i in range(k,0,-1):
  x = k//i
  #gcd = xを満たす何組あるかのあまりを計算
  #あまりを取らないとオーバーフローする
  gcd_num[i] = pow(x,n,c)
  #重複するのを取り除く
  for j in range(2,x+1):
    gcd_num[i] -= gcd_num[i * j]
  #最後にgcdの大きさによる重み付けする
  ans += gcd_num[i] * i
  
print(ans%c)

Submission status: Accepted

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

x = [0 for _ in range(k+1)]

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

Submission status: Accepted

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

MOD = 1000000007  # type: int


# 数列の中に1は含まれてはいないが、gcd=1となるような場合を数え抜けている。
# これらを追加で数え上げるのは難しそうなので、この方針ではダメなのかもしれない。
def solve(N: int, K: int):
    # sm = 0
    # for n in range(1, K + 1):
    #     if int(K / n) > int(K / (n + 1)):
    #         sm += (int(K / n) + int(K / (n + 1)) + 1) * (int(K / n) - (int(K / (n + 1)))) / 2 * ((modpow(n, N) - modpow(n - 1, N)) % MOD)
    #         print("{0} - {1}".format(K / n, K / (n + 1)))
    #         print(((modpow(n, N) - modpow(n - 1, N)) % MOD))
    #         sm %= MOD

    # print(int(sm))
    # return
    sm = 0
    dic = dict()
    for i in range(K, 0, -1):
        n = modpow(int(K / i), N)
        n2 = n
        j = 2
        while i * j <= K:
            n2 -= dic.get(i * j)
            n2 %= MOD
            j += 1
        dic[i] = n2
        sm += i * n2
        sm %= MOD

    print(sm)


def modpow(a, n):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % MOD
        a = a * a % MOD
        n = n >> 1
    return res


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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())
P = 10 ** 9 + 7
X = [0] * (K + 1)
ans = 0
for i in range(1, K + 1):
    X[i] += i
    for j in range(i * 2, K+1, i):
        X[j] -= X[i]
    ans += X[i] * pow(K//i, N, P)
print(ans % P)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class ModInt:
    def __init__(self, value, mod=10**9 + 7):
        self.mod = mod
        self.value = value % mod

    def __add__(self, other):
        return ModInt(self.value + int(other) % self.mod, self.mod)

    def __sub__(self, other):
        return ModInt(self.value - int(other) % self.mod, self.mod)

    def __mul__(self, other):
        return ModInt(self.value * int(other) % self.mod, self.mod)

    def __pow__(self, power):
        return ModInt(pow(self.value, int(power), self.mod), self.mod)

    def __int__(self):
        return self.value

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

def main():
    n, k = map(int, input().split())
    g = [0] * k
    a = ModInt(0)
    for i in range(k, 0, -1):
        c = ModInt(k // i)**n
        for j in range(i * 2, k + 1, i):
            c -= g[j - 1]
        g[i - 1] = c
        a += c * i
    print(a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache


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

@lru_cache
def gcd1_tuples(k):
    if k == 1:
        return 1
    tmp = pow(k, N, mod)
    for j in range(2, k+1):
        tmp -= gcd1_tuples(k//j)
        tmp %= mod
    return tmp

s = 0
for i in range(1, K+1):
    s += gcd1_tuples(K//i) * i
    s %= mod

print(s)

Submission status: Accepted

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

ans = 0
count=[0]*k
mod = 10**9+7
for i in range(0,k):
  kk=k-i#考える最大公約数
  maxi=k//kk#k以下のkkの倍数の個数
  count1=pow(maxi,n,mod)
  count2=0
  for j in range(2,maxi+1):
    count2 = count2 + count[j*kk-1]
  count[kk-1]=(count1 - count2)%mod

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

print(ans)

Submission status: Accepted

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

count_list = [0 for _ in range(k)]
for num in reversed(range(1,k+1)):
    # count = (k//num)**n
    count = pow(k//num,n,1000000007)
    count_list[num-1] = count

for num in reversed(range(1,k+1)):
    if k//num >= 2:
        for i in range(2,k//num+1):
            count_list[num-1] -= count_list[num*i-1]

score = 0
for idx,val in enumerate(count_list):
    score += (idx+1)*val

print(score%1000000007)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from math import gcd

def main():
     n, k = map(int, input().split())
     N = pow(10, 9) + 7
     gcd_num = [0 for i in range(k+1)]
     ans = 0

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

     print(ans%N)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort(reverse=True)
    return array


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

counts = [0] * (k+1)
counts[1] = pow(k, n, mod)

for t in range(k, 1, -1):
    multiple_t = k // t
    pattern = pow(multiple_t, n, mod)
    counts[t] += pattern
    divs = divisors(t)
    for div in divs:
        if div == t:
            continue
        counts[div] -= counts[t]
        counts[div] %= mod

ans = 0
for value, count in enumerate(counts):
    ans += value * count % mod
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
N, K = map(int, readline().split())
MOD = 10**9+7
table = [0]*(K+1)

for g in range(K, 0, -1):
    res = pow(K//g, N, MOD)
    for j in range(2*g, K+1, g):
        res = (res - table[j])%MOD
    table[g] = res
ans = 0
for g in range(1, K+1):
    ans = (ans + g*table[g])%MOD
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
MOD=10**9+7
ans=0
X=[0]*K
for k in range(1,K+1):
  k=K+1-k
  x=K//k
  if x>1:
    _=pow(x,N,MOD)
    for i in range(x-1):
      _-=X[k*(i+2)-1]
    X[k-1]=_
    ans+=k*_
  else:
    X[k-1]=pow(x,N,MOD)
    ans+=k*X[k-1]
print(ans%MOD)

Submission status: Accepted

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

mod = 10**9+7

all_num = pow(k,n,mod)
#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
    
    if tmp == 1:
        ans += all_num
        ans %= mod
        break
    
    #print(tmp,k)
    for i in range(k//tmp-1):
        #print(i)
        heru += dp[tmp*kakeru]
        kazu += 1
        kakeru += 1
    """
    while tmp * kakeru <= k:
        heru += dp[tmp*kakeru]
        kazu += 1
        kakeru += 1
        #print(tmp*kakeru,k)
    """ 
    
    kazu = pow(kazu,n,mod)-heru
    #kazu = kazu**n-heru
    ans += tmp*(kazu)
    all_num -= (kazu)
    #print(tmp,kazu,n,heru)
    dp[tmp] = kazu
    ans %= mod
    #print(ans,tmp,kazu)
    
print(ans)

Submission status: Accepted

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

MOD = 10 ** 9 + 7
cnt = [0] * (K + 1)
ans = 0
for x in reversed(range(1, K + 1)):
    cnt[x] += pow(K // x, N, MOD)
    for n in range(2, K + 1):
        if x * n > K:
            break
        cnt[x] -= cnt[x * n]
    cnt[x] %= MOD
    ans += x * cnt[x] % MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N,K = LMIIS()
    #1がひとつでもある：gcd(A) ==1
    #1を含む数列のパターン数：K**N - (K-1)**N

    #最低が2,全部偶数：gcd(A) == 2
    #そのような数列のパターン数p2：(K//2)**N - (K//2-1)**N

    #最低が3,全部3の倍数：gcd(A) == 3
    #p3:(K//3)**N - (K//3-1)**N



    #1<=d<=K
    #gcd(A)==dとなるようなパターン数：(K//D)**N-(K//D*2)**N-...
    ans = 0
    P = {}
    for i in range(K,0,-1):
        t = 2
        p = pow((K//i),N,MOD)
        while i*t<=K:
            p -= P[t*i]
            t += 1
        P[i] = p
        ans += p*i
        ans %= MOD
    print(ans)





    # ans = 0
    # notgcd1 = 0 
    # for i in range(1,K+1):
    #     p = pow((K//i),N,MOD) - pow((K//i-1),N,MOD)
    #     notgcd1 += pow((K//i),N,MOD) - p
    #     notgcd1 %= MOD
    #     ans += p*i
    #     ans %= MOD
    # ans += pow(K,N,MOD)-notgcd1
    # ans %= MOD
    # print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, K = map(int, rl().split())
    MOD = 10 ** 9 + 7
    
    a = [0]
    for d in range(1, K + 1):
        a.append(pow(K // d, N, MOD))
    
    for i in range(K, 0, -1):
        j = 2 * i
        while j <= K:
            a[i] = (a[i] - a[j]) % MOD
            j += i
    
    ans = 0
    for i in range(1, K + 1):
        ans = (ans + i * a[i]) % MOD
    print(ans)


if __name__ == '__main__':
    solve()

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

def main():
    n, k = map(int, input().split())
    count = [0]*(k+1)
    inf = pow(10, 9)+7
    for i in range(k, 0, -1):
        key = make_divisors(i)
        t = pow(k//i, n, inf)
        count[i] += t
        for value in key:
            if value == i:
                continue
            count[value] -= count[i]
    ans = 0
    for i in range(1, k+1):
        ans += ((count[i]%inf)*i)%inf
        ans %= inf
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

cnt = [0] * (k + 1)

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

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

print(ans)

Submission status: Accepted

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

cnt = [0] * (k + 1)

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

    cnt[i] = c

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

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
ans = 0
cnt_seq = [0]*(K+1) # cnt_seq[i] 最大公約数がiであるような数列の個数
MOD = 10**9 + 7
ans = 0
for i in range(K,0,-1):
    cnt_seq[i] = pow(K//i,N,MOD)
    for j in range(2*i,K+1,i):
        cnt_seq[i] -= cnt_seq[j]%MOD
    ans += i*cnt_seq[i]%MOD
print(ans%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def rep_sqr(base, k):
    ans = 1
    while k > 0:
        if k & 1:
            ans = ans * base % MOD
        base = base * base % MOD
        k >>= 1
    return ans

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

ans = 0
# 全てのgcdについて
gcd = [0 for i in range(k+1)]
for i in reversed(range(1, k+1)):
    d = k // i
    # i, 2i, 3i, ...を含めてd個
    gcd[i] = rep_sqr(d, n)
    # 倍数を上から削除
    j = i * d
    while j > i:
        gcd[i] -= gcd[j]
        j -= i
    ans += gcd[i] * i
    ans %= MOD

print(ans)

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): #gcdがiの時を考える
    l[i] = pow(k//i,n,mod) #gcdがiである数列の個数
    for j in range(i*2,k+1,i): 
        l[i] -= l[j] #重複で数えている所を取り除く
    ans += i * l[i] 
print(ans%mod)

Submission status: Accepted

Solution code:
import sys,math,copy,queue,itertools,bisect
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
MOD = 10**9 + 7

N,K = LI()
ans = 0
for i in range(1,K+1):
    yaku = []
    for j in range(1,int(math.sqrt(i))+1):
        if i % j == 0:
            yaku.append(j)
            k = i // j
            if k != j:
                yaku.append(k)
    yaku.sort(reverse=True)
    num = []
    for y in yaku:
        ny = pow(K // y,N-1,MOD)
        for z in range(len(num)):
            if yaku[z] % y == 0:
                ny -= num[z]
        num.append(ny)
    for x,y in zip(num,yaku):
        ans = (ans + x * y) % MOD

print (ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def modpow(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

def div(N):
  divv = []
  for i in range(1,int(N ** 0.5) + 1):
    if N % i == 0:
      divv.append(i)
      if i != N // i:
        divv.append(N // i)
  return(divv)
  
N,K = map(int,input().rstrip().split())
O = []
p = [0 for i in range(K + 1)]
ans = 0
for i in range(K,0,-1):
  p[i] = modpow(int(K / i),N,1000000007)
for i in range(K,0,-1):
  ans = (ans + (p[i] * i)) % 1000000007
  O = div(i)
  for o in O:
    if o != i:
      p[o] -= p[i]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
mod = 10**9+7
ans = 0
X_gcd = [0]*(K+1)
for X in reversed(range(1,K+1)):
    X_gcd[X] = pow(K//X,N,mod)
    
    for nX in range(2*X,K+1,X):
        X_gcd[X] -= X_gcd[nX]
        
    ans = (ans+(X%mod)*(X_gcd[X]%mod))%mod
print(ans%mod)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
dp=[0]*(k+1)
mod=int(1e9+7)
for i in range(k,0,-1):
    sm=0
    for j in range(2*i,k+1,i):
        sm=(sm+dp[j])%mod
    dp[i]=(pow(k//i,n,mod)-sm)%mod

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
p = 10**9+7
S = 0
memo = []
for i in reversed(range(1, K+1)):
  rep = K//i
  num = pow(rep, N, p)
  sub = 0
  if rep > 1:
    for j in range(rep - 1):
      sub += memo[- i - j * i][1]
  num -= sub
  S += i * num
  S = S%p
  memo += [(i, num)]
print(S)

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

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

print(ans%MOD)

Submission status: Accepted

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 = pow(k//i,n,mod)
  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)
# print(data)

Submission status: Accepted

Solution code:
# E
N,K=map(int,input().split())
MOD=10**9+7
# e.g.
# N=3,K=4
#   gcd(A)=4 -> (4,4,4)=1**3=1
#   gcd(A)=3 -> (3,3,3)=1**3=1
#   gcd(A)=2 -> (2or4,2or4,2or4)-(4,4,4)=2**3-1**3=7
#   gcd(A)=1 -> (1~4,1~4,1~4)-上全部=4**3-(2**3-1**3)-1**3-1**3=55
# and=1*4+1*3+7*2+55*1=76
#
# gcd(A)=xとなるAをx=K,K-1,...,1として数えていく。
# A=(x or 2x or 3x or ...,x or 2x or 3x or ...,...)という形をしているが
# 2x,3x,...がK以下ならxより大きい場合で既にカウントしてしまっている
# (gcd(2x,2x)=2xをgcd(2x,2x)=xとして数えてしまっている)
# ->2x,3xについてカウント済みならそれを引けばいい: Kから数えればいい

ans=0 # 出力する答え
GCD=[0 for _ in range(K+1)] # GCD[i]:gcd(A)=iとなるAの総数
for x in range(K,0,-1): # gcd(A)=xとなるAを各xで数える
    Ai_cnt=K//x # 各Aiについてとりうる値の総数(x,2x,3x,...<=K)
    rep=0 # 既にカウント済みなものをここに数えてまとめておく

    # 既にカウント済みがあるか数える
    check=2*x
    while check<=K: #これを満たすならK以下である
        rep+=GCD[check] # 満たしたのでrepに足す
        check+=x # 次のxの倍数について調べるために足す

    # repができたのでGCD[i]に記録
    GCD[x]=pow(Ai_cnt,N,MOD)-rep #繰り返し2乗法: O(logN)
    # kについては完成したので,ansに足す
    ans+=x*(GCD[x])
    ans%=MOD
# 出力する前に計算量の確認
# 計算量はおよそ各xでK//x回の計算とpowが必要なので
#   sum(log(N)+K//x x:1toK)
# <=K*(log_2(N)+sum(1/x 1toK))
# ~ K*(log_2(N)+log_e(K))
# < (10**5)*(2*log_2(10**5))
# < 4*10**6
# よってギリ間に合うと思われる
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
H=[0]*(K+1)
m=pow(10,9)+7

ans=0
i=K
while i>=1:
    H[i]=pow(K//i,N,m)
    j=2
    while j*i<=K:
        H[i]-=H[j*i]
        j+=1
    ans+=H[i]*i
    i-=1


print(ans%m)

Submission status: Accepted

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

def phi_table(N):
    phi = list(range(N + 1))
    for p in range(2, N + 1):
        if phi[p] == p:
            for n in range(N // p, 0, -1):
                phi[p * n] -= phi[n]
    return phi


L = int(N ** .66)
H = int(N // (L + 1))
phi = phi_table(L)

# f(n) = \sum_{i=1}^n phi(i)

f_l = phi.copy()
for n in range(L):
    f_l[n + 1] += f_l[n]

f_h = [0] * (H + 1)  # f(N//d)


def f(n):
    return f_l[n] if n <= L else f_h[N // n]


def compute_f(n):
    sq = int(n ** .5)
    x = n * (n + 1) // 2
    for d in range(1, n + 1):
        m = n // d
        if m <= sq:
            break
        x -= f(m)
    for m in range(1, sq + 1):
        cnt = n // m - n // (m + 1)
        x -= f_l[m] * cnt
    return x


for d in range(H, 0, -1):
    f_h[d] = compute_f(N // d)

sq = int(N ** .5)
answer = 0
for d in range(1, N + 1):
    n = N // d
    if n <= sq:
        break
    answer += pow(n, e, MOD) * phi[d]

for n in range(1, sq + 1):
    low_d = N // (n + 1)
    high_d = N // n
    phi_sum = f(high_d) - f(low_d)
    answer += phi_sum * pow(n, e, MOD)

answer %= MOD
print(answer)

Submission status: Accepted

Solution code:

MOD = 10**9 + 7

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

c = 0

d = [0] * (k + 1)

for i in range(k, 0, -1):

        # temp_c = 0
    if d[i] == 0:

        
        t1 = k // i    
        c1 = pow(t1, n, MOD)

        j = i
        while j + i <= k:
            j += i
            c1 -= d[j]
            if c1 < 0:
                c1 += MOD

        d[i] = c1

        # print (i, d[i])

        c += i * c1
        c %= MOD

print (c)

Submission status: Accepted

Solution code:
import math
import fractions
import collections
import itertools
#gcd(A)=XなるAがいくつあるかを、1<=X<=Kで探査できれば問題ない
#gcdを決めうつ
#gcd(A)=aXなる条件はAの各要素がXの倍数であることであるためその個数はceil(K//X)^Nとなる
#そのうちgcd(A)=Xとなるものは#C(gcd(A)=aX)-#C(gcd(A)=2X)-...-#C(gcd(A)=nX)である
#よって上から順にgcd(A)=Xなるものを探すことができそう
N,K=map(int,input().split())
gcdnum=[0]*(K+1)
num=0
ans=0
p=10**9+7
for i in range(K,0,-1):
    num=pow(K//i,N,p)
    #print(K//i,i)
    for j in range(2,(K//i)+1):
        num=(num-gcdnum[j*i])%p
    gcdnum[i]=num
#print(gcdnum)
for i in range(K+1):
    ans=(ans+(gcdnum[i]*i)%p)%p
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,N = map(int,(input().split()))
MOD = 10**9+7
core = [0]*(N+1)
tr = [0]*(N+1)

for i in range(1,N+1):
    core[i] = N//i

for i in range(1,N+1)[::-1]:
    if core[i] == 1:
        tr[i] = 1
    else:
        tr[i] = pow(core[i],K,MOD)
        now = i
        r = 2
        while now*r <= N:
            tr[i] -= tr[now*r]
            r += 1

ans = 0
for i in range(1,N+1):
    ans += i * tr[i]
    ans %= MOD

print(ans)

Submission status: Accepted

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

MOD = 10**9 + 7

class mint:
    def __init__(self, i):
        self.i = i

    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)

    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)

    def __mul__(self, m):
        return mint(self.i * m.i % MOD)

    def __sub__(self, m):
        t = self.i - m.i
        if t < 0:
            t += MOD
        return mint(t)

    def __pow__(self, m):
        i = self.i
        res = 1
        while(m > 0):
            if m & 1:
                res = res * i % MOD 
            i = i * i % MOD
            m >>= 1
        return mint(res)

    def __truediv__(self, m):
        return mint(self.i * m ** (MOD - 2) % MOD)

    def __repr__(self):
        return repr(self.i)

l = [mint(0) for _ in range(k + 1)]

for x in range(k, 0, -1):
    count = mint(k // x) ** n
    for tx in range(x + x, k + 1, x):
        count -= l[tx]
    l[x] = count

ans = sum(mint(i) * x for i, x in enumerate(l))
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
MOD = 1000000007
ans = 0
dp = [0] * (K + 1)
for i in range(K, 0, -1):
    div = K // i
    amount = (pow(div, N, MOD)) % MOD
    for j in range(2, div + 1, 1):
        amount = (amount - dp[j * i] + MOD) % MOD
    dp[i] = amount
    ans = (ans + amount * i) % MOD
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

MOD = 10 ** 9 + 7

def main():
    N, K = [int(x) for x in input().split()]

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

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

    print(ans2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
mod = int(1e9) + 7
X = [0 for _ in range(K)]
def doubling(n, m):
  y = 1
  base = n
  while m != 0:
    if m % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    m //= 2
  return y
SS = 0
for i in range(K, 0, -1):
  d = K // i
  S = doubling(d, N)
  if d > 1:
    for j in range(2, d+1):
      S -= X[j*i-1]
      S %= mod
  X[i-1] = S
  SS += i * S
  SS %= mod
print(SS)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

def main():
    N,K = map(int, readline().split())

    gcd_cnt = [0] * (K+1)

    for i in range(K,1,-1):
        gcd_cnt[i] = pow(K // i, N, MOD)
        x = 2
        while i * x <= K:
            gcd_cnt[i] -= gcd_cnt[i*x]
            gcd_cnt[i] %= MOD
            x += 1

    #print(gcd_cnt)

    ans = pow(K,N,MOD)
    for i in range(2,K+1):
        ans += ((gcd_cnt[i] % MOD) * (i-1)) % MOD
        ans %= MOD
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
mod = 1000000007

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

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