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: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

cnt = 0
ans = 0

for i in range(2,k+1):
  if k//i-1 == 0:
      cnt += 1
      ans += i
  else:
    for j in range(1,n+1):
      cnt += cmb(n,j)
      ans += i*cmb(n,j)*(k//i-1)**(n-j)

ans += k**n - cnt

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import jit

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

@jit
def main():
  mod=10**9+7
  L=np.zeros(k+1,dtype='int64')
  ans=0
  for i in range(k,0,-1):
    li=(k//i)**n
    cnt=1
    while i*(cnt+1)<=k:
      cnt+=1
      li-=L[i*cnt]
    L[i]=li
    ans+=(li*i)%mod
  return ans%mod

if __name__=="__main__":
  print(main())

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
gcddic = [0]*K
for i in range(K-1,-1,-1):
    gcddic[i] = (K//(i+1))**N
    ll=2
    while(ll*(i+1)<=K):
        gcddic[i] -= gcddic[ll*(i+1)-1]
        ll += 1
sumnation = 0
for i,l in enumerate(gcddic):
    sumnation += (i+1)*l
print(sumnation)

Submission status: Wrong Answer

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] 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: Wrong Answer

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):
        if i * j > k:
            break
        ans[i] -= ans[i * j]

# print(ans)
print(sum(ans))

'''
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: Wrong Answer

Solution code:
def find(N,K):
    MOD = 10**9+7
    number = [1]*(K+1)
    for i in range(K,0,-1):
        number[i] = pow(K//i,N,MOD)
        for j in range(2,K+1):
            if i*j>K:
                break
            number[i] -= number[i*j]
            number[i] %= MOD
    ans = 0
    for k in range(1,K+1):
        ans += number[k]*k
        ans %= MOD
    return ans
N,K = list(map(int,input().strip().split()))

Submission status: Wrong Answer

Solution code:
def find_primes(K):
    # list te smallest prime which divide x
    A = [1]*(K+1)
    for i in range(2,K+1):
        if A[i] > 1:
            continue
        for j in range(1,K+1):
            k = i*j
            if k>K:
                break
            if A[k] == 1:
                A[k] = i
    return A

def find_factors(K):
    P = find_primes(K)
    F = [[] for _ in range(K+1)]
    F[0] = [1]
    F[1] = [1]
    for k in range(2,K+1):
        if P[k] == k:
            F[k] = [1,k]
        else:
            temp = k//P[k]
            F[k] = F[temp] + [x*P[k] for x in F[temp]]
    
    F = [list(set(x)) for x in F]
    return F
        
def find(N,K):
    MOD = 10**9+7
    F = find_factors(K)
    ans = 0
    number = [0] + [pow(K//i,N,MOD) for i in range(1,K+1)]
    
    for k in range(1,K+1):
        
        for x in F[k]:
            if x<k:
                number[x] -= number[k]
                
    for i in range(1,K+1):
        ans += i*number[i]
        ans %= MOD
        
    
    return ans


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

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
lim=10**9+7
ans = pow(k,n,lim)
ans += (k*(k-1)//2)%lim
print(ans%lim)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
lim=10**9+7
ans = pow(k,n,lim)
ans += (k*(k+1)//2)%lim
print(ans%lim)

Submission status: Wrong Answer

Solution code:
def left_bin(a, n, c):
    ns = [int(i) for i in bin(n)[3:]]
    t = a
    for i in ns:
        t = t*t % c
        if i == 1:
            t = t*a % c
    return t


n, k = map(int, input().split())
c = 10**9+7
tm = [0] + [1]*k
a = k-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: Wrong Answer

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(i, k+1):
    ans += d[i] * i

print (ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict

N,K = map(int,input().split())
dict = defaultdict(lambda: 0)

ans = 0

for i in range(K,0,-1):
    #最大公約数がiの倍数になる数列の数
    a = (K//i)**N
    for j in range(i+1,K+1):
        if j%i == 0:
            a -= dict[j]
            

    dict[i] = a
    ans += (a*i) % (10**9+7)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h,w): return [[i for j in range(w)] for k in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

input = sys.stdin.readline


N,K = MI()
ans_l = [0 for i in range(K)]
for l in range(K,0,-1):
    ans = pow(K//l,N,MOD)
    newl = 2*l
    multi_num = 2
    while newl<K:
        ans -= ans_l[newl-1]
        multi_num += 1
        newl = l*multi_num
    ans_l[l-1] = ans%MOD
ans = 0
for i in range(K):
    ans += (i+1)*ans_l[i]%MOD
ans = ans%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
m=1000000007
ans=0
dp=[0]*(k+1) #dp[i]:=iを数列内の最大値とするもののgcd合計
for i in range(k,0,-1):
  mul_i=k//i#iの倍数の個数
  dp[i]=pow(mul_i,n)
  for j in range(2,mul_i+1):
    dp[i]-=dp[i*j]
  ans+=i*dp[i]
print(ans)

Submission status: Wrong Answer

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

counts = [0]*(K)
for x in range(K,0,-1):
    y = K//x
    counts[x-1] = y**N%mod
    if y >= 2:
        for i in range(2,y+1):
            counts[x-1] = (counts[x-1]- counts[i*x-1]%mod )% mod
ans = 0
for i in range(K):
    ans += (ans +(i+1)*counts[i] % mod) % mod
print(ans)

Submission status: Wrong Answer

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

counts = [0]*(K)
for x in range(K,0,-1):
    y = K//x
    counts[x-1] = y**N%mod
    if y >= 2:
        for i in range(2,y+1):
            counts[x-1] = (counts[x-1]- counts[i*x-1]%mod )% mod
ans = 0
for i in range(K):
    ans += (i+1)*counts[i] % mod
print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd
import itertools
N, k = map(int, input().split())
 
result = 0
 
# 3つとも等しい数字
for i in range(1, k+1):
    result += i
 
# 2つが等しくて、1つが異なる数字
for set in list(itertools.combinations(range(1, k+1), 2)):
    result += (gcd(set[0], set[1]))*6
 
# 3つとも異なる
for set in list(itertools.combinations(range(1, k+1), 3)):
    result += (gcd(gcd(set[0], set[1]), set[2]))*6
 
print(result)