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:
N,K=list(map(int,input().split()))
size=[[0]*K][0]
sum=0
mod=10**9+7
for x in range(0,K):
    x=K-x
    tmp=(K//x)**N%mod
    for y in range(2*x,K+1,x):
        tmp-=size[y-1]
    size[x-1]=tmp
    sum+=(size[x-1]*x)%mod
print(sum)

Submission status: Wrong Answer

Solution code:
N,K=list(map(int,input().split()))
size=[[0]*K][0]
sum=0
for x in range(0,K):
    x=K-x
    tmp=(K//x)**N
    for y in range(2*x,K+1,x):
        tmp-=size[y-1]
    size[x-1]=tmp
    sum+=size[x-1]*x
print(sum)

Submission status: Wrong Answer

Solution code:
# countBcd[i] : 最大公約数がiとなる数列の個数
# 全てiの倍数である数列の数はint(K/i) ** N ただし、全てi*2,i*3・・・の場合を除く

N, K = [int(x) for x in input().split()]
countBcd = [0]*(K+1)
mod=10**9+7
sumTotal=0
for i in range(K,0,-1):
    countBcd[i] = pow(K//i,N,mod)

    for j in range(i*2,K+1,i):
        countBcd[i] - countBcd[j]

    sumTotal += i*countBcd[i]%mod

print(sumTotal%mod)

Submission status: Wrong Answer

Solution code:
# countBcd[i] : 最大公約数がiとなる数列の個数
# 全てiの倍数である数列の数はint(K/i) ** N ただし、全てi*2,i*3・・・の場合を除く

N, K = [int(x) for x in input().split()]
countBcd = [0]*(K+1)
mod=10**9+7
sumTotal=0
for i in range(K,0,-1):
    countBcd[i] = int(K/i) ** N

    for j in range(i*2,K+1,i):
        countBcd[i] += mod - countBcd[j]
        countBcd[i] %= mod

    print(i)
    sumTotal += i*countBcd[i]
    sumTotal %= mod

print(sumTotal)

Submission status: Wrong Answer

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

for i in reversed(range(1,k+1)):
    l[i]=pow(math.floor(k/i),n)
    a=2*i
    while a<=k:
        l[i]-=l[a]
        a+=i
    ans+=l[i]*i%mod

print(ans)

Submission status: Wrong Answer

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

for i in reversed(range(1,k+1)):
    l[i]=pow(math.floor(k/i),n)%mod
    a=2*i
    while a<=k:
        l[i]-=l[a]
        a+=i
    ans+=l[i]*i%mod

print(ans)

Submission status: Wrong Answer

Solution code:
import math
a=10**9+7
N,K=map(int,input().split())
gcd=[0]*(K+1)
ans=0
multipleNumber=0
for i in reversed(range(1,K+1)):
    multipleNumber=math.floor(K/i)
    totalNumber=multipleNumber**N
    if 2*i<=K:
        minus=range(2*i,K+1,i)
        for j in minus:
            totalNumber-=gcd[j]
    gcd[i]=totalNumber
for i in range(1,len(gcd)):
    ans+=i*gcd[i]
print(ans)

Submission status: Wrong Answer

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

count = 0
sumn = 0
for i in range(2, K+1):
    ty = K // i
    sumn += i * max(ty**N - (ty-1)**N,1)
    count += max(ty**N - (ty-1)**N,1)
    print(i, max(ty**N - (ty-1)**N,1))
print((sumn + K**N - count)%(10**9+7))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

n, k = map(int, input().split())
ans = [0 for i in range(k+1)]
for i in range(k,0,-1):
    t = 0
    for j in range(2*i, k+1, i):
        t += ans[j]
    ans[i] = pow(k//i, n) - t
sm = 0
for i in range(k+1):
    sm += i*ans[i]
print(sm % MOD)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)

def gcd(x, y):
    while (y):
        x, y = y, x % y
    return x
MOD = int(10e9 + 7)



n, k = map(int, input().split())
mem = {}
def dp(at, cur):
    if at == n:
        return cur
    if cur == 1:
        return pow(k, n-at, MOD)
    if (at,cur) in mem:
        return mem[(at,cur)]
    sm = 0
    for i in range(1, k+1):
        sm += dp(at+1,gcd(cur, i))
    mem[(at,cur)] = sm % MOD
    return sm % MOD



sm = 0
for i in range(1, k+1):
    sm += dp(1, i)
print(sm % MOD)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)

def gcd(x, y):
    while (y):
        x, y = y, x % y
    return x
MOD = int(10e9 + 7)



n, k = map(int, input().split())
mem = {}
def dp(at, cur):
    if at == n:
        return cur
    if (at,cur) in mem:
        return mem[(at,cur)]
    sm = 0
    for i in range(1, k+1):
        sm += dp(at+1,gcd(cur, i))
    mem[(at,cur)] = sm % MOD
    return sm % MOD

sm = 0
for i in range(1, k+1):
    sm += dp(1, i)
print(sm % MOD)

Submission status: Wrong Answer

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(G)
print(sum([i*f for i,f in enumerate(G)]) % mod)

Submission status: Wrong Answer

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

Solution code:
import math
n,k = map(int,input().split())
dp = [0]*100010
MOD = 1000000007
for g in reversed(range(1,k+1)):
    reg=0
    if(math.floor(k//g) >= 2):
        for i in range(2,math.floor(k//g)+1):
            reg += dp[i*g] %MOD
        
    dp[g] = math.floor(k//g)**n%MOD - reg % MOD
    
sum = 0
for i in range(1,k+1):
    sum += i * dp[i]%MOD
print("{}".format(sum))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

    d = [0 for _ in range(k + 1)]
    f = [i for i in range(k + 1)]
    for i in range(k, 0, -1):
        x = k // i
        tmp = x ** n
        sub = sum(d[i::i])
        res = tmp - sub
        d[i] = res

    ans = sum(i * j for i, j in zip(d, f))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    p = 10 ** 9 + 7
    ans = 1
    for _ in range(n):
        ans *= k
        ans %= p

    for i in range(2, k + 1):
        x = k//i
        c = x ** n - (x-1) ** n
        d = (i-1) * c
        ans += d
        ans %= p

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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
print(ans)

Submission status: Wrong Answer

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

d = dict()
ans = 0
for X in range(K,0,-1):
  res = (K//X)**N
  for k in range(2*X,K+1,X):
    res -= d[k]
  d[X] = res
  ans += res*X
  
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from sys import stdin
import itertools
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
  
def main():
  N, K = map(int, stdin.readline().split(" "))
  
  ans = 0
  
  for xs in itertools.combinations_with_replacement(range(1, K+1), N):
    
    if len(set(xs)) == 1:
      ans += gcd(*xs)
    elif len(set(xs)) == 2:
      ans += 3*gcd(*xs)
    else:
      ans += 6*gcd(*xs)
      
  print(ans % (10**9 + 7))
 
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from sys import stdin
import itertools

def gcd(*numbers):
    return reduce(math.gcd, numbers)
  
def main():
  N, K = map(int, stdin.readline().split(" "))
  
  ans = 0
  
  for xs in itertools.combinations_with_replacement(range(1, K+1), N):
    
    if len(set(xs)) == 1:
      ans += gcd(*xs)
    elif len(set(xs)) == 2:
      ans += 3*gcd(*xs)
    else:
      ans += 6*gcd(*xs)
      
  print(ans % (10**9 + 7))

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
print(9)

Submission status: Wrong Answer

Solution code:
n, k = (int(x) for x in input().split())

c = {} 
t = 0
for x in range(k, 0, -1):
    q = k // x
    c[x] = q ** n # - sum(c[x * y] for y in range(2, q + 1))
    t += c[x] * x
    t = t % 1000000007

print(t)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

m = 1000000007

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

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

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

s = 0
for i in range(1, k + 1):
    s += (i * c[i]) % m

print(s)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

m = 1000000007

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

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

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

s = 0
for i in range(1, k + 1):
    s += (i * c[i]) % m

print(s)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

m = 1000000007

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

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

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

s = 0
for i in range(1, k + 1):
    s += (i * c[i]) % m

print(s)

Submission status: Wrong Answer

Solution code:
import math

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

cnt = [0]*(10**6)

for i in range(1, k+1):
    cnt[i] = 2**10000
    cnt[i] = pow(math.floor(k/i), n, mod)


for i in range(k+1, 0, -1):
    j = 2
    while i*j <= k:
        cnt[i] -= cnt[i*j]
        cnt[i] %= mod
        j += 1

ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
ans = 0
lis = [0]*K
mod = 1e9 + 7
def modpow(a, n, mod):
    ans = 1
    while n > 0:
        if n&1:
            ans = ans * a % mod
        a = a * a % mod
        n = n >> 1
    return ans
for x in range(K,0, -1):
    a = (K // x) % mod
    b = modpow(a, N, mod)
    for i in range(2, K//x +1):
        b = (b - lis[x*i-1]) %mod
        if b < 0:
            b += mod
    lis[x-1] = b
    ans = (ans + b*x%mod) % mod
print(int(ans))

Submission status: Wrong Answer

Solution code:

# -*- coding: utf-8 -*-

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


count=0
lis=[[0 for i in range(K)] for k in range(K)]
l0=[1 for i in range(K)]

ans=0

sq=int(K**0.5)
for i in range(1,K+1):
    for j in range(i+1,K+1):
        k=math.gcd(i,j)
        lis[i-1][j-1] =k
print(lis)
#print("fin")
for i in range(2,N+1):
    l1=[0 for i in range(K)]
    for n in range(K):
        l1[n]+=l0[n]
        for j in range(n+1, K):
            k=lis[n][j]
            l1[k-1]+=l0[n]+l0[j]
    
    l0=l1.copy()
    print(l0)


for i in range(1,K+1):
    ans+=i*l0[i-1]
#print(l0)
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
MOD = 10 ** 9 + 7
cnt = [0] * (K + 1)
for x in range(1, K + 1):
  cnt[x] = pow(K // x , N , MOD)

for x in range(K, 0, -1):
  for i in range(2, (K // x) + 1):
    cnt[x] -= cnt[x * i]
  #被りを消さなきゃいけない
print(cnt)
ans = 0
for x in range(1, K + 1):
  ans += cnt[x] * x
print(ans % MOD)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
MOD = 10 ** 9 + 7
cnt = [0] * (K + 1)
for x in range(1, K + 1):
  cnt[x] = pow(K // x , N , MOD)
  #全数列のうち、xの約数を持つ数字が含まれている数列の数
for x in range(1, K + 1):
  for i in range(2, K // x):
    cnt[x] -= cnt[x * i]
  #被りを消さなきゃいけない
  
print(sum(cnt) % MOD)

Submission status: Wrong Answer

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

cnts=[0]*(k+1)

for x in reversed(range(1,k+1)):
    num= k//x

    c = num**n
    for j in range(2,num+1):
        c-= cnts[x*j]
    cnts[x]=c

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

Submission status: Wrong Answer

Solution code:
def sieve(n):
    res = list(range(n+10)) # nが小さい時よう
    res[0] = -1
    res[1] = -1
    i = 2
    while i*i<n:
        if res[i]<i:
            i += 1
            continue
        j = i*i
        while j<n:
            if res[j]==j:
                res[j] = i
            j += i
        i += 1
    return res

def mobius_divisor(a,primes): #aを約数メビウス
    n = len(a)
    for p in primes:
        for i in range(1,n):
            if i*p >= n: break
            a[i] -= a[p*i] 

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

pl = []
for i,p in enumerate(sieve(k)):
    if i==p:
        pl.append(p)

al = [0]*(k+1)
for x in range(1,k+1):
    al[x] = pow(k//x,n,mod)

mobius_divisor(al,pl)

res = 0
for i,c in enumerate(al):
    res += i*c
    res %= mod
print(res)

Submission status: Wrong Answer

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

    cnt = [0] * (K+1)
    for g in range(K,0,-1):
        cnt[g] = (K // g) ** N % mod
        gg = g * 2
        while gg <= K:
            cnt[g] -= cnt[gg]
            gg += g
    
    ans = 0
    for i in range(1,K+1):
        ans += cnt[i] * i % mod
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

    cnt = [0] * (K+1)
    for g in range(K,0,-1):
        cnt[g] = (K // g) ** N
        gg = g * 2
        while gg <= K:
            cnt[g] -= cnt[gg]
            gg += g
    
    ans = 0
    for i in range(1,K+1):
        ans += cnt[i] * i
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, K = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
dd = defaultdict(int)

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

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
p = int(10e9+7)
res = 0
d = [0]*K

for i in range(K, 0, -1):
    n = ((K//i)**N)%p

    for j in range(2, K//i+1):
        x = j*i
        n -= d[x-1]

    d[i-1] = n
    res += n*i
    res %= p

print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, K = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
dd = defaultdict(int)

ans = 0
for i in range(K, 0, -1):
    dd[i] = (K // i) ** N
    for temp in range(i * 2, K, i):
        dd[i] -= dd[temp]
    ans += (dd[i] * i) % mod

print(ans)

Submission status: Wrong Answer

Solution code:
import math

def pow(p,n):
    bin_n=bin(n)[2:][::-1]
    tmp=p;pn=1
    for i in range(len(bin_n)):
        if bin_n[i]=="1": pn=(pn*tmp)%mod
        tmp=tmp*tmp%mod
    return pn


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

ans=[0]*(k+1)
for i in range(k,0,-1):
    div=set()
    for x in range(1,int(i**0.5)+1):
        if i%x==0: div.add(x);div.add(i//x)
    ans[i]=pow(k//i,n)-sum([ans[j*i] for j in range(k//i,1,-1)])
    ans[i]%=mod
print(sum(ans[i]*i for i in range(k+1)))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
mod = 10**9+7
# 最大公約数がx(1 <= x <= k)な数列の数
num_gcd_k = [0]*(k+1)
num_gcd_k[k] = 1
ans = 0
for i in range(k-1,0,-1):
    # total = ((k // i)**n)%mod
    total = pow(k//i,n,mod)
    m = 2
    while i*m <= k:
        total -= num_gcd_k[i*m]
        m += 1
    num_gcd_k[i] = total
    ans += i*total
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
p = int(10e9+7)
res = 0
c = 0
d = [0]*K


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

    j = 2
    x = i*j
    while x <= K:
        n -= d[x-1]
        j += 1
        x = i*j

    d[i-1] = n
    res += n*i
    # res += xn*i
    res %= p

print(res)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
  return list(map(int,input().split()))
def m(): #複数文字
  return map(int,input().split())
def onem(): #Nとかの取得
  return int(input())
def s(x): #圧縮
  a = []
  if len(x) == 0:
    return []
  aa = x[0]
  su = 1
  for i in range(len(x)-1):
    if aa != x[i+1]:
      a.append([aa,su])
      aa = x[i+1]
      su = 1
    else:
      su += 1
  a.append([aa,su])
  return a
def jo(x): #listをスペースごとに分ける
  return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
  return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
  ll = 0
  rr = r
  while True:
    mid = (ll+rr)//2

  if rr == mid:
    return ll
  if (ここに評価入れる):
    rr = mid
  else:
    ll = mid+1
"""

n,k = m()

co = 0
on = pow(k,n,mod)
for i in range(k,0,-1):
  if i != 1:
    po = k // i
    on -= (pow(po,n,mod) - pow(po-1,n,mod)) % mod
    on %= mod
    #print((pow(po,n) - pow(po-1,n))% mod)
    co += i * (pow(po,n,mod) - pow(po-1,n,mod))
    co %= mod
  else:
    co += on
    co %= mod
print(co)

Submission status: Wrong Answer

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

ans=0
MOD=10**9+7

cnt=[0]*(K+1)
for x in reversed(range(1,K+1)):
    cnt_tmp = pow(K//x,N,MOD)#xの倍数のみで作れるlen=Nの数列の総数
    t=1
    while (t+1)*x<=K:
        t+=1
        cnt_tmp -= cnt[x*t] #cnt_tmpのうち,gcd=2x,3x...になるものを除く

    cnt[x]=cnt_tmp
    ans = x*cnt_tmp %MOD
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
p = int(10e9+7)
res = 0
c = 0
d = [0]*K

def mk_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(K, 0, -1):
    n = ((K//i)**N)
    xn = n - d[i-1]
    # divisors

    if i != 1:
        d[0] += xn
    for j in range(2, int(i**0.5)+1):
        if i % j == 0:
            d[j-1] += xn
            if j != i // j:
                d[i//j-1] += xn

    res += xn*i
    res %= p

print(res)

Submission status: Wrong Answer

Solution code:
import itertools
import math

n,k = map(int,input().split())
l = []
for i in range(1,k**n+1):
    l.append(i)
    
    
a = list(itertools.combinations(l, 3))
ans = 0
for i in range(len(a)):
    b = math.gcd( math.gcd(a[i][0],a[i][1]), a[i][2])
    ans += b
c = list(itertools.combinations(l, 2))

for i in range(len(c)):
    d = math.gcd(c[i][0], c[i][1])
    ans += d
ans = ans * 6 % (10**9 + 7)
e = sum(l)
print(ans+e)

Submission status: Wrong Answer

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

v = [0]*(k+1)
ans = 0
for i in range(k,0,-1):
    if v[i] == 0:
        v[i] = (k//i)**n-sum(v[i::i])
for i in range(k+1):
    ans += v[i]*i
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = list(map(int,input().split()))
x = 0
sum = 0
 
for y in range(k):
  x = k - y
  sum += ((k // x) ** n * x) % (10 ** 9 + 7)
  if k // x > 1:
    for z in range(1, k // x):
      sum -= ((k // ((z + 1) * x)) ** n * x) % (10 ** 9 + 7)
      
print(sum)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, k = list(map(int,input().split()))
x = 0
sum = 0

for y in range(k):
  x = k - y
  sum += (k // x) ** n * x
  if k // x > 1:
    for z in range(1, k // x):
      sum -= (k // ((z + 1) * x)) ** n * x
      
print(sum % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
n, k = list(map(int,input().split()))
x = 0
sum = 0

for y in range(k):
  x = k - y
  sum += (k // x) ** n
  if k // x > 1:
    for z in range(1, k // x):
      sum -= (k // ((z + 1) * x)) ** n
      
print(sum % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
n, k = list(map(int,input().split()))
x = 0
sum = 0

for y in range(k):
  x = k - y
  sum += (k // x) ** n
  if k // x > 1:
    for z in range(1, k // x):
      sum -= (k // (z + 1)) ** n
      
print(sum % (10 ** 9 + 7))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
[N,K] = [int(x) for x in input().split()]
l = [0 for i in range(K)]
for i in range(K):
    l[i] = int(K/(i+1))**N
    for j in range(1,int(K/(i+1))+1):
        l[i] -= l[(i+1)*j-1]
ans = 0
for i in range(K):
    ans += l[i]*(i+1)
print(ans)

Submission status: Wrong Answer

Solution code:
def gcd(x, y): 
    while(y): 
        x, y = y, x % y 
    return x 

sum = 0
n , k = map(int,input().split())
n = max(n,k)
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            sum += gcd(gcd(i,j),k)

print(sum%1000000007)

Submission status: Wrong Answer

Solution code:
mod=10**9+7
N,K=map(int,input().split())
Ans=[1 for k in range(K)]
c=K
for j in range(N):
    Ans[0]=Ans[0]*(K)%mod
for k in range(2,(K+1)//2+1):
    d=K//k
    if c==d:
        Ans[k-1]=Ans[k-2]
    else:
        for j in range(N):
            Ans[k-1]=Ans[k-1]*d%mod
        c=d
print(Ans)
for j in range(K,1,-1):
    for l in range(j//2,0,-1):
        if j%l==0:
            Ans[l-1]-=Ans[j-1]
for j in range(K):
    Ans[j]*=j+1
print(sum(Ans)%mod)

Submission status: Wrong Answer

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

    def __str__(self):
        return str(self.x)
    def __int__(self):
        return 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 __mod__(self, other):
        return (
            ModInt(
                other.x
            ) if isinstance(other, ModInt) else
            other
        )

    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))
        )
    
    def __iadd__(self,other):
        self.x += other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self

    def __isub__(self,other):
        self.x += ModInt(MOD - other.x) if isinstance(other, ModInt) else ModInt(MOD - other)
        return self

    def __imul__(self, other):
        self.x *= other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self
    
    def factorical(self,n):
        tmp = ModInt(1)
        for i in range(n):
            tmp *= (i+1)
        return tmp
    
    #m:int MOD
    def modinv(self,a,m=MOD):
        b = m
        u = 1
        v = 0
        while(b):
            t = a//b
            a -= t * b
            a,b = b,a
            u -= t * v
            u,v = v,u
        return ModInt(u)

    def comb(self,n,r):
        n = int(n)
        r = int(r)
        if r > n or n < 0 or r < 0:
            return 0
        m = n+1
        nterms = min(r, n-r)
        numerator = ModInt(1)
        denominator = ModInt(1)
        for j in range(1, nterms + 1):
            numerator *= m - j
            denominator *= j
        return numerator * self.modinv(denominator.x)


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

    ans = ModInt(0)
    gcd_equal_i = [0]*(K+1) #gcd(A) == i なるAの作り方がgcd_equal_i[i]個

    for D in range(K, 0, -1):
        num_of_mul = ModInt(K // D)
        tmp = num_of_mul**N

        i = 2
        while D*i <= K:
            tmp -= gcd_equal_i[D*i]
            i += 1
        
        gcd_equal_i[D] = tmp


    for i in range(K+1):
        ans += i*gcd_equal_i[i]

    print(ans)

Submission status: Wrong Answer

Solution code:
import itertools 
import math
from functools import reduce


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

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

if K<=2:
    a_list = [i for i in range(1,K+1)]
    comb_list = list(itertools.product(a_list, repeat=N))
    print(sum([gcd_list(x) for x in comb_list]))

else:
    a_list = [i for i in range(1,K+1)]
    comb_list = list(itertools.combinations_with_replacement(a_list, 3))
    test = sum([gcd_list(x) for x in comb_list])*3

    comb_list_dup = [[i, i, i] for i in a_list]
    duplica = sum([gcd_list(x) for x in comb_list_dup])*2

    comb_list_unique = list(itertools.combinations(a_list, 3))
    unique = sum([gcd_list(x) for x in comb_list_unique])*3
    print(test-duplica+unique)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 +7

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

ans = 0
gcd_equal_i = [0]*(K+1) #gcd(A) == i なるAの作り方がgcd_equal_i[i]個

for D in range(K, 0, -1):
    num_of_mul = K // D
    tmp = num_of_mul**3

    i = 2
    while D*i <= K:
        tmp -= gcd_equal_i[D*i]
        i += 1
    
    gcd_equal_i[D] = tmp
    ans += D*tmp
    ans %= MOD


print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
INF=10**9+7
baisu=[0]*(k+1)
D=[0]*(k+1)
ans=0
for d in range(1,k+1):
    baisu[d]=[d*i for i in range(2,k//d+1)]
    D[d]=pow(k//d,n,INF)

for d in range(k,0,-1):
    for b in baisu[d]:
        D[d]-=D[b]
for x in range(1,k+1):
    ans+=(D[x]*x)%INF
#print(baisu)
#print(D)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def f(n):
  if n == 1:
    return 1
  else:
    a = n
    m = n
    for i in range(2,math.floor(math.sqrt(m))+1):
      if m % i == 0:
        a = a*(i-1)//i
        while m % i == 0:
          m = m // i
    if m == n:
      return n-1
    else:
      return a
      
    
ans = 0  
for i in range(1,K+1):
  ans += (pow(K//i,N,mod)*f(i)) % mod

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): 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 LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
mod = 10**9+7

def main():
	n,k = MI()
	dp=[0]*(k+1)
	ans=0
	def g(x, n, mod):
		if n == 0:
			return 1
		K = 1
		while n > 1:
			if n % 2 != 0:
				K *= x
			x *= x%mod
			n //= 2
		return K * x

	for i in range(k,0,-1):
		dp[i]=g(k//i,n,mod)
		for j in range(i*2,k,i):
			dp[i]-=dp[j]
			dp[i]%=mod
		dp[i]=(dp[i]%mod+mod)%mod
		ans+=i*dp[i]%mod
	print(ans%mod)
if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

    ans += i*cnt_seq[i]
    #print('+',i*cnt_seq[i])
    #print(ans)

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

        ans %= MOD
#print(cnt_seq)
print(ans)