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:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))


n,k = inpl()
res = 0
cnt = [0] * (k+5)
for i in reversed(range(1,k+1)):
    tmp = pow(k//i,n,mod)
    cnt[i] = tmp
    now = i
    while True:
        now += i
        if now > k:
            break
        cnt[i] -= cnt[now]
    res += cnt[i] * i
    res %= mod
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from functools import reduce

mod = 10 ** 9 + 7
def madd(x, y):
    ret = x + y
    return ret if ret < mod else ret - mod
def msub(x, y):
    ret = mod + x - y
    return ret if ret < mod else ret - mod
def mmul(x, y):
    return (x * y) % mod
def mpow(x, n):
    ret = 1
    while n > 0:
        if n & 1 > 0:
            ret *= x
            ret %= mod
        x = (x * x) % mod
        n >>= 1
    return ret

def msum(a):
    return reduce(madd, a, 0)

n, k = map(int, input().split())
INF = - (2**60)
dp = [-INF] * (k + 1)

for g in range(k, 0, -1):
    dp[g] = msub(mpow(k // g, n), msum(dp[2 * g::g]))

print(msum([mmul(g, dp[g]) for g in range(1, k + 1)]))

Submission status: Accepted

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

m = 10**9+7

def f(n, k):
  res = 0
  lst = [0]*(k+1)
  for i in range(k, 0, -1):
    lst[i] = pow((k//i), n, m) - sum(lst[i*j] for j in range(2, k//i+1))%m
    res += i*lst[i]
    res %= m
  return res

print(f(n, k))

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
mod = 10**9 +7
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:
# YouTube解説
MOD = 1000000007
n, k = [int(x) for x in 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(i * 2, k + 1, i):  # iの倍数
        # d[6] = d'[6] - d[12] - d[18] ...
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
# YouTube解説
MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [pow(k // i, n, MOD) if i > 0 else 0 for i in range(0, k + 1)]

for i in range(k, 0, -1):  # 大きいほうから
    for j in range(i * 2, k + 1, i):  # iの倍数
        # d[6] = d'[6] - d[12] - d[18] ...
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)

Submission status: Accepted

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

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

print(sum([i*f for i,f in enumerate(G)]) % mod)

Submission status: Accepted

Solution code:
# YouTube解説
MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [pow(k // i, n, MOD) for i in range(1, k + 1)]
d.insert(0, 0)

for i in range(k, 0, -1):  # 大きいほうから
    for j in range(i * 2, k + 1, i):  # iの倍数
        # d[6] = d'[6] - d[12] - d[18] ...
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)

Submission status: Accepted

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

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

for i in range(k, 0, -1):
    kin = 1  ## kosuに入れる数
    nn = k//i    ## iの倍数が何個あるかを計算する
    ii = n
    kini = nn
    while ii > 0:
        if ii%2 == 1:
            kin = (kin*kini)%mod
        kini = (kini**2)%mod
        ii //= 2
    for j in range(2,nn+1):
        kin = (kin-kosu[j*i])%mod
    kosu[i] = kin

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

print(ans)

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,k=map(int,input().split())
mod=10**9+7
A=[0]*(k+1)
for i in range(1,k+1)[::-1]:
  cur=pow(k//i,n,mod)
  for j in range(2,k+1):
    if i*j>k:
      break
    else:
      cur-=A[i*j]
  A[i]=cur
ans=0
for i in range(1,k+1):
  ans=(ans+i*A[i])%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:
N,K=map(int,input().split())

# 最大公約数が1〜Kになるそれぞれの個数を求める
# 大きい方から順に計算して、自分の倍数になるものは除外する

res = [0] * (K+1)
DIV = 10 ** 9 + 7
for x in range(K,0,-1):
  # 最大公約数がxになるものは
  # K//x個ある
  # (K//x)**Nが、個数
  res[x] = pow(K//x,N,DIV)
  for i in range(x*2,K+1,x):
    res[x] -= res[i]
    
ans = 0
for i in range(len(res)):
  ans += res[i] * i
  ans %= DIV
  
print(ans)

Submission status: Accepted

Solution code:
N,K = [int(x) for x in input().split()]
count = [0]*(K+1)
ans = 0
mod = 1000000007
for i in range(K,0,-1):
    kosuu = pow(K//i,N,mod)
    if K // i >= 2:
        for j in range(K//i,1,-1):
            kosuu -= count[j*i]
    ans += i*kosuu
    count[i] = kosuu
print(ans%mod)

Submission status: Accepted

Solution code:
# 最大公約数ごとの数を列挙
N,K=map(int,input().split())
li=[0]*(K+1)
out=0
mod=10**9+7

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

print(out%mod)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
MOD=int(1e9)+7

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

  k=2*j
  while k<=K:
    dp[j]=(dp[j]-dp[k]+MOD) % MOD
    k+=j

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())  # N個の数列, K以下の数字で構成される
gcd_sum = [0]*(K+1)
MOD = 10**9+7
# 最大公約数がKになる通りが何パターンあるかを求める
for i in reversed(range(1, K+1)):
    # パターン数にMODを取っても問題ない（結局掛け算しかしないので）
    gcd_sum[i] = pow(K//i, N, MOD)
    cur = 2*i
    while cur <= K:
        gcd_sum[i] -= gcd_sum[cur]
        cur += i
ans = 0
for i in range(1, K+1):
    ans += gcd_sum[i]*i
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def main():
    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 reversed(range(1, k+1)):
        for j in range(2*i, k+1, i):
            a[i] -= a[j]
            a[i] %= MOD
    ans = 0
    for i in range(1, k+1):
        ans += a[i]*i
        ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

print(int(ans%m))

Submission status: Accepted

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

# E - Sum of gcd of Tuples (Hard)

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

modulus = 10 ** 9 + 7

def expt(x, k):
    """(x ** k) % modulus"""
    p = 1
    for b in (bin(k))[2:]:
        p = p * p % modulus
        if b == '1':
            p = p * x % modulus
    return p

# iの倍数をn個並べた列の個数
nseq = [expt((k // i), n) if i > 0 else None for i in range(k + 1)]

for i in range(k, 0, -1):
    # iの2倍以上の倍数からなる列の個数を引く
    s = sum(nseq[m] for m in range(2 * i, k + 1, i))
    nseq[i] = (nseq[i] - s % modulus + modulus) % modulus

# nseq[i]はgcd==iになる列の個数
ans = sum(i * nseq[i] % modulus for i in range(1, k + 1))
print(ans % modulus)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

def bekizyo(x, n): #べき乗x**n(nが大きいとき)
    n2 = format(n, "b")
    l_n2 = len(n2)
    ass = 1
    y = x
    for i in range(l_n2):
        if n2[l_n2 - 1 - i] == "1":
            ass *= y
            ass %= mod
        y **= 2
        y %= mod
    return ass


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

l = [0] * (k+1)

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
ans = 0
mod = 10 ** 9 + 7
count = [0] * (K+10)
for i in range(K,0,-1):
    t = pow(K//i, N, mod)
    j = 2
    while j * i <= K:
        t -= count[j*i]
        j += 1
    count[i] = t
    # tがiの倍数からなる数列の個数であることが確定しているはず
    ans += t * i
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

mod = 10 ** 9 + 7
def madd(x, y):
    ret = x + y
    return ret if ret < mod else ret - mod
def msub(x, y):
    ret = mod + x - y
    return ret if ret < mod else ret - mod
def mmul(x, y):
    return (x * y) % mod
def mpow(x, n):
    ret = 1
    while n > 0:
        if n & 1 > 0:
            ret *= x
            ret %= mod
        x = (x * x) % mod
        n >>= 1
    return ret

def msum(a):
    return reduce(madd, a, 0)

n, k = map(int, input().split())
INF = - (2**60)
dp = [-INF] * (k + 1)

for g in range(k, 0, -1):
    dp[g] = msub(mpow(k // g, n), msum(dp[2 * g::g]))

print(msum([mmul(g, dp[g]) for g in range(1, k + 1)]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, K):
    ans = 0
    M = Mod(10**9+7)

    c = {}
    for k in range(K, 0, -1):
        n = M.pow(K//k, N)
        for j in range(2, K//k+1):
            n = M.sub(n, c[j*k])
        ans = M.add(ans, M.mul(n, k))
        c[k] = n

    return ans


def main():
    N, K = read_int_n()
    print(slv(N, K))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math
import sys
import itertools
sys.setrecursionlimit(10**7)

MOD = 1000000007  # type: int

class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]  # 階乗を求めるためのキャッシュ
        self.invModulos = [0, 1]  # n^-1のキャッシュ
        self.invFactorial_ = [1, 1]  # (n^-1)!のキャッシュ

    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  # To make sure already calculated n^-1
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]


class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def choose_k_from_n(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def pow(a,n,m):
    if n == 1:
        return a
    elif n == 0 or a == 1:
        return 1
    else:
        if n%2 == 0:
            r = pow(a,n//2,m)
            return r*r%m
        else:
            r = pow(a,n-1,m)
            return a*r%m

def solve(N: int, K: int):
    powDict = {}
    def powd(a):
        if a in powDict:
            return powDict[a]
        else:
            powDict[a] = pow(a,N,MOD)
            return powDict[a]
    cDict = {}
    sum = 0
    for p in range(K,0,-1):
        c = powd(K//p)
        for i in range(2*p,K+1,p):
            c = (c-cDict[i])%MOD
        cDict[p]=c
        sum = (sum + c*p)%MOD
    print(sum)


# 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:
Big=10**9+7
_=list(map(int,input().split(" ")))
N=_[0]
K=_[1]
gcd_list=[0 for _ in range(K)]
for i in range(K):
  s=K-i-1
  gcd_list[s]=(pow(K//(K-i), N, Big)-(sum(gcd_list[2*s+1::s+1]))%Big)%Big
answer=[(x+1)*gcd_list[x]%Big for x in range(K)]
print(sum(answer)%Big)

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, K = lr()
    MOD = pow(10, 9)+7
    lst = [0]*K
    klst = [0]*K
    for k in range(K, 0, -1):
        lst[k-1] = pow(K//k, N, MOD)
        for i in range(2, K//k+1):
            lst[k-1] -= lst[i*k-1]
        klst[k-1] = k*lst[k-1]
    print(sum(klst)%MOD)
resolve()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n, k = na()

def modpow(n, p, m):
    if p == 0:
        return 1
    if p % 2 == 0:
        t = modpow(n, p // 2, m)
        return t * t % m
    return n * modpow(n, p - 1, m) % m

d = [0] * (k + 1)

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

print(ans % mod)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
mod = 10**9 + 7
s = [0 for i in range(k+1)]
ret = 0

for i in range(k, 0, -1):
    p = int(k/i)
    c = pow(p, n, mod)
    for j in range(2, k+1):
        if i*j <= k:
            c -= s[i*j]
        else:
            break
    
    s[i] = c%mod

    ret = (ret + (c%mod)*i)%mod

print(ret)

Submission status: Accepted

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

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

# update d
for i in range(k,0,-1):
    for j in range(i*2,k+1,i):
        d[i]-=d[j]
        d[i]%=MOD
ans=0
for i in range(1,k+1):
    ans+=d[i]*i%MOD
    ans%=MOD
print(ans)

Submission status: Accepted

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

mod = 10**9 + 7
array = []

for k in range(1, K+1):
    array.append(pow((K // k), N, mod))
    
for k in range(K, 0, -1):
    for i in range(2*k, K+1, k):
        array[k-1] -= array[i-1]

sum = 0
for k in range(1, K+1):
    array[k-1] *= k
    array[k-1] %= mod
    sum += array[k-1]
    
sum %= mod

print(sum)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

n, k = map(int, input().split())
otv = 0
D = [0] * (k + 1)
for i in range(1, k + 1):
    D[i] = pow(k // i, n, mod)

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

for i in range(1, k + 1):
    otv = (otv + D[i] * i) % mod

print(otv)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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[i] - D[j]) % mod

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

    print(res)


if __name__ == '__main__':
    resolve()

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:
N,K = map(int, input().split())

MOD = 10 ** 9 + 7

# just[X]: gcdがぴったり X になる個数
just = [0] * (K + 1)

for X in range(K, 0, -1):
    just[X] = pow(K // X, N, MOD)
    
    mul = X + X
    while mul <= K:
        just[X] -= just[mul]
        mul += X

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

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
mod=10**9+7
bk = [pow((k//l),n,mod) for l in range(1,k+1)]

BK=[0]*(k+1)
for i in range(k,0,-1):
    hiku=0
    for j in range(k//i+1):
        if j*i>k:
            break
        hiku+=BK[i*j]
    BK[i] = bk[i-1]-hiku

ans=0
for i,bb in enumerate(BK):
#     print(i,bb)
    ans=ans+i*bb %mod
print(ans%mod)

Submission status: Accepted

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

MOD = 1000000007  # type: int

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

def solve(N: int, K: int):
    ans = 0

    x = [1] * (K+1)

    for i in range(K, 0, -1):
        if i * 2 <= K:
            x[i] = modpow(K//i, N)
            j = 2
            while i * j <= K:
                x[i] -= x[i*j]
                j += 1
            ans += x[i] * i % MOD
        else:
            ans += i
    print(ans%MOD)


    return


# 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())
mod = 10**9+7
ans = [0]*(K+1)
result = 0

for i in range(K,0,-1):
    c = K//i
    ans[i] += pow(c,N,mod)
    for j in range(i,K+1,i):
        if i != j:
            ans[i] -= ans[j]
    result += i*ans[i] % mod

print(result%mod)

Submission status: Accepted

Solution code:
import sys, math
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

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

    """
    gcd(a1,...,aN) = dになる時を考える。もしこの個数がわかれば\sum_dして答えを得る。
    （決め打ち二分探索的な発想として出てくるのか？？？）
    これはa1,...,aNがすべてdの倍数のときと予想が立つが、すぐにgcd=2d, 3d,...の場合もありうると気づく。
    しかしこの考察から
            gcd(a1,...,aN)がdの倍数になる(a1,...,aN)の個数 = (K // d)^N
    という式を得る。

    同様にgcd(a1,...,aN)=(2dの倍数), gcd(a1,...,aN)=(3dの倍数)なる(a1,...aN)の個数もすぐ求まるので、
    kd <= Nなるなるべく大きなkを考えて（そうするとgcd(a1,...,aN)=mdなる(a1,...aN)の個数がばっちり求まる）、
    あとはkを小さくしていきながら適当な引き算を施すことで答えが求まる。
    """

    count = [0] * (K + 1) # count[i] = (gcd(a1,...,aN) = iとなる(a1,...,aN)の組の数)
    for d in range(1, K + 1):
        count[d] = pow(K // d, N, mod)
    for d in range(K // 2 + 1, 0, -1):
        for m in range(2, K // d + 1):
            count[d] -= count[m * d]
            count[d] %= mod
    #print(count)
    ans = 0
    for i in range(1, K + 1):
        ans += count[i] * i
        ans %= mod
    print(ans)

if __name__ == "__main__":
    main()

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)
    return divisors

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

lst = [0 for i in range(k+1)]
for i in range(1, k+1)[::-1]:
    num = pow(k//i, n, mod)
    lst[i] += num
    divisors = make_divisors(i)
    for j in divisors:
        if j != i: lst[j] -= lst[i]

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

Submission status: Accepted

Solution code:
MOD = int(1e9+7)


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
N, K = list(map(int, input().split()))
mod = 10 ** 9 + 7
sum = 0
count = [0 for _ in range(K+1)]
pows = [0 for _ in range(K+1)]

def cal_pow(k, pows):
    if pows[k] == 0:
        pows[k] = pow(k,N, mod)
        return pows[k]
    else:
        return pows[k]

for h in range(K):
    k = K-h
    sub, alpha = 0,2
    while True:
        if alpha*k <= K:
            sub += count[alpha*k]
            alpha += 1
        else:break
    count[k] = (cal_pow(K//k, pows) - sub) % mod

for k, c in enumerate(count):
    sum += k * c % mod
print(sum % mod)

Submission status: Accepted

Solution code:
MOD = int(1e9+7)
N, K = map(int, input().split())

count = [0] * (K+1)
ans = 0
for now in range(K, 0, -1):
    count[now] = pow(K // now, N, MOD)
    for j in range(2*now ,K+1, now):
        count[now] -= count[j]
        if count[now] < 0:
            count[now] += MOD
    ans += now * count[now]
print(ans % MOD)

Submission status: Accepted

Solution code:
MOD = 1000000007
def fast_power(base, power):
    """
    Returns the result of a^b i.e. a**b
    We assume that a >= 1 and b >= 0

    Remember two things!
     - Divide power by 2 and multiply base to itself (if the power is even)
     - Decrement power by 1 to make it even and then follow the first step
    """

    result = 1
    while power > 0:
        # If power is odd
        if power % 2 == 1:
            result = (result * base) % MOD

        # Divide the power by 2
        power = power // 2
        # Multiply base to itself
        base = (base * base) % MOD

    return result
n,k = [int(j) for j in input().split()]
d = dict()
ans = k
d[k] = 1
sum_so_far = 1
for i in range(k-1, 0, -1):
	d[i] = fast_power(k//(i),n)
	for mul in range(i*2, k+1, i):
		d[i]-=d[mul]
	# d[i] = max(1, d[i])
	ans+=(i*d[i])%MOD
	# if d[i]>1:
		# sum_so_far += d[i]
print(ans%MOD)

Submission status: Accepted

Solution code:
n,k = [int(x) for x in input().split()]
li = [0]*(k+1)
mod = 10**9+7

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

Submission status: Accepted

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

for i in range(K, 0, -1):
    n = pow((K//i), N, mod)
    for x in range(i, K+1, i):
        n -= gcd_l[K-x]
    gcd_l[K-i] = n%mod

res = 0
for i in range(K):
    res += (gcd_l[i] * (K-i))%mod

print(res%mod)

Submission status: Accepted

Solution code:
from functools import reduce

MOD = 10**9 + 7
N, K = map(int, input().split())
cnt = [0] * (K + 1)
ans = 0
for k in range(K, 0, -1):
    temp = cnt[2*k::k]
    cnt[k] = pow(K // k, N, MOD) - (reduce(lambda x, y: (x + y) % MOD, temp) if temp else 0)
    ans += (cnt[k] * k) % MOD; ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
gcd_list = [0] * K#K, K-1, K-2の順
MOD = 10 ** 9 + 7

for i in range(K, 0, -1):
  #print(i)
  ans2 = pow((K // i), N, MOD)#
  x = i
  while x <= K:
    ans2 -= gcd_list[K - x]
    x += i
  gcd_list[K - i] = ans2 % MOD
  
ans = 0  
for i in range(K):
  ans += (gcd_list[i] * (K - i)) % MOD
  
print(ans % MOD)

Submission status: Accepted

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

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

ret = 0
for i in range(k,0,-1):
	a = int(k/i)
	c = pow(a,n,mod)
	for j in range(2,k+1):
#		print("aaa",i,j,k)
		if i*j <= k:
			c -= s[i*j]
		else :
			break
	s[i] = c%mod
#	print(i,a,c%mod,(c*i)%mod)
	ret = (ret+(c%mod)*i)%mod
print(ret)

Submission status: Accepted

Solution code:
mod = 10**9+7

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

N, K = map(int, input().split())
li = [0] * (K+1)
for i in range(K, 0, -1): 
    li[i] = Pow((K//i), N)
    for j in range(2,K//i+1):
        li[i] = (li[i] - li[i*j])%mod
ans = 0
for i in range(1, K+1):
    ans = (ans + i*li[i])%mod
print(ans)

Submission status: Accepted

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

def pow(N,R,mod):
    ans = 1
    i = 0
    while((R>>i)>0):
        if (R>>i)&1:
            ans *= N
            ans %= mod
        N = (N*N)%mod
        i += 1
    return ans%mod


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

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

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


        ans += (i*mm)%mod
        ans %= mod

    print(ans)

if __name__ == '__main__':
    main()