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):
n=int(input())
def prime_factorize(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    f=3
    while f**2<=n:
        if n%f==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return(a)

import collections
A=collections.Counter(prime_factorize(n-1))
B=collections.Counter(prime_factorize(n))

ans=1
cnt=0
for a,b in A.items():
    ans*=(b+1)
for a, b in B.items():
    if b>=2:
        for i in range(2,b+1):
            if (n//(a**i))%a==1:
                cnt+=1
import math
for i in range(1,math.floor(n**0.5)+1):
    if n%i==0:
        if ((n//i)-1)%i==0:
            cnt+=1
        if ((n//i)-1)%(n//i)==0:
            cnt+=1

print(ans-2+cnt)



n=int(input())
def prime_factorize(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    f=3
    while f**2<=n:
        if n%f==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return(a)

import collections
A=collections.Counter(prime_factorize(n-1))
ans=1
cnt=0
for a,b in A.items():
    ans*=(b+1)

import math
for i in range(1,math.floor(n**0.5)+1):
    x=n
    if n%i==0:
        while x%i==0:
            x//=i   
        if (x-1)%i==0:
            cnt+=1
        if (i-1)%(n//i)==0:
            cnt+=1

print(ans-2+cnt)



n=int(input())
def prime_factorize(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    f=3
    while f**2<=n:
        if n%f==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return(a)

import collections
A=collections.Counter(prime_factorize(n-1))
B=collections.Counter(prime_factorize(n))
ans=1
cnt=0
for a,b in A.items():
    ans*=(b+1)

import math
for i in range(1,math.floor(n**0.5)+1):
    x=n
    if n%i==0:
        if n//(i**B[i])%i==0:
            cnt+=1
        if (i-1)%(n//i)==0:
            cnt+=1

print(ans-2+cnt)



n=int(input())
def prime_factorize(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    f=3
    while f**2<=n:
        if n%f==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return(a)

import collections
A=collections.Counter(prime_factorize(n-1))
B=collections.Counter(prime_factorize(n))
ans=1
cnt=0
for a,b in A.items():
    ans*=(b+1)

import math
for i in range(1,math.floor(n**0.5)+1):
    if n%i==0:
        if j in B.keys():
            if (n // (j ** B[j])) % j == 1:
                cnt+=1
        else:
            if (n//i)%i==1:
                cnt+=1
                
        if (i-1)%(n//i)==0:
            cnt+=1
            
print(ans-1+cnt)

n=int(input())
def prime_factorize(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    f=3
    while f**2<=n:
        if n%f==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return(a)

import collections
A=collections.Counter(prime_factorize(n-1))
ans=1
cnt=0
for a,b in A.items():
    ans*=(b+1)

import math
li=[]
for i in range(2,math.floor(n**0.5)+1):
    if n%i==0:
        li.append(i)
        if i!=n//i:
            li.append(n//i)
li.append(n)
for i in li:
    x = n
    while x % i == 0:
        x //= i
    if x % i == 1:
        cnt += 1
print(ans - 1 + cnt)

        

Verdicts: Wrong Answer

Time Limit Exceeded

Wrong Answer

Runtime Error

Accepted