Problem:


Score : 300 points

Problem Statement

You are given integers N and K. Find the number of triples (a,b,c) of positive integers not greater than N such that a+b,b+c and c+a are all multiples of K.
The order of a,b,c does matter, and some of them can be the same.

Constraints

1 \leq N,K \leq 2\times 10^5

N and K are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

Print the number of triples (a,b,c) of positive integers not greater than N such that a+b,b+c and c+a are all multiples of K.

Sample Input 1

3 2

Sample Output 1

9

(1,1,1),(1,1,3),(1,3,1),(1,3,3),(2,2,2),(3,1,1),(3,1,3),(3,3,1) and (3,3,3) satisfy the condition.

Sample Input 2

5 3

Sample Output 2

1

Sample Input 3

31415 9265

Sample Output 3

27

Sample Input 4

35897 932

Sample Output 4

114191



Sample input:
3 2


Sample output:
9

Submission status: Runtime Error

Solution code:
mod = 998244353
rng = 4100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
def homo(n,k):
  if n<0 or k<=0:
    return 0
  else:
    return cmb(n+k-1,k-1)
k,n = map(int,input().split())
if k%2 == 0:
  flg = 0
else:
  flg = 1
ans = []
for i in range(3,k+2,2):
  ic = (i-1)//2
  anstmp = 0
  for j in range(ic+1):
    t = homo(n-j,(k-ic*2+j))*cmb(ic,j)*pow(2,j,mod)
    anstmp = (anstmp+t)%mod
  ans.append(anstmp)
  ans.append(anstmp)
if flg:
  anstmp = 0
  for j in range(1,k//2+1):
    t = (homo(n-j,j)+homo(n-j-1,j))*cmb(k//2,j)*pow(2,j,mod)
    anstmp = (anstmp+t)%mod
  ans.append(anstmp)
ans2 = ans[:-1]
ans2 = ans2[::-1]
print(*ans,*ans2,sep="\n")

Submission status: Runtime Error

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

# Kが偶数の場合, 全てKの倍数または全てK//2に倍数の両方考える必要あり
num = [0]*(K)  # 1以上N以下の整数で余りが0~K-1の個数をカウントする
for i in range(1, N+1):
    num[i % K] += 1  # i % K の取りうる値は0~K-1

ans = 0
for a in range(K+1):  # aに関して全探索を行う
    b = (K-a) % K
    c = (K-a) % K
    if (b + c) % K == 0:
        ans += num[a] * num[b] * num[c]

print(ans)

Submission status: Runtime Error

Solution code:
# 2019/09/10
# かんにんぐ

n,k=map(int,input().split())
cnt=0
num=[0]*(n+1)
for i in range(1,n+1):
    num[i%k]+=1

for a in range(k):
    b=(k-a)%k
    c=(k-a)%k
    if (b+c)%k:continue
    cnt+=num[a]*num[b]*num[c]
    
print(cnt)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
c=0
if K%2==0:
    d=K//2
else:
    print(N//K**3)

for i in range(d,N+1,d):
    for j in range(d,N+1,d):
        for k in range(d,N+1,d):
            if (i+j)%K==0 and (j+k)%K==0 and (k+i)%K==0:
                c+=1
print(c)

Submission status: Runtime Error

Solution code:
def base3(K):
    tmp=K
    S=""
    while(True):
        S=str(tmp%3)+S
        tmp=tmp//3
        if tmp==0:
            break
    return S
L=int(input())
T=base3(L)[::-1]
N=len(T)
A=[]
for i in range(N-1):
    tmp=3**i
    for k in range(3):
        A.append((i+1,i+2,k*tmp))
bef=0
for i in range(N)[::-1]:
    tmp=3**i
    for k in range(int(T[i])):
        A.append((i+1,N+1,bef+k*tmp))
    bef+=int(T[i])*tmp
print(N+1,len(A))
for p in A:
    print(p[0],p[1],p[2])ans=(n//k)**3

Submission status: Runtime Error

Solution code:
    def base3(K):
        tmp=K
        S=""
        while(True):
            S=str(tmp%3)+S
            tmp=tmp//3
            if tmp==0:
                break
        return S
    L=int(input())
    T=base3(L)[::-1]
    N=len(T)
    A=[]
    for i in range(N-1):
        tmp=3**i
        for k in range(3):
            A.append((i+1,i+2,k*tmp))
    bef=0
    for i in range(N)[::-1]:
        tmp=3**i
        for k in range(int(T[i])):
            A.append((i+1,N+1,bef+k*tmp))
        bef+=int(T[i])*tmp
    print(N+1,len(A))
    for p in A:
        print(p[0],p[1],p[2])

Submission status: Runtime Error

Solution code:
n,k=map(int,input())
if k%2:
  print((n//k)**3)
else:
  l=k//2
  if l%2:
    print(((n+l)//k)**3)
  else:
    print(((n+l)//k)**3 + (n//k)**3)

Submission status: Runtime Error

Solution code:
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N =  sc.nextInt();
    int K =  sc.nextInt();
    long ans = 0;
    for(int i=1;i<=N;i++){
      int ak = i%K;
      int tmp = K-ak;
      int cnt = (N-tmp)/K;
      cnt++;
      if ((tmp+tmp)%K == 0){
       ans += cnt*cnt;
      }
    }
    System.out.println(ans);
    
  }
}

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

# K+1 - x でうつす -> i と 2K+2-i は同じ

MOD = 998244353
U = 10000
fact = [1] * (U+1)
fact_inv = [1] * (U+1)
for n in range(1,U+1):
    fact[n] = fact[n-1] * n % MOD
fact_inv[n] = pow(fact[n], MOD-2, MOD)
for n in range(U,0,-1):
    fact_inv[n-1] = fact_inv[n] * n % MOD

def comb(n,k):
    if not (0 <= k <= n):
        return 0
    return fact[n] * fact_inv[k] * fact_inv[n-k] % MOD

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

def F(x,y,N):
    n = min(x, N)
    return sum(comb(x,i) * pow(2,i,MOD) * comb(N+y-1,i+y-1) for i in range(n+1)) % MOD

answer = []
for S in range(2,K+2):
    if S & 1:
        x = F((S-1)//2, K - S + 1, N)
    else:
        x = F((S-1)//2, K - S + 1, N) + F((S-1)//2, K - S + 1, N - 1)
    answer.append(x % MOD)

answer += answer[:-1][::-1]

print('\n'.join(map(str,answer)))

Submission status: Runtime Error

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

if K%2 == 1:
  cand = N // K
  print(int(cand + comb(cand,2) * 6 + comb(cand,3) * 6))
else:
  cand_mod0 = N // K
  ans_mod0 = cand_mod0\
           + cand_mod0 * (cand_mod0-1) * 3\
           + cand_mod0 * (cand_mod0-1) * (cand_mod0-2)
  cand_modhalf = N // K if N % K < K / 2 else (N // K) + 1
  ans_modhalf = cand_modhalf\
           + cand_modhalf * (cand_modhalf-1) * 3\
           + cand_modhalf * (cand_modhalf-1) * (cand_modhalf-2)
  print(int(ans_mod0 + ans_modhalf))

Submission status: Runtime Error

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

dprint = lambda *x:x

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353 #出力の制限
__N = 8000
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, __N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )



def kumiawase(p, q):
    # dprint(p,q,cmb(p+q-1,q-1 ,mod))
    return cmb(p+q -1,q-1 ,mod)


def solve(n):
    assert n <= K+1
    # 組み合わせの組
    # abs(n-1)//2 + 偶数分 n//2?
    # 2 ->  1,1
    # 3 -> 1,2
    # 4 -> 1,3 2,2
    # 5 -> 1,4 2,3
    # 6 -> 1,5 2,4 3,3
    # 7  3通り

    # 組のうち片方だけ使用する数 p
    ans = 0
    kumi = (n - 1) // 2
    for p in range(kumi+1):
        # dprint("p",p,"n",n)
        if p>N:
            break
        # 使えるのは p個 + 組に関係ないやつ
        ans += 2**p *cmb(kumi,p,mod)* kumiawase(N - p, p+ (K-kumi*2- int(n%2==0) ) )
        # dprint("anstmp1",ans)
        if n % 2 == 0 and N - p -1 >= 0:
            ans += 2**p *cmb(kumi,p,mod) * kumiawase(N - p -1 , p+ (K-kumi*2- int(n%2==0) ) ) # K==n//2を使用
    # dprint("-------",ans)
    return ans


ans = []
for i in range(2, 2 * K +1):
    if i <= K+1:
        tmp = solve(i)%998244353
        ans.append(tmp)
        print(tmp)
    else:
        print(ans[-i + K])

Submission status: Runtime Error

Solution code:
from decimal import Decimal, ROUND_HALF_UP
n,k = map(int,input().split())
ans = 0
if k % 2 ==0:
    k = Decimal(n/k).quantize(Decimal('0'),rounding=ROUND_HALF_UP)
    ans = k**3 +(n//k)**3
else:
    ans = (n // k)**3
print(ans)

Submission status: Runtime Error

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

time = [0]*(n-k+1)
time_rev = time
res = 10e9
for i in range(n-k+1) :
  time[i] = abs(x[i+k-1]-x[i]) + abs(x[i])
  if(res > time[i]) : res = time[i]
  time_rev[i] = abs(x[i+k-1]-x[i]) + abs(x[i+k-1])
  if(res > time_rev[i]) : res = time_rev[i]
print(res)

Submission status: Runtime Error

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


nums = [x for x in range(1, N+1)]

res = {}
for cwr in combinations_with_replacement(nums, 3):
	rems = [sum(c) % K for c in combinations(cwr, r=2)]
	if 0 == sum(rems):
		for p in permutations(cwr):
			res[p] = 1

print len(res.keys())

Submission status: Runtime Error

Solution code:
n = input()
node = 0
tmp = n
while tmp:
	node += 1
	tmp >>= 1
edges = []
for i in range(node - 1):
	edges.append([i+1, i+2, 0])
	edges.append([i+1, i+2, 1<<i])
for i in range(node-2, -1, -1):
	if (1<<i)&n:
		edges.append([i+1, node, (n>>(i+1))<<(i+1)])
print node, len(edges)
for i in edges:
	print i[0], i[1], i[2]

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
print((N//K)**3)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())

if b%2 != 0:
  print(pow(a//b,3))
else:
  print(pow(a//b,3)+pow(((a+b//2)//a),3)

Submission status: Runtime Error

Solution code:
import collections
n = int(input())
a = list(map(int,input().split()))
mae = []
usi = []
for i in range(0,n,2):
  mae.append(a[i])
for i in range(1,n,2):
  usi.append(a[i])
mae = collections.Counter(mae)
usi = collections.Counter(usi)
mae = mae.most_common()
usi = usi.most_common()
if mae[0][0] != usi[0][0]:
  print(n-mae[0][1]-usi[0][1])
else:
  try:
    t = mae[0][1] + usi[1][1]
  except:
    t = 0
  try:
    s = mae[1][1] + usi[0][1]
  except:
    s = 0
  u = mae[0][1]
  print(n-max(t,s,u))

Submission status: Runtime Error

Solution code:
N = int(input())
A=[]
ret = "Yes"
for i in range(N):
    A.append (int(input()))
    
if A[0] % 2 ==0:
    ret = "No"
    
for i in range(N-2):
    if A[i]-A[i+2] % 2 !=0:
        ret = "No"


print (ret)

Submission status: Runtime Error

Solution code:
def Triangular(N,K):
    count=0
    for a in range(1,N+1):
        for b in range(1,N+1):
            for c in range(1,N+1):
                if ((a+b)%K)+((b+c)%K)+((c+a)%K)==0:
                    count=count+1
                    print("(",a," ",b," ",c,")")
    return count

N=input()
K=input()
N,K=int(N),int(K)
print(Triangular(N,K))

Submission status: Runtime Error

Solution code:
N=int(input())
K=int(input())
i=0
if 1<=N<=2.0e5 and 1<=K<=2.0e5:
        for a in range(1,N+1,1):
            for b in range(1,N+1,1):
                for c in range(1,N+1,1):
                    if (a+b)%K == 0 and  (a+c)%K == 0 and (b+c)%K == 0:
                        i+=1
print(i)

Submission status: Runtime Error

Solution code:
import sys

data_s = sys.argv
large_n = int(data_s[1])
large_k = int(data_s[2])

res_sum = 0
for num_a in range(1, large_n + 1):
	for num_b in range(1, large_n + 1):
		tmp_ab = num_a + num_b
		if large_k > tmp_ab:
			if large_k % tmp_ab != 0:
				continue
		elif tmp_ab % large_k != 0:
			continue

		for num_c in range(1, large_n + 1):
			tmp_bc = num_b + num_c
			if large_k > tmp_bc:
				if large_k % tmp_bc != 0:
					continue
			elif tmp_bc % large_k != 0:
				continue
			
			tmp_ca = num_c + num_a
			if large_k > tmp_ca:
				if large_k % tmp_ca != 0:
					continue
			elif tmp_ca % large_k != 0:
				continue

			res_sum += 1

print(res_sum)

Submission status: Runtime Error

Solution code:
l = int(input())
edge = []
for i in range(1, 19):
    edge.append((i, i + 1, 1 << (i - 1)))
    edge.append((i, i + 1, 0))
sm = 0
for i in range(19, 0, -1):
    v = 1 << (i - 1)
    while l >= v:
        edge.append((i, 20, sm))
        sm += v
        l -= v
print(20, len(edge))
for x, y, z in edge:
    print(x, y, z)

Submission status: Runtime Error

Solution code:
a, b=map(int, input().split())
try:
	c = a // (b // 2)
	c = c //2 + c% 2
except Exception:
  c = 0
try:
    d = a // b
except Exception:
  d = 0
    print(c**3 + d **3)

Submission status: Runtime Error

Solution code:
a, b=map(int, input().split())
c = a // (b // 2)
c = c //2 + c% 2
d = a // b
print(c**3 + d **3)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
c = a//b-1
d = a//(b//2)
if b % 2 == 0:
	print(c**3+d**3)
else:
	print(c**3)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
c = a//b
d = a//(b//2)
if b % 2 == 0:
	print(d**3)
else:
	print(c**3)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
c = a//b
d = a//(b//2)
if b % 2 == 0:
	print(c**3 + d**3)
else:
	print(c**3)

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 998244353
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

K,N = inpl()

MAX = 20000
fac = [1]*(MAX+1)
for i in range(1,MAX+1):
	fac[i] = (fac[i-1]*i)%mod

gyakugen = [1]*(MAX+1)
gyakugen[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
	gyakugen[i-1] = (gyakugen[i]*i)%mod

def Comb(n,k):#nCk
	return (fac[n]*gyakugen[k]*gyakugen[n-k])%mod

#K=k,N=n,0pair = 0
def calc(k,n,i):
	x = (i-2)//2
	k -= x
	n -= x
	if k == 1:
		if n <= 1:
			return n
		else:
			return 0
	elif k < 1:
		return 0
	tmp = 0
	for j in range(2):
		zb = n-j
		zm = k-2
		tmp += Comb(zb+zm,min(zb,zm))%mod
	tmp %= mod
	tmp *= pow(2,x,mod)
	return tmp

ans = []
for i in range(2,K+2):
	if i%2 == 0:
		pairs = (i-2)//2
		tmp = 0
		for p0 in range(pairs+1):
			tmp += calc(K-p0*2,N,i-p0*2)*Comb(pairs,p0)%mod
			tmp %= mod
	ans.append(tmp)
	print(tmp)

ans = ans[::-1]

for i in range(1,K):
	print(ans[i])

Submission status: Runtime Error

Solution code:
n,k=map(int, input().split())
if k%2==0:
    x=0
    y=0
    for i in range(1,n+1):
        if i%k==k//2:
            x+=1
        if i%k==0:
            y+=1
    ans=0
    if x>=1:
        ans+=com(x,1)
    if x>=2:
        ans+=6*com(x,2)
    if x>=3:
        ans+=6*com(x,3)
    if y>=1:
        ans+=com(y,1)
    if y>=2:
        ans+=6*com(y,2)
    if y>=3:
        ans+=6*com(y,3)
    print(ans)
else:
    x=0
    for i in range(1,n+1):
        if i%k==0:
            x+=1
    ans=0
    if x>=1:
        ans+=com(x,1)
    if x>=2:
        ans+=6*com(x,2)
    if x>=3:
        ans+=6*com(x,3)
    print(ans)
def com(a,b):
    r=1
    for i in range(b):
        r*=(a-i)
        r//=i+1
    return r

Submission status: Runtime Error

Solution code:
n,k=map(int, input().split())
if k%2==0:
    x=0
    y=0
    for i in range(1,n+1):
        if i%k==k//2:
            x+=1
        if i%k==0:
            y+=1
    ans=0
    if x>=1:
        ans+=com(x,1)
    if x>=2:
        ans+=6*com(x,2)
    if x>=3:
        ans+=6*com(x,3)
    if y>=1:
        ans+=com(y,1)
    if y>=2:
        ans+=6*com(y,2)
    if y>=3:
        ans+=6*com(y,3)
    print(ans)
else:
    x=0
    for i in range(1,n+1):
        if i%k==0:
            x+=1
    ans=0
    if x>=1:
        ans+=com(x,1)
    if x>=2:
        ans+=6*com(x,2)
    if x>=3:
        ans+=6*com(x,3)
    print(ans)
    
def com(a,b):
    r=1
    for i in range(b):
        r*=(a-i)
        r//=i+1
    return r

Submission status: Runtime Error

Solution code:

def getIntList():
    return list(map(int, input().split()))    

N, K = getIntList()

res = 0
c1 ==0
c2 ==0
if K %2 ==0:
    t = K//2
else:
    t= -1

if True:
    for i in range(1,N+1):
        if i%K == t:
            c1+=1
        if i%K ==0:
            c2+=1
res =  c1 **3 + c2** 3
print(res)