Problem:


Score : 500 points

Problem Statement

Snuke received a positive integer N from Takahashi.
A positive integer m is called a favorite number when the following condition is satisfied:

The quotient and remainder of N divided by m are equal, that is, \lfloor \frac{N}{m} \rfloor = N \bmod m holds.

Find all favorite numbers and print the sum of those.

Constraints

All values in input are integers.

1 \leq N \leq 10^{12}

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

8

Sample Output 1

10

There are two favorite numbers: 3 and 7. Print the sum of these, 10.

Sample Input 2

1000000000000

Sample Output 2

2499686339916

Watch out for overflow.



Sample input:
8


Sample output:
10

Submission status: Time Limit Exceeded

Solution code:
import math
# import random
 
 
class Prime:
    seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
 
    def is_prime(self, n):
        """
        prime test (hybrid)
 
        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369
 
        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common
 
        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)
 
    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False
 
    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes
 
        :param n:
        :return: boolean
        """
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True
 
    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes
 
        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369
 
        :param n:
        :return: boolean
        """
 
        d = n - 1
        while d & 1 == 0:
            d >>= 1
 
        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]
 
        for w in witnesses:
            y = pow(w, d, n)
 
            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1
 
            if y != n - 1 and d & 1 == 0:
                return False
 
        return True
 
    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12
 
        return self.seed_primes[:_get_range(num)]
 
    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a
 
    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n
 
    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm
 
        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98
 
        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n
 
        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)
 
        if d == n:
            return self.find_factor(n, seed+1)
        return self.find_factor(d)
 
    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes
 
        while n > 1:
            factor = self.find_factor(n)
 
            primes.setdefault(factor, 0)
            primes[factor] += 1
 
            n //= factor
 
        return primes
 
 
if __name__ == '__main__':
    prime = Prime()
    N = int(input())
 
    end = int((math.sqrt(1 + 4 * N) + 1) / 2) + 1
 
    cmpl_sum = 0
    cmpl_num = 0
    for div in range(1, end):
        if N % div == 0:
            cmpl_num += 1
            cmpl_sum += div
 
    # assert prime.find_factors(36610051291281) == {653: 1, 593783: 1, 3: 3, 13: 1, 269: 1}
    factors = prime.find_factors(N)
 
    sum_divisor = 1
    num_divisor = 1
    for p, a in factors.items():
        sum_divisor *= sum(pow(p, power) for power in range(a+1))
        num_divisor *= (a + 1)
 
    print(sum_divisor - cmpl_sum - (num_divisor - cmpl_num))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
max_N = N
min_a = 1
sum_n = 0
while(min_a < N):
    for a in range(min_a, int(N/2)):
        for n in reversed(range(1, max_N)):
            #print("n",n)
            if n * a + a == N:
                if N % n*a != 0:
                    #print(n,a)
                    #l.append(n)
                    sum_n += n
                    max_N = int(n / 2) + 1
                    min_a *= 2
                    break
print(sum_n)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
result = 0

for m in range(1, N+1):
    if int(N/m) == N%m:
        result += m

print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(input())

cnt = 0

for m in range(1,N):
    if int(N/m) == N%m:
        cnt += m

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

ans = 0
for i in range(1, N+1):
    if N//i == N%i:
        ans += i

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import product

n = int(input())
if n < 3:
    print(0)
else:
    rt = int(n ** 0.5)
    if n // rt != rt:
        rt = 0
    factors = defaultdict(int)
    N = n
    n_div = 2
    while n > 1:
        while not n % n_div:
            factors[n_div] += 1
            n = n // n_div
        n_div += 1
    lis = [1]
    for k, v in factors.items():
        facts = [k ** i for i in range(v + 1)]
        it = product(lis, facts)
        lis = [a * b for a, b in it]
    nums = [l - 1 for l in lis if l - 1]
    nums = [i for i in nums if (N //i) == (N % i)]
    print(sum(nums))

Submission status: Time Limit Exceeded

Solution code:
N =int(input())
ans = 0
for j in range(2,N):
  for i in range(N//j,N//(j-1)):
    if (N//i) == N%i:
        ans += i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

s = 0
t = 0
sum1 = 0

for i in range(n):
    s = n // (i+1)
    t = n % (i+1)
    if s == t:
        sum1 += i+1
        
print(sum1)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline

N = int(readline())

sqrtN = int(N ** 0.5)

i = 1
total = 0
while True:
    if N % i == 0:
        if i < (N // i) - 1:
            total += N // i - 1
        else:
            break
    i += 1

print(total)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
sum = 0
for i in range(1, N+1):
  a = int(N / i)
  b = N % i
  if (a == b):
    sum += i
print(sum)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
sum = 0

for i in range(1, n+1):
    if n%i == n//i:
        sum += i

print(sum)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
cnt = 0
a = 1
while a <= np.sqrt(N):
    if N % a == 0:
        add = int(N/a) - 1
        if a < add:
            cnt += add
    a += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
sum = 0
for i in range(1,n):
  q = n // i
  r = n % i
  if q == r:
    sum += i
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
ans = 0


class Prime:
    # https://qiita.com/daikw/items/f48d6ac374255763463d
    seed_primes = [
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
        71, 73, 79, 83, 89, 97
    ]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

        :param n:
        :return: boolean
        """
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed + 1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes


factors_dict = Prime().find_factors(N)
factors_values = list(factors_dict.values())
factors_keys = list(factors_dict.keys())
factors = []
import itertools
for K in itertools.product(*[range(_ + 1) for _ in factors_values]):
    f = 1
    for i in range(len(factors_keys)):
        f *= factors_keys[i]**K[i]
    factors += [f]
ans = 0
for f in factors:
    if N < f * (f - 1):
        ans += f - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
total = 0
for i in range(2,N):
    if N//i == N%i:
        total += i
print(total)

Submission status: Time Limit Exceeded

Solution code:
N =int(input())
ans = 0
for j in range(2,N):
  for i in range(N//(j),N//(j-1)):
    if (N//i) == N%i:
        ans += i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools as itr
import math
n = int(input())

if n == 1:
    print(0)
    exit()

if n == 1:
    print(0)
    exit()


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

def calc(tp):
    ans = 1
    for a in tp:
        ans *= a
    return ans

soinsu = factorize(n)
yakusu = []
for i in range(len(soinsu)):
    yakusu += [calc(a) for a in itr.combinations(soinsu, i+1) if calc(a) >= math.sqrt(n)]

yakusu = sorted(list(set(yakusu)))

ans = 0
for a in yakusu:
    sho = n // (a-1)
    amari = n % (a-1)
    if sho == amari:
        ans += (a-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
count = 0
for i in range(1, N+1):
    if int(N/i) == N%i:
        count += i
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
count = 0
for i in range(1,N):
    if N % i != 0:
        if N//i == N % i:
            count += i
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
sum = 0
for i in range(1,n):
  if n // i == n % i:
    sum += i
print(sum)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

sN = int((N-1/4)**0.5+1/2)
sm = 0
for m in range(sN,N):
  if int(N/m)==N%m:
    sm += m
    
print(sm)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

count = 0
for m in range(1,n+1):
    s = n // m
    a = n - s*m
    if(s==a):
        count += m
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
#DivRem number
N  = int(input())
ans = 0
for m in range(1, N):
    if int(N / m) == N % m:
        ans += m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
# import random


class Prime:
    seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

        :param n:
        :return: boolean
        """
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed+1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes


if __name__ == '__main__':
    prime = Prime()
    N = int(input())

    end = int((math.sqrt(1 + 4 * N) + 1) / 2) + 1

    cmpl_sum = 0
    cmpl_num = 0
    for div in range(1, end):
        if N % div == 0:
            cmpl_num += 1
            cmpl_sum += div

    # assert prime.find_factors(36610051291281) == {653: 1, 593783: 1, 3: 3, 13: 1, 269: 1}
    factors = prime.find_factors(N)

    sum_divisor = 1
    num_divisor = 1
    for p, a in factors.items():
        sum_divisor *= sum(pow(p, power) for power in range(a+1))
        num_divisor *= (a + 1)

    print(sum_divisor - cmpl_sum - (num_divisor - cmpl_num))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
sum=0
for i in range(1,N):
    q, mod = divmod(N, i)
    if q==mod:
        sum=sum+i
print(sum)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

alpha = 0
answer = 0
while True:
    alpha += 1
    if N - alpha < alpha:
        break
    if (N - alpha) % alpha == 0:
        m = (N - alpha) // alpha
        if alpha >= m:
            break
        answer += m
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

correct_list = []

for i in range(1,N+1):
    ans = N // i
    mod = N % i
    #print(ans, mod)
    if ans == mod:
        correct_list.append(i)
        
print(sum(correct_list))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

ans = 0

for m in range(1, N+1):
    n_div = N // m
    n_mod = N % m
    if n_div == n_mod:
        #print(m)
        ans += m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N =int(input())
ans = 0
for i in range(1,N):
    if (N//i) == N%i:
        ans += i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = 1
ans = 0
while x < n:
    if ((n-x) % x) == 0:
        m = (n-x) // x
        if m <= x:
            break
        ans += m
    x += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = 0
for i in range(1,N):
    if(N//i == N%i):
        ans += i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = 0

for p in range(1, int(n/2) + 1):
  t = (n - p) / p
  if t.is_integer():
    if (n // int(t)) == (n % int(t)):
      s += int(t)

print(s)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = 0
x = 0

while True:
    x += 1
    m = (N-x)/x
    if m % 1 == 0:
        if x < m <= N:
            ans += m
        else:
            break

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = 0
s = N//2+1
for i in range(1, s):
  if N%i == 0:
    a = N/i - 1
    if a > i:
      ans += a
    else:
      break;
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
z =0

for i in range(1, n+1):
    b = n//i
    c = n%i
    if b==c:
        a.append(i)
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = 0
ans_list = [1]

if N != 1:
  for i in range(2, N // 2 + 1):
    if N % i == 0:
      ans_list.append(i)

for i in ans_list:
  if N/i - 1 > i:
    ans += N/i - 1
  else:
    break;
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

i = 2
N_ = N
ans = 0

divisor = {}
while(N_>1):
    if N_ % i == 0:
        divisor[i] = 0
        while(N_ % i == 0):
            divisor[i] += 1
            N_ //= i
    i += 1

ans += 0
def solve(dic,keys,n,i):
    if i == len(keys):
 #       print(n)
        if n-1 != 0 and N == (N % (n-1))*n:
            global ans
            ans += n-1

    else:
        for j in range(dic[keys[i]]+1):
            solve(dic,keys,n*keys[i]**j,i+1)

#print(divisor)
ans = 0 
solve(divisor,list(divisor.keys()),1,0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
# import random


class Prime:
    seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

        :param n:
        :return: boolean
        """
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed+1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes


if __name__ == '__main__':
    prime = Prime()
    N = int(input())

    end = int((math.sqrt(1 + 4 * N) + 1) / 2) + 1

    cmpl_sum = 0
    cmpl_num = 0
    for div in range(1, end):
        if N % div == 0:
            cmpl_num += 1
            cmpl_sum += div

    # assert prime.find_factors(36610051291281) == {653: 1, 593783: 1, 3: 3, 13: 1, 269: 1}
    factors = prime.find_factors(N)

    sum_divisor = 1
    num_divisor = 1
    for p, a in factors.items():
        s = 0
        for power in range(a+1):
            s += pow(p, power)
        sum_divisor *= s
        num_divisor *= (a + 1)

    print(sum_divisor - cmpl_sum - (num_divisor - cmpl_num))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans  = [i for i in range(1,n) if n//i == n%i]
print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

###商及び余りをsとすると、n=m*s+s=s(m+1)、ただし0<s<m
sum_fav = 0
for s in range(1,n):
  if n%s == 0:
    m = n//s-1
    if s < m:
      #print(m)
      sum_fav += m
    else:
      break
  
print(sum_fav)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
c=0
for i in range(1,n):
  if(n//i==n%i):
    c+=i
print(c)

Submission status: Time Limit Exceeded

Solution code:
a=int(input())  #数値入力
fav = 0
for i in range(2,a):
#     print(i)
    if int(a/i) == a%i:
        fav += i
print(fav)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

sm = 0
for m in range(1,N):
  if int(N/m)==N%m:
    sm += m
    
print(sm)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

ans = 0

for m in range(1, N+1):
    if N//m == N % m:
        ans += m

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = 0
m = 1
for m in range(1,N):
    tmp = divmod(N,m)  # tapple
    if int(tmp[0]) == int(tmp[1]):
        ans = ans+m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

m_list = []
for m in range(1,N+1):
    div = N//m
    mod = N%m
    if mod != 0:
        if div == mod:
            m_list.append(m)
print(sum(m_list))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = []
for i in range(1,N):
    a = N // i
    mod = N % i
    if a == mod:
        s.append(i)
print (sum(s))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = 0
for i in range(1, N):
  if N%i == 0:
    if N/i - 1 > i:
      ans += N/i - 1
    else:
      break;
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
i = 1
ans = 0
while 1:
    if (n-i)%i == 0 :
        if ((n-i)//i) > i:
            ans += (n-i)//i
        else:
            break
    i += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = 0
m = 1
for m in range(1,N):
    tmp = divmod(N,m)  # tapple
    a = int(tmp[0])
    b = int(tmp[1])
    if a == b:
        ans = ans+m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

ans = [m for m in range(2, n) if n // m == n % m]

print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

ans = 0
for i in range(1, 10**6+1):
    if n % i == n//i:
        ans += i

syou = n // 10**6

i = 10**6 + 1
while True:
    if syou != n//i:
        break
    else:
        if n % i == n//i:
            ans += i
    i += 1

syou = n//i

for i in range(1, syou+1):
    if (n-i) % i != 0:
        continue
    else:
        okiniiri = (n-i) // i
        if n % okiniiri == i:
            ans += okiniiri 

print(ans)