Problem:
 Score : 600 points    Problem Statement 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?      Constraints  2 \leq N \leq 10^{12}  N is an integer.         Input Input is given from Standard Input in the following format:  N       Output Print the number of choices of K in which N becomes 1 in the end.        Sample Input 1 6      Sample Output 1 3  There are three choices of K in which N becomes 1 in the end: 2 , 5 , and 6 .  In each of these choices, N will change as follows:   When K=2 : 6 \to 3 \to 1  When K=5 : 6 \to 1  When K=6 : 6 \to 1        Sample Input 2 3141      Sample Output 2 13       Sample Input 3 314159265358      Sample Output 3 9

Solution (Python):
n = int(input())
ans = 0
def factorize(n):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.append(n)
    return divisors

def check(num, mod):
    if num % mod == 1:
        return 1
    elif num % mod == 0:
        num = num / mod
        return check(num, mod)
    else:
        return 0


nfct = factorize(n)
n_1fct = factorize(n - 1)
if n_1fct != [1]:
  ans += len(n_1fct)
for mod in nfct:
  ans += check(n,mod)
print(ans)

Solution (Python):
N = int(input())

ans = []
for n in range(1, int(N ** 0.5) + 1):
    if (N - 1) % n == 0:
        ans.append(n)
        ans.append((N - 1) // n)

for k in range(2, int(N ** 0.5) + 1):
    if N % k != 0:
        continue

    x = N
    while x % k == 0:
        x //= k

    if x % k == 1:
        ans.append(k)

print(len(set(ans)))

Solution (Python):
n = int(input())


def check(n, k):
    while n % k == 0:
        n = n // k
    if n >= k:
        n = n - k * (n // k)
    return n


def count(n):
    total = 0
    cands = set([n, n-1])
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cands.add(i)
            cands.add(n // i)
    for i in range(2, int(n ** 0.5) + 1):
        if (n-1) % i == 0:
            cands.add(i)
            cands.add((n - 1) // i)
    for k in cands:
        if k == 1:
            continue
        if check(n, k) == 1:
            total += 1
    return total


print(count(n))

Solution (Python):
n = int(input())
n_ = n-1
a = [n]
if n_ == 1:
    a_ = []
else:
    a_ = [n_]
    
for i in range(2,int(n**0.5//1+1)):
    if n%i == 0:
        a.append(i)
        if n/i != i:
            a.append(n/i)
    if n_%i == 0:
        a_.append(i)
        if n_/i != i:
            a_.append(n_/i)

ans = len(a_)
for i in a:
    num = n
    while num%i == 0:
        num /= i
    if num % i == 1:
        ans += 1
    
print(ans)

Solution (Python):
from collections import Counter

n = int(input()) 
times = 0

def make_divisors(n):
    divisors = [n]
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    divisors.sort()
    return divisors
    
times = len(make_divisors(n - 1))
a = make_divisors(n)

for i in a:
    tmp = n // i
    if tmp == 1:
        times += 1 
        continue
    while tmp % i == 0:
        tmp = tmp // i
    if tmp % i == 1:
        times += 1 
    
print(times if n != 2 else 1)

Solution (Python):
n = int(input())

def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table


def tester(n, k):
    if k == 1:
        return False

    temp = n
    while temp % k == 0:
        temp /= k

    if temp % k == 1:
        return True
    else:
        return False

answer = []
for i in (divisor(n - 1) + divisor(n)):
    if tester(n, i):
        answer.append(i)

print(len(answer))

Solution (Python):
n = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

cnt = len(make_divisors(n-1))-1
base = make_divisors(n)
for x in base[1:]:
    org = n
    while org % x == 0:
        org = org / x
    if org % x == 1:
        cnt += 1

print(cnt)

Solution (Python):
def make_divisors(n):
    div=[n]
    for i in range(2,-int(-n**0.5//1)):
        if n%i==0:
            div.append(i)
            div.append(n//i)
    if n%(n**0.5)==0:
        div.append(int(n**0.5))
    div.sort()
    return div

n=int(input())
if n>2:
    ans=make_divisors(n-1)
else:
    ans=[]
for i in make_divisors(n):
    a=n
    while a%i==0:
        a=a//i
    if a%i==1:
        ans.append(i)
print(len(ans))

Solution (Python):

N = int(input())



import math
from collections import Counter
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

def sub_div(n, k):
    if k == 1:
        return n
    while n >= k:
        if n % k == 0:
            n = n//k
        else:
            n = n % k
    return n

a = Counter(prime_factors(N))
b = Counter(prime_factors(N-1))
c = make_divisors(N)

answer = 1
for value in b.values():
    answer *= (value+1)

answer -= 1

for x in c:
    if sub_div(N, x) == 1:
        answer += 1

print(answer)

Solution (Python):
n = int(input())
ans = 1

for k in range(2, int(n ** 0.5) + 1):
    if n % k != 0:
        continue
    if (n // k) % k == 1:
        ans += 1
for i in range(2, 41):
    for k in range(2, n + 1):
        x = k ** i
        if x > n:
            break
        if n % x != 0:
            continue
        if (n // x) % k == 1:
            ans += 1
n -= 1
for k in range(1, int(n ** 0.5) + 1):
    if n % k != 0:
        continue
    if k * k == n or k == 1:
        ans += 1
    else:
        ans += 2
if(n == 1):
    ans -= 1
print(ans)

Solution (Python):
n=int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

tmp=make_divisors(n-1)
tmp.remove(1)
ans=set(tmp)
cnt=make_divisors(n)
cnt.remove(1)
for i in range(len(cnt)):
    k=cnt[i]
    gh=n
    while(gh%k==0):
        gh//=k
    if gh%k==1:
        ans.add(k)

print(len(ans))

Solution (Python):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)                
                
    divisors.sort()
    return divisors

n = int(input())
num = 0

num += len(make_divisors(n-1))-1

k = make_divisors(n)
k.pop(0)

for item in k:
  tn = n
  while tn % item == 0:
      tn /= item
    
  if tn % item == 1:
    num += 1

print(num)

Solution (Python):
n = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

a = make_divisors(n-1)
b = make_divisors(n)

a.remove(1)
b.remove(1)

count = len(a)

for i in b:
    n_new = n // i
    while n_new % i == 0:
        n_new = n_new // i
    if n_new % i == 1:
        count += 1

print(count)

Solution (Python):
from collections import deque
def deque_divisor(n):
    d = deque()
    for i in range(int(n**(1/2)),0,-1):
        if i**2 == n:
            d.append(i)
            continue
        if n % i == 0:
            d.appendleft(i)
            d.append(n//i)
    return d

n = int(input())

candidate = (set(deque_divisor(n)) | set(deque_divisor(n-1)))
candidate.discard(1)

ans = 0

for i in candidate:
    k = n
    while k % i == 0:
        k //= i
    k %= i
    if k == 1:
        ans += 1

print(ans)

Solution (Python):
import math

N = int(input())

divisor_N1=set()
for i in range(1, math.floor(math.sqrt(N-1)) + 1):
    if (N - 1) % i == 0:
        divisor_N1.add(i)
        divisor_N1.add((N-1) // i)


divisor_N=set()
for i in range(1, math.floor(math.sqrt(N) + 1)):
    if N % i == 0:
        divisor_N.add(i)
        divisor_N.add(N // i)

divisor_N.remove(1)
divisor_N1.remove(1)



cnt = len(divisor_N1)
for num in divisor_N:
    temp = N
    while temp % num == 0:
        temp //= num
    if temp % num == 1:
        cnt += 1
        
print(cnt)

Solution (Python):
N = int(input())
A = []
B = []
for i in range(2,int(N**0.5)+1):
    if N%i==0:
        A.append(i)
        A.append(N//i)
    if (N-1)%i==0:
        B.append(i)
        B.append((N-1)//i)
A.append(N)
if N>2:
    B.append(N-1)
A = sorted(A)
for a in A:
    m = 1
    while True:
        if a**m==N:
            B.append(a)
            break
        elif a**m>N:
            break
        m += 1
for a in A:
    m=0
    while a**m<N:
        if N%a**m==0:
            if (N//(a**m)-1)%a==0:
                B.append(a)
        m += 1
B = sorted(list(set(B)))
print(len(B))

Solution (Python):
def abc(n,i):
    if i==1:
        return 0
    while not n%i:
        n=n//i
    return not (n-1)%i
n=int(input())
e={}
for i in range(1,int(pow(n,0.5))+1):
    if not n%i:
        if abc(n,i):
            e[i]=0
        if abc(n,n//i):
            e[n//i]=0
n-=1

c=0
for i in range(1,int(pow(n,0.5))+1):
    if not n%i:
        c+=1
        if i!=n//i:
            c+=1
print(len(e)+c-1)

Solution (Python):
N = int(input())

divisor = [N]
ans = 0


for i in range(2,N+1,1):
    if i*i < N:
        if N % i == 0:
            divisor.append(i)
            divisor.append(N//i)
    elif i*i == N:
        divisor.append(i)
    else:
        break


yakusuuu = [N-1]
for i in range(2,N,1):
    if i*i < (N-1):
        if (N - 1)% i == 0:
            yakusuuu.append(i)
            yakusuuu.append((N-1)//i)
    elif i*i == (N-1):
        yakusuuu.append(i)
    else:
        break

for i in yakusuuu:
    if N % i == 1:
        ans += 1




M = N

for K in divisor:
    
    while M % K == 0:
        M = M//K

    

    if M == 1:
        ans += 1
        
    else:
        M =  M % K
        if M == 1:
            ans += 1 
    
    M = N
        




print(ans)

Solution (Python):
def divisors(N):
    U = int(N ** 0.5) + 1
    L = [i for i in range(1, U) if N % i == 0]
    return L + [N // i for i in reversed(L) if N != i * i]

def solve(k):
    n = N
    while n % k == 0:
        n //= k
    return (n % k == 1)

N = int(input())

K = set(divisors(N) + divisors(N - 1)) - {1}
print(sum(solve(k) for k in K))

Solution (Python):
def divisors(N):
    U = int(N ** 0.5) + 1
    L = [i for i in range(1, U) if N % i == 0]
    return L + [N // i for i in reversed(L) if N != i * i]

def solve(k):
    n = N
    while n % k == 0:
        n //= k
    return (n % k == 1)

N = int(input())

K = set(divisors(N) + divisors(N - 1)) - {1}
print(sum(solve(k) for k in K))

Solution (Python):
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


def divisors(n, sort=False):
    """
    nの約数をO(√n)で列挙する
    """
    d = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            d.append(i)
            if i != n // i:
                d.append(n//i)
    if sort:
        d.sort()
    return d


N = I()

ans = 0
for d in divisors(N - 1):
    if d > 1:
        ans += 1
for d in divisors(N):
    if d == 1:
        continue
    num = N
    while num % d == 0:
        num = num // d
    if num % d == 1:
        ans += 1
print(ans)

Solution (Python):
def main():
    n = int(input())
    ans = 0
    m = n - 1
    num = 1
    while num * num <= m:
        if m % num == 0:
            if num > 1:
                ans += 1
            if m // num != num:
                ans += 1
        num += 1
    num = 1
    while num * num <= n:
        if n % num == 0:
            tmp = n
            while num > 1 and tmp % num == 0:
                tmp = tmp // num
            if tmp == 1 or tmp % num == 1:
                ans += 1
            rest = n // num
            if rest != num:
                tmp = n
                while tmp % rest == 0:
                    tmp = tmp // rest
                if tmp == 1 or tmp % num == 1:
                    ans += 1
        num += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

def f(x):
  out=set() 
  for i in range(1, int(-(-pow(x, 1/2)//1))):
    
    if x%i==0:
      
      out.add(i)
      out.add(x//i)
      
  
  if x%(x**(1/2))==0:
    out.add(x**(1/2))
    
  
  out=list(out)
  out.sort()
  
  
  return out[1:]


N=int(input())
ans=0 

for K in f(N): 
    x=N 
    
    while x%K==0:
      x/=K
      
    
    x%=K
    
    
    if x==1:
        ans+=1
        

ans+=len(f(N-1))


print(ans)

Solution (Python):
n=int(input())
ans=0
nmcc=0
i=1
d=[]
while i*i<=n:
  if n%i==0:
    d.append(i)
    if i*i!=n:
      d.append(n//i)
  i+=1
for i in d:
  if i==1:
    continue
  tmp=n
  while tmp%i==0:
    tmp//=i
  tmp%=i
  if tmp==1:
    ans+=1

i=1
while i*i<=(n-1):
  if (n-1)%i==0:
    nmcc+=1
    if i*i!=n-1:
      nmcc+=1
  i+=1
nmcc-=1
print(ans+nmcc)

Solution (Python):
n=int(input())
ans=0
nmcc=0
i=1
d=[]
while i*i<=n:
  if n%i==0:
    d.append(i)
    if i*i!=n:
      d.append(n//i)
  i+=1
for i in d:
  if i==1:
    continue
  tmp=n
  while tmp%i==0:
    tmp//=i
  tmp%=i
  if tmp==1:
    ans+=1

i=1
while i*i<=(n-1):
  if (n-1)%i==0:
    nmcc+=1
    if i*i!=n-1:
      nmcc+=1
  i+=1
nmcc-=1
print(ans+nmcc)

Solution (Python):
from math import sqrt
from math import ceil
from math import floor

def divisors(n):
	count=0
	lis=[]
	for i in range(1,ceil(sqrt(n))+1):
		if n%i==0:
			if n//i==i:
				count+=1
				lis.append(i)
			else:
				lis.append(i)
				lis.append(n//i)
				count+=2
	lis=set(lis)
	lis.remove(1)
	return lis

def main():
	n=int(input())
	ol=n-1
	ans=0
	case1div=divisors(ol)
	case2div=divisors(n)
	for i in case2div:
		newn=n
		if newn%i==0:
			while newn%i==0:
				newn//=i
		if newn%i==1:
			ans+=1
	ans+=len(case1div)
	print(ans)
main()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return divisors 

ret = 0
a = make_divisors(n)
for k in a:
    if k == 1:
        continue
    m = n
    while m % k == 0:
        m //= k
    if m % k == 1:
        ret += 1

s = make_divisors(n - 1)
s.discard(1)
print(ret + len(s))

Solution (Python):
N=int(input())
n=N
ans=0
def make_divisors(n):
    divisors = []
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n//i:
                divisors.append(n//i)

    return divisors
l=make_divisors(N-1)
r=make_divisors(N)
ans=len(l)-1
for i in range(len(r)):
    N=n
    K=r[i]
    if K==1:
        continue
    while(N%K==0):
        N=N//K
    if N%K==1:
        
        ans+=1
print(ans)

Solution (Python):
"""from collections import *
from heapq import *
from itertools import *
from fractions import gcd

from decimal import *
import copy
from bisect import *
import time"""
import sys
sys.setrecursionlimit(10**7)
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
if 2<=N<=4:
    if N==2:
        print(1)
    if N==3:
        print(2)
    if N==4:
        print(2)
    exit()
count=2
visited=set()
for K in range(2,round(N**.5)+1):
    n=N
    while n%K==0:
        n//=K
    count+=n%K==1
    visited.add(K)

lst=[]
X=round(N**.5)+1
for i in range(2,round(N**.5)+1):
    if (N-1)%i==0:
        if not i in visited:
            lst.append(i)
        C=(N-1)//i
        if not C in visited:
            lst.append(C)



for K in lst:
    n=N
    while n%K==0:
        n//=K
    count+=n%K==1
    visited.add(K)
print(count)
"""
for K in C:
    n=N
    while n>=K:
        if n%K==0:
            n//=K
        else:
            n-=K
    if n==1:
        print(K,"KK")
"""

Solution (Python):
n=int(input())
a=n>2
for i in range(2,int(n**.5)+1):
 m=n
 while m%i<1:m//=i
 a+=(m%i<2)+(~-n%i<(i<~-n//i))
print(a+1)

Solution (Python):
N=int(input())
def F(n):
    A=[]
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            A.append(i)
            if i != n // i:
                A.append(n//i)
    return A
D=F(N-1)
E=F(N)
E=sorted(E)
G=[]
for i in E[1:]:
  a=N
  while a%i==0:
    a//=i
  if a%i==1:
    G.append(i)
print(len(G)+len(D)-1)

Solution (Python):

import math
N = int(input())

m = int(math.sqrt(N-1))
Myaku = []
for i in range(1,m+1):
    if (N-1)%i == 0:
        if i != 1:
            Myaku.append(i)
        if (N-1)//i != i:
            Myaku.append((N-1)//i)
            
ans = len(Myaku)

n = int(math.sqrt(N))
Nyaku = []
for i in range(1,n+1):
    if N%i == 0:
        if i != 1:
            Nyaku.append(i)
        if N//i != i:
            Nyaku.append(N//i)
            
for ny in Nyaku:
    X = N
    while X%ny == 0:
        X //= ny
    if X%ny == 1:
        ans+=1
        
print(ans)

Solution (Python):

import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    def divisors(x):
        r1 = deque()
        r2 = deque()
        for i in range(1,ceil(x**0.5)):
            if x % i == 0:
                r1.append(i)
                r2.appendleft(x//i)
        if int(x**0.5) == x**0.5:
            r1.append(int(x**0.5))
        return list(r1)+list(r2)
    
    ans = len(divisors(N-1))-1
    
    
    for d in divisors(N)[1:]:
        tmpN = N
        while tmpN % d == 0:
            tmpN //= d
        if tmpN % d == 1:
            ans += 1

            
            
    print(ans)


    

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
"""
6:3
3141:13
314159265358:9
"""

def make_divisors(n):  
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    
    return divisors
r = len(make_divisors(n-1)) - 1
w = make_divisors(n)
for wi in w:
  if wi == 1:
    continue
  i = 1
  while n % (wi**i) == 0:
    i += 1
  if (n / (wi**(i-1))) % wi == 1:
    r += 1
print(r)

Solution (Python):
n = int(input());div=[];ans=[]
for i in range(1,int(n**0.5)+2):
  if n%i == 0:
    div.append(i);div.append(n//i)
    
for i in div:
  if i == 1:
    continue
  tmp = n
  while tmp % i == 0:
    tmp //= i
  if tmp % i ==1:
    ans.append(i)
    
n -= 1
for i in range(1,int(n**0.5)+2):
  if n%i == 0:
    ans.append(i);ans.append(n//i)
    
print(len(set(ans))-1)

Solution (Python):
n = int(input())
if n == 2:
    print(1)
    exit()
def ele(n):
    L = [n]
    for i in range(2, int(n**0.5)+1):
        cur = n
        while cur%i == 0:
            cur = cur//i
            L.append(i)
            L.append(n//i)
    L = list(set(L))
    return L
ans = ele(n-1)
t = ele(n)
for i in range(len(t)):
    temp = n
    while temp%t[i] == 0:
        temp = temp//t[i]
    if temp%t[i] == 1:
        ans.append(t[i])
print(len(ans))

Solution (Python):
import math

def get_divisor(n):
    sn = math.sqrt(n)
    i = 1
    divisor = []
    while i <= sn:
        if n % i == 0:
            divisor.append(i)
            if i != n // i:
                divisor.append(n // i)
        i += 1
    return divisor

n = int(input())
if n == 2:
    print(1)
    exit()
d1 = get_divisor(n)
d2 = get_divisor(n - 1)
ans = -1
for i in d1:
    tmp = int(n)
    if i == 1:
        continue
    while tmp % i == 0:
        tmp //= i
    if tmp % i == 1:
        ans += 1
ans += len(d2)
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline

def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


n = int(input())
div = divisors(n)
div2 = divisors(n-1)

ans = 0
for d in div[1:]:
    tmp = n
    while tmp % d == 0:
        tmp //= d
    if tmp % d == 1:
        ans += 1

print(ans + len(div2) - 1)

Solution (Python):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

def l_b(x):
  ok = 0
  ng = 40
  while ng - ok > 1:
    mid = (ok+ng) // 2
    if n % (k ** mid) == 0:
      ok = mid
    else:
      ng = mid
  return x ** ok
n = int(input())
L = make_divisors(n)
ans = 0
for k in L:
  if k == 1:
    continue
  k_m = l_b(k)
  if (n // k_m) % k == 1:
    ans += 1
ans += len(make_divisors(n-1))
ans -= 1
print(ans)

Solution (Python):
def make_divisors(n):
    lsls=[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            lsls.append(i)
            if i!=n//i:
                lsls.append(n//i)
    lsls.sort()
    return lsls

N=int(input())

ans=1
for K in range(2,min(N,int(N**0.5)+2)):
    num=N
    while num%K==0:
        num//=K
    if num>=K:
        num%=K
    if num==1:
        ans+=1

lst=make_divisors(N-1)

for u in lst:
    if u>=int(N**0.5)+2:
        ans+=1
        
print(ans)

Solution (Python):
from itertools import *
from collections import *
from functools import *

def isqrt(n):
  if n > 0:
    x = 1 << (n.bit_length() + 1 >> 1)
    while True:
      y = (x + n // x) >> 1
      if y >= x:
        return x
      x = y
  elif n == 0:
    return 0
  else:
    raise ValueError

def qrime():
  yield from [2, 3, 5, 7]
  q = [i for i in range(1, 210, 2) if 0 not in (i%3, i%5, i%7)]
  yield from q[1:]
  for i in count(210, 210):
    for j in q:
      yield i + j

def factor(n):
  p = Counter()
  limit = isqrt(n)
  for q in qrime():
    if q > limit:
      break
    while n % q ==0:
      p[q] += 1
      n //= q
    if q in p:
      limit = isqrt(n)
  if n != 1:
    p[n] += 1
  return p

def divisor(n):
  p, m = zip(*factor(n).items())
  for c in product(*map(lambda x:range(x+1), m)):
    yield reduce(int.__mul__, (x**y for x, y in zip(p, c) if y), 1)

N = int(input())
ans = reduce(int.__mul__, (c+1 for c in factor(N-1).values()), 1) - 1

for d in divisor(N):
  if d == 1:
    continue
  n = N
  while n % d == 0:
    n //= d
  if n % d == 1:
    ans += 1

print(ans)

Solution (Python):
n=int(input())
p=n
yakusu=[]
for i in range(1,int(n**0.5)+1):
	if n%i==0:
		yakusu.append(i)
		if i!=n//i:
			yakusu.append(n//i)
p-=1
yakusu_1=[]
for i in range(1,int(p**0.5)+1):
	if p%i==0:
		yakusu_1.append(i)
		if i!=p//i:
			yakusu_1.append(p//i)
ans=len(yakusu_1)-1
for x in yakusu:
	r=n
	if x!=1:
		while r%x==0:
			r//=x
		if (r-1)%x==0:
			ans+=1
print(ans)

Solution (Python):
import math

def divisors(n):
    div = [n]
    for i in xrange(2,int(math.sqrt(n))+1):
        if n%i == 0:
            div.append(i)
            div.append(n/i)
    return div

n = int(raw_input())
ndiv = set(divisors(n))
mdiv = set(divisors(n-1))
count = 0
for x in ndiv:
    for k in xrange(1,41):
        if x**k > n:
            break
        if (n%x**k)==0 and (n/x**k)%x == 1:
            count += 1
            
            break
count += len(mdiv)
if n==2:
    count = 1
print count

Solution (Python):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

n = int(input())
ans = len(make_divisors(n - 1)) - 1
for x in make_divisors(n):
  if x == 1:
    continue
  m = n
  while m % x == 0:
    m //= x
  if m % x == 1:
    ans += 1
print(ans)

Solution (Python):
from itertools import *
from collections import *
from math import *
def qrime():
  p = [2, 3, 5, 7]
  yield from p
  q = [i for i in range(1, 210, 2) if 0 not in (i%3, i%5, i%7)]
  yield from q[1:]
  for i in count(210, 210):
    for j in q:
      yield i + j

def factor(n):
  limit = int(sqrt(n))
  p = Counter()
  for q in qrime():
    if n == 1 or q > limit:
      break
    while n % q ==0:
      p[q] += 1
      n //= q
      limit = int(sqrt(n))
  if n != 1:
    p[n] += 1
  return p

def divisor(n):
  f = factor(n)
  p, m = zip(*f.items())
  for c in product(*map(lambda x:range(x+1), m)):
    if sum(c) == 0:
      continue
    C = 1
    for a, b in zip(p, c):
      C *= pow(a, b)
    yield C

ans = 0
N = int(input())
for d in divisor(N):
  n = N
  while n % d == 0:
    n //= d
  if n % d == 1:
    ans += 1

f = factor(N-1)
ans2 = 1
for c in f.values():
  ans2 *= c+1

print(ans + ans2 - 1)

Solution (Python):
def Divisor(n):
    res = []
    for i in range(1, int(n**0.5)+1):
      if n % i != 0: continue
      res.append(i)
      if i*i != n: res.append(n//i)
    return res

n = int(input())


ans = 0
for x in Divisor(n):
    if x == 1: continue
    tmp = n
    while (tmp % x == 0):
        tmp /= x
    tmp %= x    
    if tmp == 1: 
      ans += 1
      

ans += len(Divisor(n-1))-1
print(ans)

Solution (Python):

N = int(input())


def solve(num):
    ret = set()

    p = 1
    while p * p <= num:
        if num % p == 0:
            ret.add(p)
            ret.add(num // p)
        p += 1

    return ret


s1 = solve(N)
s2 = solve(N-1)




ans = len(s2) - 1
for n in s1:
    if n == 1:
        continue
    tmp = N
    while tmp % n == 0:
        tmp = tmp // n
    if tmp % n == 1:
        ans += 1


print(ans)

Solution (Python):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
n=int(input())
nlist=make_divisors(n)
n1list=make_divisors(n-1)


answer=len(n1list)-1
for i in nlist[1:len(nlist)]:
    pra=n
    while (pra%i==0):
        pra=pra/i
    if pra%i==1:
        answer+=1
print(answer)

Solution (Python):
N = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    
    return divisors

K = []



K1 = make_divisors(N)
K1.pop(0)


for k in K1:
    
    n=0
    while N-k**n >= 0:
        
        
        if (N-k**n)%(k**(n+1))==0:
            K.append(k)
        n += 1



K2 = make_divisors(N-1)
K2.pop(0)
K += K2



print(len(K))

Solution (Python):
from collections import defaultdict

N = int(input())
X, Y = N-1, N
dic = defaultdict(int)
for p in range(2, int(N**0.5)+1):
    if X % p == 0:
        cnt = 0
        while X % p == 0:
            X //= p
            cnt += 1
        dic[p] = cnt
    if Y % p == 0:
        cnt = 0
        while Y % p == 0:
            Y //= p
            cnt += 1
        dic[p] = cnt
if X > 1:
    dic[X] = 1
if Y > 1:
    dic[Y] = 1
f = [1]
for p in dic.keys():
    f += [x*pow(p, c) for x in f for c in range(1, dic[p]+1)]
ans = 0
for x in f:
    if x == 1:
        continue
    y = N
    while y % x == 0:
        y //= x
    if y % x == 1:
        ans += 1
print(ans)

Solution (Python):
def get_divisors(n):
    """
    引数の数字の約数を列挙し、setで返します。1および引数自身を含みます。
    計算量はO(log(n))です。
    """
    divisors = set()
    i = 1
    while i * i <= n:
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
        i += 1
    return divisors


n = int(input())

n_ = get_divisors(n)
n_1 = get_divisors(n - 1)
n_.remove(1)
n_1.remove(1)
n_.difference_update(n_1)



ans = len(n_1)
for cand in n_:
    if cand == 2 or cand == n:
        ans += 1
        continue
    tmp = n
    while tmp % cand == 0:
        tmp //= cand
    tmp %= cand
    if tmp == 1:
        ans += 1
print(ans)

Solution (Python):


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def divisors(N: int) -> set:
    from math import sqrt

    s = {1, N}
    for i in range(2, int(sqrt(N))+1):
        if N % i == 0:
            s.add(i)
            s.add(N // i)
    return s

def check(n, k):
    if k == 1:
        return False
    while n >= k:
        if n % k == 0:
            n //= k
        else:
            n %= k
    return n == 1

N = INT()

divs = divisors(N) | divisors(N-1)

ans = 0
for k in divs:
    if check(N, k):
        ans += 1
print(ans)

Solution (Python):
import math
N=int(input())
if N==2:
  print(1)
  exit()
def yaku(n):
    a=set()
    s=int(math.sqrt(n))
    for i in range(2,s+1):
        if n%i==0:
            a.add(i)
            a.add(n//i)
    return a
ans=len(yaku(N-1))+1
a=yaku(N)
for i in a:
    n=N
    while n%i==0:
        n=n//i
    if n%i==1:
        ans+=1
print(ans+1)