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):
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
  
n = int(input())
a = factorization(n)
ans = 1
b = factorization(n-1)
chk = 1
for i in range(len(b)):
  chk *= (b[i][1]+1)
ans += chk-1
for i in range(len(a)):
    for j in range(1,a[i][1]+1):
      cnt = 0
      cnt += a[i][1]-a[i][1]%j
      #print(a[i][0]**j,cnt,n/(a[i][0]**cnt),n/(a[i][0]**cnt) % (a[i][0]**(j)))
      if n/(a[i][0]**cnt) % (a[i][0]**(j)) == 1:
            ans += 1
if len(a) == 1:
  ans -= 1
if n == 2:
  ans = 1

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
  
n = int(input())
a = factorization(n)
ans = 1
if n == 2:
  print(1)
  exit()
  
b = factorization(n-1)
chk = 1
for i in range(len(b)):
  chk *= (b[i][1]+1)
ans += chk-1
for i in range(len(a)):
    for j in range(1,a[i][1]+1):
      cnt = 0
      cnt += a[i][1]-a[i][1]%j
      print(a[i][0]**j,cnt,n/(a[i][0]**cnt),n/(a[i][0]**cnt) % (a[i][0]**(j)))
      if n/(a[i][0]**cnt) % (a[i][0]**(j)) == 1:
            ans += 1
if len(a) == 1:
  ans -= 1
print(ans)

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
n = int(input())
a = factorization(n)
ans = 1
if len(a) == 1 and a[0]!=n:
  ans += a[1]-1
b = factorization(n-1)
chk = 1
for i in range(len(b)):
  chk *= (b[i][1]+1)
ans += chk-1
print(a)
if len(a) >= 2:
  for i in range(len(a)):
    for j in range(a[i][1]+1):
      if j!=0 and int(n/(a[i][0]**(j)))%(a[i][0]**(j)) == 1:
        ans += 1
print(ans)

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
n = int(input())
a = factorization(n)
ans = 2
if len(a) == 1 and a[0]!=n:
  ans += a[1]-1
b = factorization(n-1)
chk = 1
for i in range(len(b)):
  chk *= (b[i][1]+1)
ans += chk-1

if len(a) >= 2:
  for i in range(len(a)):
    for j in range(a[i][1]):
      if int(n/(a[i][0]**j))%a[i][0]**j == 0:
        ans += 1
print(ans)

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
  
def divisorize(n):
    
    f = factorization(n)
    divisors = [1]
    for k in range(len(f)):
        num_divisors = len(divisors)
        for i in range(1, f[k][1] + 1):
            for j in range(num_divisors):
                divisors.append(divisors[j] * f[k][0] ** i)
    return sorted(divisors)
  
n = int(input())
ans = 0
chk = divisorize(n-1)
for i in divisorize(n)[1:]:
  m = n
  while True:
    if m == 1:
        ans += 1
        chk.append(i)
        break
    if m < i:
      break
    if m%i == 0:
      m = m//i
    else:
      m = m%i

chk = set(chk)
print(len(chk)-1)

Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Accepted