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 = 1000000000 + 7

def fastpow(x,y):
    ans = 1

    global Mod
    while y:
        if (y & 1): ans = (ans * x) % Mod
        x = (x * x) % Mod
        y >>= 1
    return ans

def solve(N,K):
    # f[i] is number (x1,....xn) such that gcd(x1,..,xK) = i
    
    f = [0]*(K + 1)
    for i in range(K,0,-1):
        f[i] = fastpow(K//i,N)
        for j in range(i + i,K + 1,i):
            f[i] -= f[j]

    global Mod
    ans = 0
    for i in range(1,K + 1):
        ans = (ans + i*f[i]) % Mod
    return ans


if __name__ == "__main__":
    
    N, K = map(int,input().split())
    print(solve(N,K))

Submission status: Accepted

Solution code:
def sumGCD(N,K,M):
    dp = [None for _ in range(K+1)]
    #dp[i]:gcd(A) % i == 0を満たすAの個数
    for i in reversed(range(1,K+1)):
        dp[i] = pow(K//i,N,M)
        for j in range(2,K//i+1):
            dp[i] -= dp[i*j]
            dp[i] %= M

    output = 0
    for i in range(1,K+1):
        output += (dp[i]*i)
        output %= M

    return output

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

    print(sumGCD(N,K,10**9+7))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

def solve(N, K):
    mod = 10 ** 9 + 7
    multiples = [[] for _ in range(K + 1)]
    for k in range(1, K + 1):
        for i in range(k, K + 1, k):
            multiples[k].append(i)

    gcdcounts = [0] * (K + 1)  # gcd 毎の組み合わせ個数
    gcdsums = [0] * (K + 1)   # gcd 毎の合計値
    for k in reversed(range(1, K + 1)):
        x = pow(len(multiples[k]), N, mod)
        for l in multiples[k]:
            x -= gcdcounts[l]
        gcdcounts[k] = x % mod
        gcdsums[k] = x * k % mod
    print(sum(gcdsums) % mod)


if __name__ == '__main__':
    N, K = map(int, input().split())
    solve(N, K)

Submission status: Accepted

Solution code:
# E - Sum of gcd of Tuples (Hard)
# https://atcoder.jp/contests/abc162/tasks/abc162_e

MOD = 10 ** 9 + 7

n, k = map(int, input().split())
dic = [0] * (k + 1)

ans = 0
for i in range(k, 0, -1):
  dic[i] = pow(k // i, n, MOD)

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

MOD = 10 ** 9 + 7
N, K = nm()


def solve():
    ans = 0
    tbl = [0] * (K + 1)
    for i in range(K, 0, -1):
        m = K // i
        p = pow(m, N, MOD)

        j = 2
        while j * i <= K:
            p += MOD - tbl[j * i] % MOD
            p %= MOD
            j += 1
        tbl[i] = p

        ans += i * p % MOD
        ans %= MOD
    return ans


print(solve())

Submission status: Accepted

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

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

# print(d)

for i in range(K, 0, -1):
    # print('i', i)
    for j in range(K//i, 1, -1):
        # print(' j', j)
        # print(i, i*j)
        d[i] -= d[i*j]
    # print(d)

res = 0
for i, v in enu(d):
    res += i*v
    res %= MOD
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

lst = [0] * (K + 1)

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

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

print (ans)

Submission status: Accepted

Solution code:
N, K = [int(i) for i in input().split()]
MOD = 10**9 + 7

class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )


memo = [-1] * K
def count(k):
    if(memo[k-1] != -1):
        return memo[k-1]
    
    if(k > K//2):
        memo[k-1] = ModInt(1)
        return memo[k-1]
    
    res = ModInt(K//k) ** N
    for i in range(2, K//k + 1):
        res -= count(i * k)

    memo[k-1] = res
    return res

ans = 0
for k in range(K, 0, -1):
    ans += count(k) * k
print(ans)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

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

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

print(ans)

Submission status: Accepted

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

mod = 10**9+7

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res


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

    for j in range(1, num):
        dp[i] -= dp[(j + 1) * i]
    ans += i * dp[i]
    ans %= mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
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

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

N,K = IL()

d = DD(int)

for i in range(1,K+1)[::-1]:
  n = K//i

  d[i] = pow(n,N,MOD) - sum(d[j*i] for j in range(2,n+1))
keys = [k for k in d]

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

P(ans)

Submission status: Accepted

Solution code:
Q = 10**9+7
def main():
    N, K = map( int, input().split())
    ANS = [0]*(K+1)
    for x in range(K,0,-1):
        ans = pow(K//x,N,Q)
        for i in range(2, K+1):
            if x*i > K:
                break
            ans -= ANS[x*i]
        ANS[x] = ans%Q
    print( sum( [ANS[i]*i%Q for i in range(K+1)])%Q)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

nums = [0] * (K+1)
for i in reversed(range(1, K+1)):
    num = pow(K//i, N, MOD)
    for j in range(2*i, K+1, i):
        num -= nums[j]
    nums[i] = num % MOD

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

print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


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

    ans = 0
    n_gcd = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        n = pow(K // k, N, mod=P)
        for kk in range(2 * k, K + 1, k):
            n -= n_gcd[kk]
        n_gcd[k] = n % P
        ans += k * n_gcd[k]
        ans %= P

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


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

    ans = 0
    n_gcd = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        n = pow(K // k, N, mod=P)
        for kk in range(2 * k, K + 1, k):
            n -= n_gcd[kk]
        n_gcd[k] = n % P
        ans = (ans + k * n_gcd[k]) % P

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


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

    ans = 0
    n_gcd = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        n = pow(K // k, N, mod=P)
        for m in range(2, K // k + 1):
            n -= n_gcd[k * m]
        n_gcd[k] = n % P
        ans = (ans + k * n_gcd[k]) % P

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


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

    ans = 0
    n_gcd = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        n_gcd[k] = pow(K // k, N, mod=P)
        for m in range(2, K // k + 1):
            n_gcd[k] -= n_gcd[k * m]
        n_gcd[k] %= P
        ans = (ans + k * n_gcd[k]) % P

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


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

    ans = 0
    n_gcd = dict.fromkeys(range(K + 1), 0)
    for k in reversed(range(1, K + 1)):
        n_gcd[k] = pow(K // k, N, mod=P)
        for m in range(2, K // k + 1):
            n_gcd[k] = (n_gcd[k] - n_gcd[k * m]) % P
        ans = (ans + k * n_gcd[k]) % P

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


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

    ans = 0
    n_gcd = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        n_gcd[k] = pow(K // k, N, mod=P)
        for m in range(2, K // k + 1):
            n_gcd[k] = (n_gcd[k] - n_gcd[k * m]) % P
        ans = (ans + k * n_gcd[k]) % P

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


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

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

    n_gcd = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        n_gcd[k] = pow(n_multiple[k], N, mod=P)
        for m in range(2, K // k + 1):
            n_gcd[k] = (n_gcd[k] - n_gcd[k * m]) % P

    ans = 0
    for k in range(1, K + 1):
        ans = (ans + k * n_gcd[k]) % P
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


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

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

    n_gcd = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        n_gcd[k] = pow(n_multiple[k], N, mod=P)
        m = 2
        kk = k * m
        while kk <= K:
            n_gcd[k] = (n_gcd[k] - n_gcd[kk]) % P
            m += 1
            kk = k * m

    ans = 0
    for k in range(1, K + 1):
        ans = (ans + k * n_gcd[k]) % P
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
n, k = map(int, input().split())
d = [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*i, k + 1, i):
        d[i] -= d[j]
        d[i] %= MOD
print(sum(i * d[i] % MOD for i in range(1, k + 1)) % MOD)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
d = [0]*(K+1)
MOD = 10**9+7
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
ans=0

baig=[0]*(10**5+1)
exg=[0]*(10**5+1)

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

for j in range(k,0,-1):
    exg[j]=baig[j]
    for jj in range(2*j,k+1,j):
        exg[j]-=exg[jj]
    exg[j]%=MOD
    ans+=exg[j]*j
    ans%=MOD

print(int(ans))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    """"ここに今までのコード"""
    n, k = map(int, input().split())
    MOD = 10 ** 9 + 7
    ans = 0
    baig = [0 for i in range(10 ** 5 + 1)]

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

    for j in range(k, 0, -1):
        for jj in range(2 * j, k + 1, j):
            baig[j] -= baig[jj]
        baig[j] %= MOD
        ans += baig[j] * j
        ans %= MOD
    print(int(ans))
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9+7
N, K = list(map(int, input().split()))
t = {}
ans = 0

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

    for j in range(2*i, K+1, i):
        n -= t[j]
    t[i] = n
    ans = (ans + i * n) % MOD
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
mod=pow(10,9)+7
ans=[0]*(k+1)
# gcdがkiとなる数列。すべてがkiの倍数でかつ少なくとも一つkiを含む
for ki in range(k,0,-1):
    a=k//ki
    ans[ki]=pow(a,n,mod)
    i=2
    while i*ki<=k:
        ans[ki]-=ans[i*ki]
        i+=1
b=0
for ki in range(1,k+1):
    b+=(ans[ki]*ki)%mod
    b%=mod
print(b)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(self.power_func(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(self.power_func(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

    def power_func(self,a,n,p):
        bi=str(format(n,"b"))#2進表現に
        res=1
        for i in range(len(bi)):
            res=(res*res) %p
            if bi[i]=="1":
                res=(res*a) %p
        return res
#グローバル変数MODを決めてあげてください

#グローバル変数MODを決めてあげてください
MOD = 10**9 + 7

N,K=[int(hoge) for hoge in input().split()]
Kazus = [0]*(K+1)
for x in range(K,0,-1):
    Dmax = K//x
    MoDmax = ModInt(Dmax)
    kazu = MoDmax ** N
    for d in range(Dmax,1,-1):
        kazu -= Kazus[d*x]
    Kazus[x] = kazu

print(sum([x*k for x,k in enumerate(Kazus) ]))

Submission status: Accepted

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

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

class Solver:

    def __init__(self, n, k):
        self.n = n
        self.k = k
        #fprint('k') # debug
        #fprint(k) # debug
        self.ans_list = [0] * (k + 1) # var[i] = count of gcd() == i case
        #fprint('self.ans_list') # debug
        #fprint(self.ans_list) # debug
        self.m = 10 ** 9 + 7

    def gcd_count(self, i):
        times = k // i
        cases = pow(times, n, self.m)
        j = i * 2
        while not (j > k):
            cases -= self.ans_list[j]
            j += i
        #fprint('i') # debug
        #fprint(i) # debug
        self.ans_list[i] = cases % self.m

    def run(self):
        for i in range(k, 0, -1):
            #print('i') # debug
            #print(i) # debug
            self.gcd_count(i)
        ans = 0
        for i, a in enumerate(self.ans_list):
            ans += i * a
        #fprint('self.ans_list') # debug
        #fprint(self.ans_list) # debug
        return ans % self.m



if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    ans = Solver(n, k).run()
    #fprint('ans') # debug
    print(ans)


    #fprint('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Accepted

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: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

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

# print(ans)
print(sum([ans[i]*i%mod for i in range(1,k+1)])%mod)

'''
1以上K以下の整数からなる長さNの数列{A_1,...A_N}を考える。
K^N個考えられる数列のgcd(A_1,...A_N)の和を求め、10^9+7で割った余りを出力せよ。

term:
2<=N<=10**5
1<=K<=10**5
input:
3 2
output:
    9
'''

'''
K^N個の数列すべてに対してgcdを計算しているとO((K^N)*(N+logK))になり間に合わない。
そこで、問題を
「1<=X<=Kに対してgcd(A_1,...A_N)=Xとなる数列A_iがいくつあるか」
という問題に読み替える。
Xが最大公約数であるためには{A_1,...A_N}がすべてXの倍数でなければならない。
K以下でXの倍数である数の個数はK//Xで求められる。
これらによって構成される数列は(K//X)^N種類ある。
しかしgcdがXの倍数であるものも含まれてしまうのでそれを包除原理で除く。
ex)
    K=4,N=3のとき(4,4,4)はすべて2の倍数だがgcdは4。
    したがって{(4//2)^3-(4//(2*2))^3}%modとする。
'''

Submission status: Accepted

Solution code:
import sys
MOD = 10**9+7
def main():
    input = sys.stdin.readline
    N,K=map(int, input().split())
    ans=Mint()
    cnt=[Mint() for _ in range(K+1)]
    for g in range(K,0,-1):
        cnt[g]+=pow(K//g,N,MOD)
        for h in range(g+g,K+1,g):
            cnt[g]-=cnt[h]
        ans+=g*cnt[g]
    print(ans)

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self
    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
#import numpy as np
#INF = float("inf")
#MOD = 10**9+7
MOD = 10**9+7
import math
N,K = map(int,input().split())
ans = [0]*K
for i in range(K):
    p = K-i
    a = pow(math.floor(K/p),N,MOD)
    x = 1
    while p*(x+1) <= K:
        a -= ans[p*(x+1)-1]
        x = x+1
    ans[p-1] = a%MOD
s = 0
for i in range(K):
    s += (i+1)*ans[i]
    s = s%MOD
print(s)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)



class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = [2]
        for j in range(4, m, 2):
            a[j] = False
        for i in range(3, m, 2):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False
        self.ds_memo = {}
        self.ds_memo[1] = set([1])

    def is_prime(self, n):
        return self.A[n]

    def division(self, n):
        d = collections.defaultdict(int)
        for c in self.T:
            while n % c == 0:
                d[c] += 1
                n //= c
            if n < 2:
                break
        if n > 1:
            d[n] += 1
        return d.items()

    # memo
    def divisions(self, n):
        if n in self.ds_memo:
            return self.ds_memo[n]

        for c in self.T:
            if n % c == 0:
                rs = set([c])
                for cc in self.divisions(n // c):
                    rs.add(cc)
                    rs.add(cc * c)
                self.ds_memo[n] = rs
                return rs

        rs = set([1, n])
        self.ds_memo[n] = rs
        return rs

def main():
    n,k = LI()
    pr = Prime(10**5)
    c = collections.defaultdict(int)
    for i in range(k, 0, -1):
        t = k // i
        p = (pow(t, n, mod) + c[i]) % mod
        ds = pr.divisions(i)
        for kk in ds:
            if kk == i:
                continue
            c[kk] -= p
        c[i] = p

    r = sum(k*v%mod for k,v in c.items()) % mod

    return r

print(main())