TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: 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.

Submission attempts (in order):
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)

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

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

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

Verdicts: Wrong Answer

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

Submission attempts (in order):



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)





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)


Verdicts: Wrong Answer

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

Submission attempts (in order):
n, k = map(int, input().split())
mod = 10**9+7

num_gcd_k = [0]*(k+1)
num_gcd_k[k] = 1
ans = 0
for i in range(k-1,0,-1):
    
    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)

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

num_gcd_k = [0]*(k+1)
num_gcd_k[k] = 1
ans = 0
for i in range(k,0,-1):
    
    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)

Verdicts: Wrong Answer

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

Submission attempts (in order):
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)

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

Verdicts: Runtime Error

Wrong Answer

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

Submission attempts (in order):
N, K = map(int, input().split())

MOD = 10 ** 9 + 7

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


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


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

MOD = 10 ** 9 + 7

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

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


Verdicts: Runtime Error

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

Submission attempts (in order):
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)
    t=1
    while (t+1)*x<=K:
        t+=1
        cnt_tmp -= cnt[x*t] 

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


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)
    t=1
    while (t+1)*x<=K:
        t+=1
        cnt_tmp -= cnt[x*t] 

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


Verdicts: Wrong Answer

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

Submission attempts (in order):
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)

n, k = (int(x) for x in input().split())
c = {} 
t = 0
MOD = 1000000007
for x in range(k, 0, -1):
    q = k // x
    c[x] = pow(q, n, MOD) - sum(c[x * y] for y in range(2, q + 1))
    t += c[x] * x
    t = t % MOD
print(t)

Verdicts: Wrong Answer

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

Submission attempts (in order):
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)

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]
  
ans = 0
for x in range(1, K + 1):
  ans += cnt[x] * x
print(ans % MOD)
  

Verdicts: Wrong Answer

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

Submission attempts (in order):
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)

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)


Verdicts: Wrong Answer

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

Submission attempts (in order):
N,K=list(map(int,input().split()))
l=[0]*(K+1)
ans=0
mod=10**9+7

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

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

for x in range(K,0,-1):
    l[x]=pow((K//x),N,mod)
    for y in range(2*x,K+1,x):
        l[x]-=l[y]
        l[x]=pow(l[x],1,mod)
    ans+=l[x]*x
    ans=pow(ans,1,mod)
print(ans)

Verdicts: Runtime Error

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

Submission attempts (in order):
M = 1000000007


def main(N=None, K=None):
    if not N or not K:
        N = int(input())
        K = int(input())
    ans = 0
    gcds = {}
    for X in range(K, 0, -1):
        gcds[X] = int(pow(K//X, N, M))
        n = 1
        while True:
            n += 1
            if n*X > K:
                break
            gcds[X] -= gcds[n*X]
        ans += gcds[X]*X
    ans %= M
    print(ans)
    return ans


if __name__ == "__main__":
    
    
    
    main()


M = 1000000007


def main(N=None, K=None):
    if not N or not K:
        N, K = map(int, input().split())
    ans = 0
    gcds = {}
    for X in range(K, 0, -1):
        gcds[X] = int(pow(K//X, N, M))
        n = 1
        while True:
            n += 1
            if n*X > K:
                break
            gcds[X] -= gcds[n*X]
        ans += gcds[X]*X
    ans %= M
    print(ans)
    return ans


if __name__ == "__main__":
    
    
    
    main()


Verdicts: Runtime Error

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

Submission attempts (in order):
mod=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=K//i
    totalNumber=multipleNumber**N%mod
    minus=range(2*i,K+1,i)
    for j in minus:
        totalNumber-=gcd[j]
        totalNumber%=mod
    gcd[i]=totalNumber
    ans+=i*gcd[i]
print(ans%a)

import math
a=10**9+7
N,K=map(int,input().split())
gcd=[0]*(K+1)
ans=0
multipleNumber
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)

mod=10**9+7
N,K=map(int,input().split())
d=[0]*(K+1)
ans=0
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+=d[i]*i
    ans%=mod
print(ans)

Verdicts: Runtime Error

Runtime Error

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

Submission attempts (in order):
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)


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


Verdicts: Runtime Error

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

Submission attempts (in order):

MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [pow(k, n, MOD) for i in range(1, k+1)]

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



MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [0] * (k + 1)

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

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


Verdicts: Runtime Error

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

Submission attempts (in order):
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) 

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) 

Verdicts: Runtime Error

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

Submission attempts (in order):
import math

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

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

def culc(x):
    f=K//i
    r=K-f
    if r==1:
        return (f*(N-1))%P
    else:
        y=pow(r,N-1)-1
        return ((f*y)//(r-1))%P

for j in range(1,K):
    L[0]+=culc(j+1)

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

print(ans)



import math

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

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

def culc(x):
    f=K//i
    r=K-f
    if r==1:
        return (f*(N-1))%P
    else:
        y=pow(r,N-1)-1
        return ((f*y)//(r-1))%P

for j in range(1,N):
    L[0]+=culc(j+1)

ans=0
for k in range(N):
    ans+=((k+1)*L[k])%P

print(ans)



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

L=[0]*(K+1)
for i in range(1,K+1)[::-1]:
    minus=0
    count=2
    while True:
        if count*i<=K:
            minus+=L[count*i]
            minus=minus%P
            count+=1
        else:
            break

    L[i]=(pow(K//i,N,P)-minus)%P

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

print(ans)

Verdicts: Runtime Error

Wrong Answer

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

Submission attempts (in order):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
             
    return divisors

n, k = map(int, input().split())
mod = 1000000007
l = [1 for i in range(k+1)]
for i in range(k):
  for j in range(len(make_divisors(k-i))):
    l[make_divisors(k-i)[j]] += n*l[k-i]
ans = 0
for i in range(k+1):
  ans += l[i]*i
  ans %= mod
print(ans)

n, k = map(int, input().split())
l = [0 for i in range(k + 1)]
ans = 0
mod = 1000000007
for i in range(k, 0, -1):
    l[i] = pow(k // i, n, mod)
    tmp = 2 * i
    while tmp <= k:
        l[i] -= l[tmp]
        tmp += i
for i in range(k + 1):
    ans += i * l[i]
    ans %= mod
print(ans)

Verdicts: Wrong Answer

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

Submission attempts (in order):
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

import numpy as np
M = int(10**9)+7
n,k = [int(c) for c in input().split()]
nums = [0]*(k+1)
nums = np.zeros((k+1), dtype=int)
for i in range(k, 0, -1):
    tmp = (pow(k // i, n, M)
    tmp -= nums[(2*i)::i].sum()
    nums[i] += tmp
    

print((np.arange(k+1) * nums).sum()%M)

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

import numpy as np
M = int(10**9)+7
n,k = [int(c) for c in input().split()]
nums = [0]*(k+1)
nums = np.zeros((k+1), dtype=int)
for i in range(k, 0, -1):
    tmp = pow(k // i, n, M)
    tmp -= nums[(2*i)::i].sum()
    nums[i] += tmp
    

print((np.arange(k+1) * nums).sum()%M)

Verdicts: Runtime Error

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

Submission attempts (in order):
import math
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans+=math.gcd(i,math.gcd(j,k)) 
print(ans)           



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

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

Verdicts: Runtime Error

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

Submission attempts (in order):
n=int(input())
s=input()

remain = [[0,0,0]]
for i in range(n):
    r, g, b = remain[-1]
    if s[-i-1] == "R":
        r = r+1
    elif s[-i-1] == "G":
        g = g + 1
    elif s[-i-1] == "B":
        b = b + 1

    remain.append([r,g,b])

total = 0
for i in range(n-2):
    if s[i] == "R":
        for j in range(i+1, n):
            if s[j] == "G":
                total += remain[-j-1][2]
                if i+((j-i)*2) < n:
                    if s[i+((j-i)*2)]=="B":
                        total -= 1
            elif s[j] == "B":
                total += remain[-j-1][1]
                if i+((j-i)*2) < n:
                    if s[i+((j-i)*2)]=="G":
                        total -= 1
    elif s[i] == "G":
        for j in range(i+1, n):
            if s[j] == "B":
                total += remain[-j-1][0]
                if i+((j-i)*2) < n:
                    if s[i+((j-i)*2)]=="R":
                        total -= 1
            elif s[j] == "R":
                total += remain[-j-1][2]
                if i+((j-i)*2) < n:
                    if s[i+((j-i)*2)]=="B":
                        total -= 1
    elif s[i] == "B":
        for j in range(i+1, n):

            if s[j] == "R":
                total += remain[-j-1][1]
                if i+((j-i)*2) < n:
                    if s[i+((j-i)*2)]=="G":
                        total -= 1
            elif s[j] == "G":
                total += remain[-j-1][0]
                if i+((j-i)*2) < n:
                    if s[i+((j-i)*2)]=="R":
                        total -= 1
print(total)

n,k = map(int,input().split())
gcds = []


def power_func(a,n,p):
    bi=str(format(n,"b"))
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res

mod = 10**9+7
for i in range(k):
    div = k//(k-i)
    count = power_func(div,n, mod)
    for j in range(1,div):
        count = count - gcds[k-((k-i)*(j+1))]
    gcds.append(count)

total = 0

for i in range(k):
    total = (total + (gcds[i]*(k-i)%mod))%mod
print(total)

Verdicts: Runtime Error

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

Submission attempts (in order):
N,K=map(int, input().split())
import math
cnt=(K**N)%(10**9+7)

print(cnt)
for i in range(2,K+1):
  a=K//i
  cnt+=((a**N-2)*(i-1))%(10**9+7)
print(cnt)

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

Verdicts: Wrong Answer

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

Submission attempts (in order):
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()

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
			K %= 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+1,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()

Verdicts: Wrong Answer

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

Submission attempts (in order):
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)

#from line_profiler import LineProfiler
 
N, K = map(int, input().split())
mod = 10**9 + 7
def main():
  b = N
  blis = []
  c = 0
  while b >0:
    if b & 1 == 1:
      blis.append(c)
    c += 1
    b >>= 1


  def modpow(a, blis= blis, c = c):
    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):
    x = 1*fact_count[k]
    cc = modpow(x)
    j = 2*k
    l = 2
    while(j<=K):
      cc -= count[j]
      l += 1
      j = k*l
    count[k] = cc
    cc = cc*k%mod
    ans += cc
    ans %= mod
  print(ans)
if __name__ == '__main__':
  main()
#prof = LineProfiler()
#prof.add_function(main)

#prof.print_stats()


Verdicts: Wrong Answer

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

Submission attempts (in order):
n = input()
k = int(input())
dp = [[[0 for i in range(len(n)+1)] for i in range(2)] for i in range(len(n)+1)]
dp[0][0][0] = 1
for a in range(len(n)):
  for b in range(2):
    for c in range(len(n)):
      for i in range(10):
        if b ==1:
          if i != 0:
            dp[a+1][1][c+1] += dp[a][1][c]
          else:
            dp[a+1][1][c] += dp[a][1][c]
        else:
          if int(n[a]) > i and i ==0:
            dp[a+1][1][c] += dp[a][0][c]
          if int(n[a]) > i and i != 0:
            dp[a+1][1][c+1] += dp[a][0][c]
          if int(n[a]) == i and i ==0:
            dp[a+1][0][c] += dp[a][0][c]
          if int(n[a]) == i and i !=0:
            dp[a+1][0][c+1] += dp[a][0][c]
if len(n) == 1:
	print(int(n))  
else:
  print(dp[-1][0][k] + dp[-1][1][k])


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

Verdicts: Runtime Error

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

Submission attempts (in order):
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;



ll n,k,mod=1e9+7,ans=0;

ll fastMod(ll a,ll b){
    ll res=1;
    while(b>0){
        if(b&1)res=(res*a)%mod;
        b/=2;
        a=(a*a)%mod;
    }
    return res;
}

void solve(){    
    cin>>n>>k;
    vector<ll> v(k+1);
    for(int i=k;i>0;i--){
        v[i]=fastMod(k/i,n);
        for(int j=2*i;j<=k;j+=i){
            v[i]=(v[i]-v[j]+mod)%mod;
        }
    }
    for(int i=1;i<=k;i++){
        ll val=(v[i]*i)%mod;
        ans=(ans+val)%mod;
    }
    cout<<ans%mod;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}


n,k=[int(x) for x in input().split()]
ans=0
l=[0]*(k+1)
i=k
mod=1000000007
while i>0:
    l[i]=pow(k//i,n,mod)
    j=2*i
    while j<=k:
        l[i]=(l[i]-l[j]+mod)%mod
        j+=i
    i-=1
for i in range(1,k+1):
    ans+=(l[i]*i)%mod
print(ans%mod)


Verdicts: Runtime Error

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

Submission attempts (in order):
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;




#define INF 2e9
#define ALL(v) v.begin(), v.end()

int k;
int memo[200+1][200+1];
ll N=1000000000+7;

int gcd(int x,int y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}

int main(){
    cin>>k;
    int ans=0;
    for(int a=1;a<=k;a++){
        for(int b=1;b<=k;b++){
            for(int c=1;c<=k;c++){
                ans+=gcd(gcd(a,b),c)%N;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

n,k=map(int,input().split())
INF=10**9+7
baisu= [[] for _ in [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]
    D[d]%=INF
for i,x in enumerate(D):
    
    ans=(ans+i*x)%INF
    

#print(D)
print(ans)

Verdicts: Runtime Error

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

Submission attempts (in order):
n, k = list(map(int, input().split()))
l = [0 for i in range(k)]
ans = 0
M = 10**9 + 7

def dev(n):
    dl = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            dl.append(i)
            if i != n // i:
                dl.append(n//i)
    dl.sort()
    return dl

for i in range(k, 0, -1):
    a=k//i
    b=a**n
    l[i-1] += b
    d=dev(i)
    for m in d:
        if m != i:
            l[m-1] -= l[i-1]
    print(i, l)

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

print(ans%M)


n, k = list(map(int, input().split()))
l = [0 for i in range(k)]
ans = 0
M = 10**9 + 7


#     dl = []


#             dl.append(i)

#                 dl.append(n//i)
#     dl.sort()


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

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

print(ans%M)


Verdicts: Wrong Answer

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

Submission attempts (in order):
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)

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)

Verdicts: Wrong Answer

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

Submission attempts (in order):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    a0, a1, a2, b0, b1, b2 = A[0], 0, 0, A[1], 0, 0
    for a in A[2:]:
        a0, a1, a2, b0, b1, b2 = (
                b0,
                max(b1, a0),
                max(b2, a1),
                a0 + a,
                a1 + a,
                a2 + a)

    if N & 1:
        return max(b2, a1)
    else:
        return max(a0, b1)


print(main())


def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    r = 0
    D = [0] * (K + 1)
    for i in reversed(range(1, K + 1)):
        D[i] = pow(K // i, N, mod) - sum(D[::i])
    return sum(i * j for i, j in enumerate(D)) % mod

print(main())


Verdicts: Runtime Error

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

Submission attempts (in order):
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)  

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)  

Verdicts: Runtime Error

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

Submission attempts (in order):
n,k = map(int,input().split())
mod = 10**9 + 7


def pow_mod(x, n, mod):
    if n > 1:
        return pow_mod(pow(x,2) % mod, n//2, mod) * pow(x, n%2) % mod
    else:
        return x


pow_n = [-1] * (k+1)
for i in range(1,k+1):
    if pow_n[k//i] == -1:
        pow_n[k//i] = pow_mod(k//i, n, mod)

ans = 0
c = [0] * (k+1)
for i in range(k, 0, -1):
    count = pow_n[k//i]
    for j in range(2, k//i+1):
        if j > k//i:
            break
        count -= c[i]
        count %= mod
    c[i] = count
    ans += count * i
    ans %= mod
print(ans)


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


def pow_mod(x, n, mod):
    if n > 1:
        return pow_mod(pow(x,2) % mod, n//2, mod) * pow(x, n%2) % mod
    else:
        return x


pow_n = [-1] * (k+1)
for i in range(1,k+1):
    if pow_n[k//i] == -1:
        pow_n[k//i] = pow_mod(k//i, n, mod)

ans = 0
c = [0] * (k+1)
for i in range(k, 0, -1):
    count = pow_n[k//i]
    for j in range(2, k//i+1):
        count -= c[i*j]
        count %= mod
    c[i] = count
    ans += count * i
    ans %= mod
print(ans)


Verdicts: Wrong Answer

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

Submission attempts (in order):
import math
N, K = map(int,input().split())
a = 0
for i in range(1, K):
    p = (K-i+1)**N - (K-i)**N
    q = (math.floor(K/i))**N - ((math.floor(K/i))-1)**N
    a += (i-1)*q + p
print(a%1000000007)


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

Verdicts: Wrong Answer

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

Submission attempts (in order):
n,k=map(int,input().split())
dp=[0]*(k+1)
mod=int(1e9+7)
for i in range(k,0,-1):
    sm=0
    for j in range(2*i,k+1,i):
        sm=(sm+dp[j])%mod
    dp[i]=pow(k//i,n,mod)-sm

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


n,k=map(int,input().split())
dp=[0]*(k+1)
mod=int(1e9+7)
for i in range(k,0,-1):
    sm=0
    for j in range(2*i,k+1,i):
        sm=(sm+dp[j])%mod
    dp[i]=(pow(k//i,n,mod)-sm)%mod

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


Verdicts: Runtime Error

Accepted
Problem: Given is an integer sequence A_1, ..., A_N of length N.  We will choose exactly \left\lfloor \frac{N}{2} \right\rfloor elements from this sequence so that no two adjacent elements are chosen.  Find the maximum possible sum of the chosen elements.  Here \lfloor x \rfloor denotes the greatest integer not greater than x.

Submission attempts (in order):
n = int(input())
a = [int(num) for num in input().split()]
dp = [[0,0,0] for _ in range(n//2+1)]

#dp[0] = [a[0],a[1],a[2]]

for i in range(n//2):
    dp[i+1][0] = dp[i][0] + a[i*2]
    dp[i+1][1] = max(dp[i][1],dp[i][0]) + a[i*2+1]
    if n % 2 == 1:
        dp[i+1][2] = max(dp[i][2],dp[i][1],dp[i][0]) + a[i*2+2]
print(dp)
print(max(dp[-1]))



n = int(input())
a = [int(num) for num in input().split()]
dp = [[0,0,0] for _ in range(n//2+1)]

#dp[0] = [a[0],a[1],a[2]]

for i in range(n//2):
    dp[i+1][0] = dp[i][0] + a[i*2]
    dp[i+1][1] = max(dp[i][1],dp[i][0]) + a[i*2+1]
    if n % 2 == 1:
        dp[i+1][2] = max(dp[i][2],dp[i][1],dp[i][0]) + a[i*2+2]
#print(dp)
if n% 2 == 1:
    print(max(dp[-1]))
else:
    print(max(dp[-1][:2]))

Verdicts: Wrong Answer

Accepted
Problem: Given is an integer sequence A_1, ..., A_N of length N.  We will choose exactly \left\lfloor \frac{N}{2} \right\rfloor elements from this sequence so that no two adjacent elements are chosen.  Find the maximum possible sum of the chosen elements.  Here \lfloor x \rfloor denotes the greatest integer not greater than x.

Submission attempts (in order):
N = int(input())
As = list(map(int, input().split()))

INF = 10 ** 15
dp = [[-INF] * N for _ in range(3)]
dp[0][0] = As[0]
dp[1][0] = As[0]
dp[0][1] = As[0]
dp[1][1] = As[1]

if N % 2 == 0:
    for i in range(2, N):
        dp[0][i] = dp[0][i-2] + As[i]
        dp[1][i] = max(dp[0][i-1], dp[1][i-2] + As[i])
else:
    for i in range(2, N):
        dp[0][i] = dp[0][i-2] + As[i]
        dp[1][i] = max(dp[0][i-1], dp[1][i-2] + As[i])
        dp[2][i] = max(dp[1][i-1], dp[2][i-2] + As[i])

print(dp)
print(max(dp[0][N-1], dp[1][N-1], dp[2][N-1]))



INF = 10 ** 15

N = int(input())
As = list(map(int, input().split()))
As.append(-INF)

INF = 10 ** 15
dp = [[-INF] * (N//2) for _ in range(3)]
dp[0][0] = As[0]
dp[1][0] = As[1]
dp[2][0] = As[2]

for i in range(1, N//2):
    dp[0][i] = dp[0][i-1] + As[2*i]
    dp[1][i] = max(dp[0][i-1], dp[1][i-1]) + As[2*i+1]
    dp[2][i] = max(dp[0][i-1], dp[1][i-1], dp[2][i-1]) + As[2*i+2]

if N % 2 == 0:
    print(max(dp[0][-1], dp[1][-1]))
else:
    print(max(dp[0][-1], dp[1][-1], dp[2][-1]))



Verdicts: Wrong Answer

Accepted
Problem: Given is an integer sequence A_1, ..., A_N of length N.  We will choose exactly \left\lfloor \frac{N}{2} \right\rfloor elements from this sequence so that no two adjacent elements are chosen.  Find the maximum possible sum of the chosen elements.  Here \lfloor x \rfloor denotes the greatest integer not greater than x.

Submission attempts (in order):

n = int(input())
a_list = list(map(int,input().split()))

if n % 2 == 0: 
    dp = [[-float('inf') for _ in range(n)] for __ in range(2)]
    dp[1][-1] = a_list[-1]

    for j in reversed(range(2)):
        for i in reversed(range(n)):
            if j == 2 and i >= n-2:
                pass
            elif j == 2:
                dp[j][i] = dp[j][i+2] + a_list[i]
            elif i == n-2:
                dp[j][i] = dp[j+1][i+1]
            elif i > n-2:
                pass
            else:
                dp[j][i] = max(dp[j+1][i+1],dp[j][i+2] + a_list[i])
    print(dp[0][0])
else: 
    dp = [[-float('inf') for _ in range(n)] for __ in range(3)]
    dp[2][-1] = a_list[-1]

    for j in reversed(range(3)):
        for i in reversed(range(n)):
            if j == 2 and i >= n-2:
                pass
            elif j == 2:
                dp[j][i] = dp[j][i+2] + a_list[i]
            elif i == n-2:
                dp[j][i] = dp[j+1][i+1]
            elif i > n-2:
                pass
            else:
                dp[j][i] = max(dp[j+1][i+1],dp[j][i+2] + a_list[i])
    print(dp[0][0])


n = int(input())
a_list = list(map(int,input().split()))

if n == 2 or n == 3:
    print(max(a_list))
elif n % 2 == 0: 
    dp = [[-float('inf') for _ in range(n)] for __ in range(2)]
    dp[1][-1] = a_list[-1]

    for j in reversed(range(2)):
        for i in reversed(range(n)):
            if j == 1 and i >= n-2:
                pass
            elif j == 1:
                dp[j][i] = dp[j][i+2] + a_list[i]
            elif i == n-2:
                dp[j][i] = dp[j+1][i+1]
            elif i > n-2:
                pass
            else:
                dp[j][i] = max(dp[j+1][i+1],dp[j][i+2] + a_list[i])
    print(dp[0][0])
else: 
    dp = [[-float('inf') for _ in range(n)] for __ in range(3)]
    dp[2][-1] = a_list[-1]

    for j in reversed(range(3)):
        for i in reversed(range(n)):
            if j == 2 and i >= n-2:
                pass
            elif j == 2:
                dp[j][i] = dp[j][i+2] + a_list[i]
            elif i == n-2:
                dp[j][i] = dp[j+1][i+1]
            elif i > n-2:
                pass
            else:
                dp[j][i] = max(dp[j+1][i+1],dp[j][i+2] + a_list[i])
    print(dp[0][0])


Verdicts: Runtime Error

Accepted
Problem: Given is an integer sequence A_1, ..., A_N of length N.  We will choose exactly \left\lfloor \frac{N}{2} \right\rfloor elements from this sequence so that no two adjacent elements are chosen.  Find the maximum possible sum of the chosen elements.  Here \lfloor x \rfloor denotes the greatest integer not greater than x.

Submission attempts (in order):
import sys

sys.setrecursionlimit(2*1000000)

N = int(input())
A = list(map(int, input().split(" ")))



def dp(i, j):
    if i >= N:
        return (-1*1000000000)
    if (N//2)-j < (i-1)//2:
        return (-1*1000000000)
    if j == 1:
        return A[i]
	else:
        temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
        dp_dict[(i, j)] = temp
        return temp


select = N//2
if select == 1:
    print(max(A))
else:
    print(dp(0, select))

N = int(input())
A = list(map(int, input().split(" ")))

dp_dict = {}


def dp(i, j):
    print(i, j)
    if i >= N:
        return (-1*10e+9)-1
    if j == 1:
        return A[i]
    if (i, j) in dp_dict:
        return dp_dict[(i, j)]
    else:
        temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
        dp_dict[(i, j)] = temp
        return temp


print(dp(0, (N//2)))

import sys

sys.setrecursionlimit(2*1000000)

N = int(input())
A = list(map(int, input().split(" ")))

dp_dict = {}


def dp(i, j):
    #print(i, j)
    if i >= N:
        return (-1*1000000000)
    if (N//2)-j < (i)//2:
        print(i, j)
        return (-1*1000000000)
    if j == 1:
        return A[i]
    if (i, j) in dp_dict:
        return dp_dict[(i, j)]
    else:
        temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
        dp_dict[(i, j)] = temp
        return temp


select = N//2
if select == 1:
    print(max(A))
else:
    print(dp(0, select))

N = int(input())
A = [0]+list(map(int, input().split(" ")))

dp_list = [{0, 0}, {0: 0, 1: A[1]}, {0: 0, 1: A[1] if A[1] > A[2] else A[2]}]

for i in range(3, N+1):
    b = (i-1)//2
    f = (i+1)//2
    dp_list.append({})
    for j in range(b, f+1):
        if j in dp_list[i-1]:
            dp_list[i][j] = dp_list[i-2][j-1]+A[i] if dp_list[i -
                                                              2][j-1]+A[i] > dp_list[i-1][j] else dp_list[i-1][j]
        else:
            dp_list[i][j] = dp_list[i-2][j-1]+A[i]

print(dp_list[-1][N//2])

Verdicts: Runtime Error

Runtime Error

Wrong Answer

Accepted