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: Runtime Error

Solution code:
def resolve():
        n = int(input())
        s = input()
        r = [0] * n
        g = [0] * n
        b = [0] * n
        for i in range(n):
            if s[i] == "R":
                r[i] = 1
            elif s[i] == "G":
                g[i] = 1
            else:
                b[i] = 1
        ans = 0
        a = [r, g, b]
        for i in range(n):
            if a[0][i] == 1:
                for j in range(i + 1, n):
                    if a[1][j] == 1:
                        ans += sum(a[2][j + 1:n])
        a = [r, b, g]
        for i in range(n):
            if a[0][i] == 1:
                for j in range(i + 1, n):
                    if a[1][j] == 1:
                        ans += sum(a[2][j + 1:n])
        a = [g, r, b]
        for i in range(n):
            if a[0][i] == 1:
                for j in range(i + 1, n):
                    if a[1][j] == 1:
                        ans += sum(a[2][j + 1:n])
        a = [g, b, r]
        for i in range(n):
            if a[0][i] == 1:
                for j in range(i + 1, n):
                    if a[1][j] == 1:
                        ans += sum(a[2][j + 1:n])

        a = [b, r, g]
        for i in range(n):
            if a[0][i] == 1:
                for j in range(i + 1, n):
                    if a[1][j] == 1:
                        ans += sum(a[2][j + 1:n])

        a = [b, g, r]
        for i in range(n):
            if a[0][i] == 1:
                for j in range(i + 1, n):
                    if a[1][j] == 1:
                        ans += sum(a[2][j + 1:n])

        for i in range(1, n // 2+1):
            j = 0
            while j + 2 * i <= n - 1:
                if {s[j], s[j + i], s[j + 2 * i]} == {"R", "G", "B"}:
                    ans -= 1
                j += 1
        print(ans)
resolve()

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
import itertools
import collections
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)[0]

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

ls = list(range(1, k+1))
ans = 0
n_fact = math.factorial(n)
for v in itertools.combinations_with_replacement(ls, n):
  gcd_val = gcd(v)
  c = list(dict(collections.Counter(v)).values())
  c = [math.factorial(x) for x in c]
  count = int(n_fact / reduce(lambda a, b: a*b, c))
  ans += gcd_val * count
  print(gcd_val * count)
  
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

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

is_prime = np.zeros(K + 1, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3, K + 1, 2):
    if p * p >= K:
        break
    if is_prime[p]:
        is_prime[p * p:: p + p] = 0
primes = np.where(is_prime)[0]


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

for p in primes.tolist():
    for i in range(K // p + 1):
        A[i] -= A[i * p]

answer = sum(i * x for i, x in enumerate(A))
print(answer % MOD)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
import itertools
import collections
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)[0]


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

ls = list(range(1, k+1))
ans = 0
n_fact = math.factorial(n)
for v in itertools.combinations_with_replacement(ls, n):
  gcd_val = gcd(v)
  c = list(dict(collections.Counter(v)).values())
  c = [math.factorial(x) for x in c]
  count = int(n_fact / reduce(lambda a, b: a*b, c))
  ans += gcd_val * count
  
print(ans%10**9+7)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

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

is_prime = np.zeros(K + 1, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3, K + 1, 2):
    if p * p >= K:
        break
    if is_prime[p]:
        is_prime[p * p:: p + p] = 0
primes = np.where(is_prime)[0]


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

for p in primes.tolist():
    for i in range(N // p + 1):
        A[i] -= A[i * p]

answer = sum(i * x for i, x in enumerate(A))
print(answer % MOD)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


# nの約数列挙
def divisor(n):
    ans = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ans.append(i)
            if i**2 == n:
                continue
            ans.append(n // i)
    return ans  # sortされていない


MOD = 10 ** 9 + 7

ans = 0
num = 0
CNT = [0] * (K+1)
for i in range(K, 1, -1):
    n = K // i
    c = pow(n, N, MOD)

    c -= CNT[i]

    num += c

    f = divisor(i)
    for n in f:
        CNT[n] += c

    ans += c * i
    ans %= MOD


al = pow(K, N, MOD)
ans += al - num
ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
def fibo(N,K):
    if K == 1:
        return 1
    else:
        return ( K + int( (N**K-N**(K-1)) +1)  * fibo(N,K-1) ) % 1000000007
      
N,K=map(int,input().split())

print(fibo(N,K))

Submission status: Runtime Error

Solution code:
import math

summ=0

def count(last,gcd_arr,same,length,k,n):
    global summ
    if length==n:
        coeff=math.factorial(n)/math.factorial(same)
        summ+=coeff*gcd_arr%(10**9+7)
        return
    for i in range(last,k):
        if i==last:
            if same==0:
                count(i, math.gcd(gcd_arr, i), 2, length + 1, k, n)
            else:
                count(i,math.gcd(gcd_arr,i),same+1,length+1,k,n)
        else:
            count(i,math.gcd(gcd_arr,i),same,length+1,k,n)

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

for i in range(1,k+1):
    count(i,i,0,1,k+1,n)

print(int(summ))

Submission status: Runtime Error

Solution code:
b = int(input())
if 7 in str(b):
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = str(input())
r = []
g = []
b = []
ra = r.append
ga = g.append
ba = b.append
for i in range(n):
  if s[i] == "R":
    ra(i)
  elif s[i] == "G":
    ga(i)
  else:
    ba(i)
c = len(r)*len(g)*len(b)
for ri in r:
  for gi in g:
    for bi in b:
      if 3*(max(ri,gi,bi)+min(ri,gi,bi)) == 2*(ri+gi+bi):
        c -= 1
print(c)

Submission status: Runtime Error

Solution code:
n = int(input())
#h  = list(map(int, input().split()))
#h, w = list(map(int, input().split()))


s = input()
count = 0
for i in range(n):
    for j in range(i+1, n):
        if s[i]!=s[j]:    
            for k in range(j+1, n):
                if j-i!=k-j:
                    if s[i]!=s[k] and s[j]!=s[k]:
                        count += 1

print(count)

Submission status: Runtime Error

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

k = int(input())

from itertools import product
per1 = product((list(range(1, k + 1))), repeat=3)
all_list = list(per1)
summary = 0

for now in all_list:
  num1 = now[0]
  num2 = now[1]
  gcd = find_gcd(num1, num2)
  for i in range(2, len(now)):
    if gcd == 1:
      break
    gcd = find_gcd(gcd, now[i])
    if gcd == 1:
      break
  # print(now, gcd)
  summary += gcd

print(summary)