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())
ans = 0
dev = [[] for _ in range(k+1)]
for i in range(1,k+1):
  l = int(i**.5)
  for j in range(1,l+1):
    if i % j == 0:
      dev[i].append(j)
      dev[i].append(i // j)
  if l**2 == i:
    dev[i].pop()
  #print(i,l,dev[i])
#print(dev)
cnt = [0 for _ in range(k+1)]
mod = 10 ** 9 + 7
for d in range(1,k+1):
  p = k // d
  double = [p]
  now = 1
  for i in range(20):
    double.append(double[-1]**2%mod)
  #print(d,p,double)
  m = int(n)
  i = 0
  while m:
    if m % 2 != 0:
      now *= double[i]
    m //= 2
    i += 1
  #print(p,n,now)
  cnt[d] = now
#print(cnt)
for i in range(1,k+1)[::-1]:
  for x in dev[i]:
    if x != i:
      cnt[x] -= cnt[i]
#print(cnt)
for i in range(k+1):
  ans += i * cnt[i]
  ans %= mod
#print(sum(cnt))
print(ans)

Submission status: Accepted

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

yakusu = [0]
ans = 0
for i in range(K):
    n = i + 1

    yaku = 0
    if n > 1:
        for j in range(1, int(n**0.5)+1):
            if n % j == 0:
                yaku += j - yakusu[j]
                if j != n//j and j != 1:
                    yaku += n//j - yakusu[n//j]
    yakusu.append(yaku)

    ans += pow((K//n), N, MOD) * (n - yaku)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

mod = 10**9 + 7

n, k = nm()
rl = [-1]*(k+1)
dp = [0]*(k+1)
ans = 0
for i in range(k, 0, -1):
    t = k//i
    if rl[t] < 0:
        rl[t] = pow(t, n, mod)
    r = rl[t]
    for j in range(2*i, k+1, i):
        r = (r - dp[j]) % mod
    dp[i] = r
    ans = (ans + r*i) % mod
print(ans)

Submission status: Accepted

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

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

P = 10 ** 9 + 7

def mod_prod(a,b):
    return a * b % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n // 2
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret


a = [0] * (K + 1)
a[-1] = 1

for i in range(K - 1, 0, -1):
    x = K // i
    x = mod_pow(x, N)
    for j in range(i * 2, K + 1, i):
        x -= a[j]
    a[i] = x % P

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

print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])


def f(dp,n,k):
    if dp[k] != -1:
        return dp[k]
    if k == 1:
        return 1
    cnt = 0
    cnt = pow(k,n,mod)
    for i in range(2,k+1):
        cnt += mod
        cnt -= f(dp,n,k//i) 
        cnt %= mod
    dp[k] = cnt       
    return cnt

def main():
    n,k = inpm()
    ans = 0
    dp = [-1 for _ in range(k+1)]
    for e in range(1,k+1):
        ans += e*f(dp,n,k//e)
        ans %= mod
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
# 大きい数用


def modPow(a, n, p):
    if n == 1:
        return a
    if n % 2 == 1:
        return (a * (modPow(a, n // 2, p) ** 2)) % p
    else:
        return (modPow(a, n // 2, p) ** 2) % p


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

ans_array = [0] * (N + 1)
mod = 10 ** 9 + 7

for i in range(N, 0, -1):
    c = N // i
    ans_array[i] = (ans_array[i] + modPow(c, K, mod)) % mod
    if i != 1:
        ans_array[1] = (ans_array[1] - ans_array[i] + mod) % mod
    for j in range(2, int(math.sqrt(i) + 1)):
        if i % j == 0:
            if i == j * j:
                ans_array[j] = (ans_array[j] - ans_array[i] + mod) % mod
                break
            else:
                ans_array[j] = (ans_array[j] - ans_array[i] + mod) % mod
                ans_array[i // j] = (ans_array[i // j] -
                                     ans_array[i] + mod) % mod

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

print(ans)

Submission status: Accepted

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

memo = {1:1}
def f(k):
    if k in memo:
        return memo[k]
    res = pow(k,N,MOD)
    for i in range(2,k+1):
        res -= f(k//i)
    res = res % MOD
    memo[k] = res
    return res

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

print(ans)

Submission status: Accepted

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

mod = 10**9+7
ans = 0
count = [0]*(k+1)

for i in range(1, k+1):
    m = i - count[i]
    ans += pow(k//i, n, mod) * m
    ans %= mod
    for j in range(i, k+1, i):
        count[j] += m

print(ans)

Submission status: Accepted

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

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

A = [0] + [k//i for i in range(1, k+1)]
B = list(set(A))
# print("A",A)
D = {}
for i in B:
    D[i] = pow(i, n, mod)

# print(D)

ans = [0] * (k+1)
for i in range(k, 0, -1):
    ans[i] = D[A[i]] % mod
    # print("ans",i,ans[i])
    ii = i * 2
    while ii <= k:
        # print("ii",ii,D[ii])
        ans[i] = (ans[i] - ans[ii]) % mod
        ii += i
# print(ans)
# print(sum(ans) % mod)

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
mod = 10 ** 9 + 7
table = [0] * (K + 1)
table[1] = K
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
for i in range(2, K + 1): table[i] = (K // i) % mod
res = 0
tt = [0] * (K + 1)
for i in range(K, 0, -1):
  t = pow(table[i], N, mod) + tt[i]
  divs = make_divisors(i)
  #print(divs, t)
  for d in divs:
    if d < i: tt[d] -= t
  res += t * i % mod
  res %= mod
  #print(res)
print(res)

Submission status: Accepted

Solution code:
mod = 10**9+7


def main():
    n, k = map(int, input().split())

    baisuu = [[] for _ in [0]*(k+1)]
    tree = [0]*(k+1)

    for i in range(1, k+1):
        j = 2*i
        while j <= k:
            baisuu[i] += [j]
            j += i
        tree[i] = pow(len(baisuu[i])+1, n, mod)
    for i in range(k, 0, -1):
        for j in baisuu[i]:
            tree[i] -= tree[j]
        tree[i] %= mod
    ans = 0
    for i, j in enumerate(tree):
        ans = (ans+i*j) % mod
    print(ans)


main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def cmb(n,r,mod):
  if r<0 or r>n:
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod

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

g1=[1,1]
g2=[1,1]
inverse=[0,1]
 
for i in range(2,n+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

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

Submission status: Accepted

Solution code:
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1	 : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r]
N, K = map(int, input().split())
B = [0] * (K+1)
r = 0
for i in range(K, 0, -1):
    ac = K//i
    c = power(ac, N)
    bsum = 0
    for j in range(ac-1):
        j += 2
        bsum += B[i*j]
    B[i] = (c - bsum)%mod
    r = (r+B[i]*i)%mod
print(r)

Submission status: Accepted

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

for i in range(K, 0, -1):
    a = pow(K//i, N, MOD)
    c = 2
    
    while True:
        if c*i>K:
            break
        
        a -= cnt[c*i]
        a %= MOD
        c += 1
    
    cnt[i] = a
    ans += i*a
    ans %= MOD
    s -= a
    s %= MOD

ans += s

print(ans%MOD)

Submission status: Accepted

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

a = [1] * (k+1)
b = [ i for i in range(k+1) ]
a[0] = 0
b[0] = 0

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

# print(a)
# print(b)

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    
    #とりあえず重複ありで，個数を数える
    cnt=[0]*(K+1)
    
    for i in range(1,K+1):
        aa=K//i
        cnt[i]=pow(aa,N,mod)
        
    for i in range(K,0,-1):
        pn=-1
        for j in range(2*i,K+1,i):
            #print(i,j,cnt)
            cnt[i]+=cnt[j]*pn
            
    #print(cnt)
    ans=0
    for i in range(1,K+1):
        ans+=(i*cnt[i])%mod
        ans%=mod
        
    print(ans)
    

main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import os
from functools import reduce

import itertools
import sys
from math import gcd

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = [1]
    r = 1
    for inv in mod_invs(max, mod)[1:]:
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


N, K = list(map(int, sys.stdin.buffer.readline().split()))


def test(N, K):
    s = 0
    counts = defaultdict(int)
    for nums in itertools.product(range(1, K + 1), repeat=N):
        s += reduce(gcd, nums)
        counts[reduce(gcd, nums)] += 1
    print(counts)
    print(s % MOD)


# test(N, K)


# comb = Combination(max=N + K, mod=MOD)


# @debug
def count_patterns(n):
    # gcd の約数が n となるように選ぶ方法の数
    return pow(K // n, N, MOD)


counts = [0] * (K + 1)
for n in range(1, K + 1):
    cnt = count_patterns(n)
    counts[n] = cnt
for n in reversed(range(1, K + 1)):
    i = n * 2
    while i <= K:
        counts[n] -= counts[i]
        i += n
# print(counts)

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

Submission status: Accepted

Solution code:
class modpow:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res

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

D = [0] * (K + 1)
ans = 0
mp = modpow(MOD)
for i in range(K, 0, -1):
  t = K // i
  u = mp.modpow(t, N)
  for j in range(i + i, K + 1, i):
    u -= D[j]
  while (u < 0):
    u += MOD
  ans = (ans + u * i) % MOD
  D[i] = u
print(ans)

Submission status: Accepted

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

ans = 0
cnt = 0
gs = dict()
for i in range(K,1,-1):
    n = pow(K//i,N,mod)
    for j in range(2,K+1):
        if i*j > K: break
        n -= gs[i*j]
        n %= mod
    gs[i] = n
    ans += n*i%mod
    ans %= mod
    cnt += n
    cnt %= mod
ans += pow(K,N,mod) - cnt
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def make_divisors(n,sort=False):
    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)
    if sort:
        divisors.sort()
    return divisors

N,K = LI()

numl = [0]*(K+1)

ans = 0
for i in range(1,K+1)[::-1]:
    num = pow(math.floor(K/i),N,mod)
    for j in range(2*i,K+1,i):
        num -= numl[j]
        num %= mod
    numl[i] = num
    ans += num*i
    ans %= mod

print(ans)

Submission status: Accepted

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

for x in range(k,0,-1):
    tmp = pow(k//x,n,mod)
    i = 2
    while i*x <= k:
        tmp -= A[i*x]
        i += 1
    A[x] = tmp
    A[x] %= mod
ans = 0
for i in range(1,k+1):
    ans += i * A[i]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

def 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(reverse=True)
    return divisors

n, k = map(int, input().split())
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):
    div = divisors(i)
    base = cnt[i]
    for d in div[1:]:
        cnt[d] -= base
ans = 0
for i, item in enumerate(cnt):
    ans += i * item
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce

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

mod=10**9+7

ar=list(range(1,k+1))
ar.reverse()

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

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(1, k+1)[::-1]:
    res = pow(k//i, n, mod)
    for j in range(i*2, k+1, i):
        res-=dp[j]
    dp[i] = res%mod
    ans+=i*res
    ans%=mod
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
pr=10**9+7
a=0
l=[None]*(K+1)
for i in range(K,0,-1):
    t=pow(K//i,N,pr)
    c=i*2
    while c<=K:
        t-=l[c]
        c+=i
    l[i]=t
    a=(a+t*i)%pr
print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    div_list = [[] for _ in range(K+1)]
    for d in range(1, K+1):
        for i in range(2, K+1):
            if d*i > K:
                break
            div_list[d*i].append(d)

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


if __name__ == '__main__':
    main()

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:
import sys
input = sys.stdin.readline

mod = 10**9+7

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

ans = 0
dp = [None]*(K+1)
for n in reversed(range(1, K+1)):
    L = K//n
    p = pow(L, N, mod)
    for i in range(2, L+1):
        p = (p - dp[n*i]) % mod
    
    dp[n] = p
    ans = (ans + p*n) % mod

print(ans)

Submission status: Accepted

Solution code:

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

mod = 10**9+7

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

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

    now = pow(K // i,N,mod)

    for j in range(2*i,K+1,i):

        now -= ans[j]
        now %= mod

    ans[i] = now % mod
    ss += i * now
    ss %= mod

    
print (ss)

Submission status: Accepted

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

ans = 0
cnt = [0] * (k + 1)
for num in range(1, k + 1)[::-1]:
    cnt[num] = pow((k // num), n, MOD)
    tmp = 2 * num
    while True:
        if tmp >= k + 1:
            break
        cnt[num] -= cnt[tmp]
        cnt[num] % MOD
        tmp += num
        
for num in range(1, k + 1):
    ans += cnt[num] * num
    ans %= MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

def Eratosthenes(N): #N以下の素数のリストを返す
    N+=1
    is_prime_list = [True]*N
    m = int(N**0.5)+1
    for i in range(3,m,2):
        if is_prime_list[i]:
            is_prime_list[i*i::2*i]=[False]*((N-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,N,2) if is_prime_list[i]]

#p,n,k,b,*a = [int(i) for i in read().split()]

# k以下、長さn
n,k = map(int,input().split())

MOD = 10**9+7
res = [0]+[pow(k//i,n,MOD) for i in range(1,k+1)]

p = Eratosthenes(k)

#print(res)
for i in p:
    for j in range(i,k+1,i):
        res[j//i] -= res[j]

#print(res)
print(sum(ri*i for i,ri in enumerate(res))%MOD)

Submission status: Accepted

Solution code:
def gcd(x,y):
    while(y): 
        x, y = y, x % y 
    return x
    
MOD = 10 ** 9 + 7

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

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

for i in range(1, K + 1):
    count = K//i
    out += val[i] * pow(count, N, MOD)
    out %= MOD
print(out)

Submission status: Accepted

Solution code:
from math import gcd
MOD = 10**9+7
n, k = map(int, input().split())
ans = [0 for _ in range(k+1)]
for i in range(k, 0, -1):
	tmp = pow(k//i, n, MOD)
	for j in range(2*i, k+1, i):
		tmp -= ans[j]
		tmp %= MOD
	ans[i] = tmp
#print(ans)
res = 0
for i, x in enumerate(ans):
	res += x * i
	res %= MOD
print(res)

Submission status: Accepted

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

ans = 0
b = [0]*(k+1)
for i in reversed(range(1, k + 1)):
    c = a[i]
    for j in range(i + i, k + 1, i):
        c -= b[j]
    c %= mod
    b[i] = c
    ans += c * i
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def main():
    mod=1000000007
    n,k=map(int,input().split())
    A=[0]*(k+1)
    A[k]=1
    for i in range(1,k)[::-1]:
        l=k//i
        A[i]=pow(l,n,mod)
        for j in range(2,l+1):
            #print(i,i*j)
            A[i]-=A[i*j]
            A[i]%=mod
    #print(A)
    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:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, K = na()
mod = 1000000007

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[j]
        j += i
    if a[i] < 0:
        a[i] %= mod
        if a[i] < 0: a[i] += mod

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

Submission status: Runtime Error

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

b = N
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1


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

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

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

Submission status: Runtime Error

Solution code:

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

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

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

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

print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()

lr = list()
lg = list()
lb = list()

for i in range(n):
    if s[i] == "R":
        lr.append(i)
    if s[i] == "G":
        lg.append(i)
    if s[i] == "B":
        lb.append(i)

r = len(lr)
g = len(lg)
b = len(lb)

ans = r*g*b

for i in lr:
    for j in lg:
        d1 = abs(i-j)
        if max(i,j) + d1 in lb:
            ans -= 1
        if min(i,j) - d1 in lb:
            ans -= 1
        if min(i,j) + d1/2 in lb:
            ans -= 1
print(ans)

Submission status: Runtime Error

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

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

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

N, K = LI()

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

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math
k = int(input())
 
ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        tmp = math.gcd(i, j)
        for l in range(1, k+1):
            ans += math.gcd(tmp, l)
print(ans)

Submission status: Runtime Error

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

L = [0]*(k+1)

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

Submission status: Runtime Error

Solution code:

import math
from functools import reduce
# def gcd(*numbers):
#     return reduce(math.gcd, numbers)

k = int(input())
res = 0
for c in range(1,k+1):
    for b in range(1,k+1):
        for a in range(1,k+1):
            # res += gcd(a,b,c)
            gcd1 = math.gcd(a,b)
            gcd2 = math.gcd(gcd1,c)
            res += gcd2
print(res)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define For(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
typedef vector<long long> vlint;
typedef vector<string> vstr;
typedef vector<char> vchar;
typedef vector<vector<long long>> vlint2;

lint powmod(lint a, lint b, lint mod = 1000000007) {
   lint res = 1;
   for (a %= mod; b; a = a * a % mod, b >>= 1)
     if (b & 1) res = res * a % mod;
   return res;
}


int main() {
    int mod = 1000000007;
    int n, k; cin >> n >> k;
    lint cnt[k+10];

    for (int x = k; x > 0; x--){
        cnt[x] = powmod(k/x, n);
        for (int y = 2 * x; y <= k; y+=x){
            cnt[x] -= cnt[y];
        }
    }
    lint ans = 0;
    For(i, 1, k+1){
        ans += (i * cnt[i]) % mod;
        ans %= mod;
    }
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define For(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
typedef vector<long long> vlint;
typedef vector<string> vstr;
typedef vector<char> vchar;
typedef vector<vector<long long>> vlint2;

lint powmod(lint a, lint b, lint mod = 1000000007) {
   lint res = 1;
   for (a %= mod; b; a = a * a % mod, b >>= 1)
     if (b & 1) res = res * a % mod;
   return res;
}
lint calc(lint a){
    if (a == 1) return 1;
    lint res = a;
    for (int i = 2; i <= sqrt(a);i++){
        if (a % i == 0){
            res -= i + a/i;
        }
    }
    return res-1;
}

int mod = 1000000007;
int main() {
    int n, k; cin >> n >> k;
    lint cnt[k+10];
    lint weight[k+10];

    for (int x = k; x > 0; x--){
        cnt[x] = powmod(k/x, n);
        for (int y = 2 * x; y <= k; y+=x){
            cnt[x] -= cnt[y];
        }
    }
    lint ans = 0;
    For(i, 1, k+1){
        ans += (i * cnt[i]) % mod;
        ans %= mod;
    }
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
c = 10**9+7
tm = [0] + [1]*k
a = k//2
ans = k*(k+1)//2 - a*(a+1)//2
for i in range(k//2, 0, -1):
    a = k//i
    t = (left_bin(a, n, c) - sum([tm[j*i] for j in range(2, a+1)])) % c
    ans = (ans + t*i) % c
    tm[i] = t
print(ans)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

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

n, k = map(int,input().split())
ans = int(k*(k+1)//2) #1種類のやつ

def function(n,k):
    if n < 1:
        return 0
    else:
        for i in range(1,k+1):
            ans += gcd(i,j) * math.factorial(n)
        return  ans + function(n-1)

for i in range(2,n+1): #2~n種類までループ
    for j in range(i+1,k+1):
        ans += gcd(i,j) * math.factorial(n) #数2種類
        for k in range(j+1,k+1):
            ans += gcd(i, j, k) * 6 #数3種類
    
print(function(n,k))