Problem: Given is a positive integer N.  We will choose an integer K between 2 and N (inclusive), then we will repeat the operation below until N becomes less than K.    * Operation: if K divides N, replace N with N/K; otherwise, replace N with N-K.  In how many choices of K will N become 1 in the end?

Submission attempts (in order):
import collections
from itertools import combinations
import math
N = int(input())

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

def gcd(*numbers):
    return reduce(math.gcd, numbers)

L = collections.Counter(prime_factorize(N-1))
# print(L)
A = 1
for i,v in L.items():
    A *= (v+1)

A -= 1 

c = collections.Counter(prime_factorize(N))
prime = list(dict(c).keys())
d = []
for i in range(1,len(c)):
    d += list(combinations(prime,i))
be = list(c.values())


D = 0
if len(be) > 1:
    beki = math.gcd(be)
else:
    beki = be[0]
    while beki%2 == 0:
        beki = beki //2
        D += 1

# C = 1
# for i,v in L.items():
#     C *= (v+1)
# C -= 1

B = 1
for divisor in d:
    a = N
    b = 1
    print(divisor)
    for i in divisor:
        b *= i ** c[i]
        a /= (i ** c[i])
    if b >= a:
        amari = b%a
        print(b,a,amari)
        if amari == 1:
            B += 1

# print(A,B,D)
print(A+B+D)

import collections
from itertools import combinations
from functools import reduce
import fractions
N = int(input())

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

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

L = collections.Counter(prime_factorize(N-1))
# print(L)
A = 1
for i,v in L.items():
    A *= (v+1)

A -= 1 

c = collections.Counter(prime_factorize(N))
prime = list(dict(c).keys())
d = []
for i in range(1,len(c)):
    d += list(combinations(prime,i))
be = list(c.values())


D = 0
if len(be) > 1:
    # print(be)
    beki = gcd(be)
else:
    beki = be[0]
    while beki%2 == 0:
        beki = beki //2
        D += 1

# C = 1
# for i,v in L.items():
#     C *= (v+1)
# C -= 1

B = 1
# print(c)
for divisor in d:
    a = N
    b = 1
    
    for i in divisor:
        a /= (i ** c[i])
        b = i
    # print(a,b)
    for j in range(c[i]):
        b = b**(j+1)
        if a > b:
            amari = a%b
            # print(b,a,amari)
            if amari == 1:
                B += 1

# print(A,B,D)
print(A+B+D)

import math
N = int(input())
M = int(math.sqrt(N))
M2 = int(math.sqrt(N-1))
count = 0
for i in range(1,M2+1):
    if (N-1)%i == 0:
        if i == M2:
            count += 1
        else:
            count += 2

divsion = []
for i in range(2,M+1):
    if N%i == 0:
        divsion.append(i)

for i in divsion:
    while N%i == 0:
        N = N/i
    if N % i == 1:
        count += 1
        break

print(count+1)


import math
N = int(input())
M = int(math.sqrt(N))
M2 = int(math.sqrt(N-1))
y = []
for i in range(1,M2+1):
    if (N-1)%i == 0:
        m = (N-1)//i
        if not m == 1:
            y.append(m)
        if i == 1 or i == m:
            continue
        else:
            y.append(i)
count = len(y)

y = []
for i in range(1,M+1):
    if N%i == 0:
        m = N//i
        y.append(m)
        if i == 1 or i == m:
            continue
        else:
            y.append(i)

for i in y:
    NN = N
    while NN%i == 0:
        NN /= i
    # print(NN)
    if int(NN) % i == 1:
        count += 1
        # print(i)

print(count)



Verdicts: Runtime Error

Wrong Answer

Wrong Answer

Accepted