Problem:


Score : 400 points

Problem Statement

For a positive integer X, let f(X) be the number of positive divisors of X.

Given a positive integer N, find \sum_{K=1}^N K\times f(K).

Constraints

1 \leq N \leq 10^7

Input

Input is given from Standard Input in the following format:

N

Output

Print the value \sum_{K=1}^N K\times f(K).

Sample Input 1

4

Sample Output 1

23

We have f(1)=1, f(2)=2, f(3)=2, and f(4)=3, so the answer is 1\times 1 + 2\times 2 + 3\times 2 + 4\times 3 =23.

Sample Input 2

100

Sample Output 2

26879

Sample Input 3

10000000

Sample Output 3

838627288460105

Watch out for overflows.



Sample input:
4


Sample output:
23

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
import string
def main():  #startline-------------------------------------------
    n = int(input())
    ans = 0
    for i in range(1, n + 1):
        x = n // i
        ans += x*(i+i*x)//2
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Wrong Answer

Solution code:
n=int(input())
aas=0
for i in range(1,n+1):
  aas+=n*(n//i)
print(aas)

Submission status: Wrong Answer

Solution code:
def main():
    def divisors(x):
        l_d, u_d = [], []
        i = 1
        while i*i <= x:
            if n % i == 0:
                l_d.append(i)
                if i != x // i:
                    u_d.append(x//i)
            i += 1
        return l_d + u_d[::-1]
    
    n = int(input())
    a = len(divisors(1))
    if n == 1:
        print(a)
    else:
        for j in range(2, n+1):
            # print('j', j)
            # print('a', a)
            # print('divisors(j)', divisors(j))
            # print('len', len(divisors(j)))
            b = (j * len(divisors(j))) 
            # print('b', b)
            a += b
        print(a)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def readinput():
    n=int(input())
    return n

def main(n):
    fk=[1]*(n+1)
    nn=n//2+1
    for i in range(2,nn+1):
        j=i
        while(j<=n):
            fk[j]+=1
            j+=i
    sum=0
    for i in range(1,n+1):
        sum+=i*fk[i]
    return sum

if __name__=='__main__':
    n=readinput()
    ans=main(n)
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 0
for i in range(1,n+1):
  ans += i * (1+n//i) * (n//i) / 2
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 0
for i in range(1, n+1):
	y = n // i
	ans += y * (y +1) * i / 2

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]



if __name__ == "__main__":
    N = int(input())
    total = 0
    for i in range(1,N+1):
        Y = int(N/i)
        total += Y*(Y+1)*i/2
    print(total)

Submission status: Wrong Answer

Solution code:
import numpy as np
def divisor_num(n):
    if n == 1:
        return 1
    arr = []
    temp = n
    for i in range(2,int(np.sqrt(n))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(cnt)
    
    if temp!=1:
        arr.append(1)

    if arr==[]:
        arr.append(1)
    
    ans = 1
    for num in arr:
        ans *= num+1
    
    return ans

n = int(input())
total = 0
for i in range(1,n+1):
    total += i*divisor_num(i)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    n = int(input().strip())
    ans = 0

    for i in range(1, n+1):
        limit = int(n / i)
        ans += limit * (limit + 1) / 2
    print(int(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())

l = [0 for _ in range(n+1)]
l[1] = 1

for i in range(n+1):
    for j in range(i-1, 0, -1):
        if i % j == 0:
            l[i] = l[j] + 1
            break

ans = 0
for k in range(n+1):
    ans += (k * l[k])

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [0 for _ in range(n+1)]
l[1] = 1

for i in range(n+1):
    for j in range(i-1, 0, -1):
        if i % j == 0:
            l[i] = l[j] + 1
            break

ans = 0
for k in range(n+1):
    print(k * l[k])
    ans += (k * l[k])

print(ans)

Submission status: Wrong Answer

Solution code:
import copy

#素因数分解
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

factorize_result_dict = dict()

N = int(input())
ans = 0

if N == 1:
    print(1)
else:
    ans = 1
    ans += 2*2
    factorize_result_dict[2] = dict()
    factorize_result_dict[2][1] = 1
    factorize_result_dict[2][2] = 1

    for i in range(3,N+1):
        for j in range(i//2,1,-1):
            if i%j == 0:
                if i//j in factorize_result_dict[j]:
                    factorize_result_dict[i] = copy.copy(factorize_result_dict[j])
                    factorize_result_dict[i][i//j] += 1
                else:
                    factorize_result_dict[i] = copy.copy(factorize_result_dict[j])
                    factorize_result_dict[i][i//j] = 1

                divisor_len = 1
                for k in factorize_result_dict[i].values():
                    print(k)
                    divisor_len *= k+1
                ans += divisor_len*i
                print(i,divisor_len*i)
                break
        else:
            factorize_result_dict[i] = dict()
            factorize_result_dict[i][1] = 1
            factorize_result_dict[i][i] = 1
            ans += 2*i
            print(i,2*i)
    print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
print(sum((N//i)*(N//i*1)//2)*i for i in range(1,N+1))

Submission status: Wrong Answer

Solution code:
N = int(input())
l = [False] * (N + 1)
def count(n):
  ret = 0
  i = 1
  while i*i <= n:
    if n % i == 0:
      ret += 1
      if i != n // i:
        ret += 1
    i += 1
  return ret

num = [0] * (10**5 + 1)
for i in range(1, 10**5):
  num[i] = count(i)


ans = 1
l[0] = True
l[1] = True
if N==1:
  print(ans)
else:
  for i in range(2,N+1):
    if l[i]:
      continue
    if i<=10**5:
      ans += num[i] * i
    else:
      x = int(i**(1/2)) + 1
      a = 1
      while x>1:
        if num[x]!=2:
          x -= 1
          continue
        else:
          y = i
          while True:
            if y%x==0:
              y//=x
              a += 1
            else:
              break
          if y<=10**5:
            ans += a * num[y]
            break
          else:
            x -= 1
            continue
              

  print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

import math
def divisor(n):
    a = set()
    for i in range(1, math.ceil(n**0.5) + 1):
        if n % i == 0:
            a.add(i)
            a.add(n // i)
    return a
x = [0] * (n+1)
M = int((n+1)**.5)+1
for i in range(1, M):
    for j in range(i, n+1, i):
        x[j] += 1
ans = 0
for i in range(n+1):
    #print(i,x[i],divisor(i))
    ans += (i * x[i])
print(ans)

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    i = 1
    ans=0
    while i*i<=n:
        if n%i ==0:
            ans+=1
            if i!=n//i:
                ans+=1
        i+=1
    return ans*i

ans=0
n=int(input())
for i in range(2,n+1):
    ans+=make_divisors(i)
print(ans+1)

Submission status: Wrong Answer

Solution code:
def divisor(x):
    count=0
    for i in range(1,x//2):
        if x%i==0:
            count+=1
    return count

n = int(input())
ans=0
for num in range(1,n+1):
    a = 0
    divisors = divisor(num)
    a = num* divisors 
    ans+=a
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=0
l=[x for x in range(1,n+1)]
for i in range(1,n+1):
  z=i
  for j in range(0,n,i):
    ans+=z
    z+=i
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

def func(num):
  count = 0  # 1は約数
  for a in range(1, num+1):
    if not num % a:
      count += 1
  return count

nums = [0] * (N + 1)
nums[1] = 1

for i in range(2, N+1):
  if not nums[i]:
    tmp = func(i)
    print(i, tmp)
    for j in range(i, N+1, i):
      add_num = nums[j // i] if j // i > 1 else 0
      nums[j] = j * (tmp + add_num)
      # print(j, tmp, add_num)

print(sum(nums))

Submission status: Wrong Answer

Solution code:
import math


def main():
    n = int(input())

    A = [2] * (n + 1)
    
    ans = 1
    for i in range(2, n + 1):
        d = math.isqrt(i)
        A[i] = d + 1
        ans += i * (A[d] + 1)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
j = int(input())
ans = 1

for n in range(2, j + 1):
    arr = 0
    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 *= cnt + 1
    if temp != 1:
        arr = 1 + 1

    if arr == 0:
        arr = 1 + 1
        
    print(n,arr)
    
    ans += n * arr
ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
n = int(input())
def main(n):
    t=0
    if n > 10000000:
        t = 838627288460105
        for i in range(10000000,n):
            t += len(make_divisors(i+1))*(i+1)
            return t
    if n > 1000000:
        t = 7235062807366
        for i in range(1000000,n):
            t += len(make_divisors(i+1))*(i+1)
            return t
    if n > 100000:
        t = 60838190672
        for i in range(100000,n):
            t += len(make_divisors(i+1))*(i+1)
            return t
    if n > 10000:
        t = 493438984
        for i in range(10000,n):
            t += len(make_divisors(i+1))*(i+1)
            return t
    if n > 1000:
        t = 3787654
        for i in range(1000,n):
            t += len(make_divisors(i+1))*(i+1)
        return t

    for i in range(n):
        t += len(make_divisors(i+1))*(i+1)
    return t
print(main(n))

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    c=0
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            c+=1
            if i != n // i:
                upper_divisors.append(n//i)
                c+=1
        i += 1
    return lower_divisors + upper_divisors[::-1]

n=int(input())
ans = 1
d = {1:1}
for i in range(2,n+1):
    c = 0
    ls = []
    for j in range(1,i+1):
        if i%j == 0:
            ls.append(j)
            c += 1
            t = i//j
            if d.get(t):
                cc = 0
                for k in ls:
                    if t%j == 0:
                        cc += 1
                c += d.get(t) - cc
                break
    ans += i * c
    d[i] = c
print(ans)

Submission status: Wrong Answer

Solution code:
def s(num):
    yakusuu_array = []
    for i in range(1,num):
        if num % i == 0:
            yakusuu_array.append(i)
    return len(yakusuu_array)
N = int(input())
count = 0
for i in range(N):
    count = (i + 1) * s(i + 1) + count
print(count)

Submission status: Wrong Answer

Solution code:
x = int(input())
solved = [0 for _ in range(x+1)]
prime = [2, 3, 5]
sum1 = 0
for i in range(2, x+1):
    j = 0
    sum2 = i
    while prime[j]**2 <= i:
        count = 0
        while i % prime[j] == 0:
            i //= prime[j]
            count += 1
        sum2 *= count+1
        j += 1
    if sum2 == i:
        prime.append(i)
        sum2 *= 2
    sum1 += sum2
print(sum1+1)

Submission status: Wrong Answer

Solution code:
import numpy
n=int(input(''))
b=numpy.zeros((n+1,1),dtype=int)


for a in range(1,n+1):
    c=0
    while(1):
        if a+a*c<=n:
            b[a+a*c][0]+=1
            c+=1
        else:
            break


q=[numpy.arange(0,n+1,dtype=int)]


s=numpy.dot(q,b)
print(s[0])

Submission status: Wrong Answer

Solution code:
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import copy
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def main():
    N = I()
    ans = 0
    t = int(math.sqrt(N)) + 1
    divsdic = defaultdict(lambda x: defaultdict(int))
    era = primes(t)

    def get_divisor_count(k):
        n = k
        d = defaultdict(int)
        while k != 0:
            if divsdic.get(k) is not None:
                for (k, v) in divsdic[k].items():
                    d[k] += v
                divsdic[n] = copy.copy(d)
                if k != 1:
                    d[k] += 1
                return copy.copy(d)
            for i in era:
                if k % i == 0:
                    k //= i
                    d[i] += 1
                    break
            else:
                break
        divsdic[n] = copy.copy(d)
        return d

    for i in range(1, N + 1):
        d = get_divisor_count(i)
        tmp = 1
        for v in d.values():
            tmp *= v + 1
        ans += tmp * i

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
from math import sqrt
N = int(input())
sqN = int(sqrt(N))
ans = 0
for i in range(1,sqN+1):
    ans += i*(N//i)*(N//i+1)//2 
    if N % i == 0:
        j = N//i
        if j > i:
            ans += j*((N//j)*(N//j+1)//2 - 1)
ans += (N - sqN)*(sqN+1+N)//2
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
import math
def phan(n):
  m=math.floor(math.sqrt(n))+1
  jud=0
  for i in range(2,m):
    if (n%i)==0:
      jud=jud+1
  if jud==0:
     return 1
  else:
    return 0
def plist(x):
  plist=[]
  for i in range(2,x):
    if phan(i)==1:
      plist.append(i)
  return plist
def yakusu(x):
  count=0
  kata=1
  for i in plist(x):
    counti=0
    for j in range(1,10**7):
      if x%(i**j)==0:
        counti=counti+1
      else:
        kata=kata*(counti+1)
        break
  return kata
sum2=0
for i in range(1,N):
  sum2=sum2+i*yakusu(i)
print(sum2)

Submission status: Wrong Answer

Solution code:
N = int(input())
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
b = 0; c = 0; j = 0; d = 1; e = 0; f = 0; g = 0
s = []; 
a = factorization(N)
while j > len(a):
    b += a[j][1]
    j += 1
    s.append(b+1)
for i in range(0,len(s)):
    d *= s[i]

for i in range(1,d+1):
    t = []
    d2 = 1
    fac = factorization(i)
    while e > len(a):
        c += fac[j][1]
        e += 1
        t.append(b+1)
    for u in range(0,len(t)):
        d2 *= t[u]
    f += d2*i
print(f)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


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


def countp(cp, p):
    ret = 0
    while cp % p == 0:
        ret += 1
        cp //= p
    return ret


def count_in(fx_dict):
    if not fx_dict:
        return 2
    ret = 1
    for v in fx_dict:
        ret *= (v + 1)
    return ret


def main():
    N = int(input())
    fx = [[] for _ in range(N + 1)]
    for p in range(2, N + 1):
        if fx[p]:
            continue
        for cp in range(p, N + 1, p):
            tmp = countp(cp, p)
            fx[cp].append(tmp)
    print(fx)

    ans = 1
    for i in range(2, N + 1):
        tmp = count_in(fx[i])
        print(i, tmp)
        ans += i * tmp

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
import math

def divNum(n):
    prod = 1
    p_sum = 1

    while n % 2 == 0:
        p_sum += 1
        n = n // 2
    prod *= p_sum

    div = 3

    while div**2 <= n:
        p_sum = 1
        if n % div == 0:
            p_sum += 1
            n = n // div
        else:
            prod *= p_sum
            div += 2
    
    if n != 1:
        prod *= 2

    return prod

n = int(input())

summ = 1
prod = 1

for i in range(2,n+1):
    summ += i * divNum(n)

print(summ)

Submission status: Wrong Answer

Solution code:
import collections
import math

n = int(input())

f_list = [[]]*(10**7+1) # すべて素数扱い

def get_ans(t):
    c = collections.Counter(t)
    v_list = c.values()
    ans = 1
    for v in v_list:
        ans *= v+1
    return ans

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
ans = 0
for i in range(2, n+1):
    tmp = prime_factorize(n)
    # f_list[i] = tmp
    ans += i*get_ans(tmp)
print(ans+1)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
ans = 0
A = [1 for i in range(N + 2)]
k = 2
A[1] = 0
while k <= math.sqrt(N):
    for i in range(k,N + 1,k):
        q = i
        p = 1
        while q % k == 0:
            q /= k
            p += 1
        A[i] *= p
    while A[k] != 1:
        k += 1
for i in range(1,N + 1):
    if A[i] <= 1:
        A[i] += 1
    ans += i * A[i]
print(ans)