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):
def main():
  n = int(input())
  ans = 0
  for k in divisors(n):
    if k == 1:
      continue
    if check(n, k):
      ans += 1
  ans += len([None for k in divisors(n-1) if k != 1])
  print(ans)

def check(original_n, k):
  n = original_n
  while n % k == 0:
    n = n // k
  n = n % k
  return n == 1

def divisors(n):
  result = []
  for i in range(1, n+1):
    if i*i > n:
      break
    if n%i == 0:
      result.append(i)
      d = n // i
      if d != i:
        result.append(d)
  return result


main()

Solution (Python):
from collections import Counter
from functools import reduce
from itertools import product
from math import gcd
from operator import mul
from random import randrange


class PrimeFactor:
    def __init__(self):
        pass

    def is_prime(self, N):
        """ミラーラビン"""
        v = [2, 7, 61] if N < 4_759_123_141 else \
            [2, 3, 5, 7, 11, 13, 17] if N < 341_550_071_728_321 else \
            [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
        if N < 2:
            return False
        if N in v:
            return True
        d = N - 1
        s = 0
        while d % 2 == 0:
            d //= 2
            s += 1

        for a in v:
            if pow(a, d, N) != 1:
                ok = True
                for r in range(s):
                    if pow(a, d * 1 << r, N) == N - 1:
                        ok = 0
                        break
                if ok:
                    return False
        return True

    def f(self, x, n, c):
        return (x * x + c) % n

    def get_factor(self, n):
        c = randrange(1, n)
        if n % 2 == 0:
            return 2
        if self.is_prime(n):
            return n
        x = randrange(1, n)
        y, d = x, 1

        while d == 1:
            x = self.f(x, n, c)
            y = self.f(self.f(y, n, c), n, c)
            d = gcd(abs(x - y), n)
        if d == n:
            return self.get_factor(n)
        return self.get_factor(d)

    def factorization(self, N):
        """素因数分解"""
        if N == 1:
            return [1]
        arr = []
        while N > 1:
            k = self.get_factor(N)
            cnt = 0
            while N % k == 0:
                cnt += 1
                N //= k
                arr.append(k)
        return arr

    def divisors(self, N):
        """約数列挙"""
        if N == 1:
            return [1]
        c = Counter(self.factorization(N))
        mul_list = []
        for i in c:
            tmp = [1] * (c[i] + 1)
            for j in range(c[i]):
                tmp[j + 1] = tmp[j] * i
            mul_list.append(tmp)
        res = [reduce(mul, v) for v in product(*mul_list)]
        return res

    def count_divisors(self, N):
        """約数の個数"""
        if N == 1:
            return 1
        res = 1
        for i in Counter(self.factorization(N)).values():
            res *= i + 1
        return res


n = int(input())
p = PrimeFactor()
a = p.divisors(n)[1:]
ans = 0
for i in a:
    k = n
    while k % i == 0:
        k //= i
    if k % i == 1:
        ans += 1
ans += p.count_divisors(n - 1) - 1
print(ans)

Solution (Python):


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


N = int(input())


div1 = make_divisors(N)

div2 = make_divisors(N - 1)


div_set = set(div1 + div2)
div_set.remove(1)




ans = 0
for div in div_set:
    tmp = N
    while tmp % div == 0:
        tmp = tmp // div

    if tmp % div == 1:
        ans += 1
print(ans)

Solution (Python):


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


N = int(input())
div1 = make_divisors(N)
div2 = make_divisors(N - 1)
div_set = set(div1 + div2)
div_set.remove(1)

ans = 0
for div in div_set:
    tmp = N
    while tmp % div == 0:
        tmp = tmp // div

    if tmp % div == 1:
        ans += 1
print(ans)

Solution (Python):
N = int(input())
if N == 2:
    print(1)
    exit()
ans = 1
divisors = []
d = 2
while d*d < N:
    if N % d == 0:
        divisors.append(d)
        divisors.append(N//d)
    d += 1
if d*d == N:
    divisors.append(d)

for d in divisors:
    dummyN = N
    while dummyN % d == 0:
        dummyN //= d
    if dummyN % d == 1:
        ans += 1

N -= 1
divisors = []
d = 2
while d*d < N:
    if N % d == 0:
        divisors.append(d)
        divisors.append(N//d)
    d += 1
if d*d == N:
    divisors.append(d)

ans += len(divisors)+1
print(ans)

Solution (Python):
def divisors(n):
    i = 1
    table = set()
    while i * i <= n:
        if not n % i:
            table.add(i)
            table.add(n//i)
        i += 1
    table = list(table)
    return table
N = int(input())
k = 2
res = 0
while k*k<=N:
    n = N
    while not n%k:
        n//=k
    if (n%k==1 or n==1) and n!=N:
        res += 1
    k += 1
a = divisors(N-1)
print(len(a)+res)

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

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


ans = 1

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

d = make_divisors(n)
for k in range(1,(len(d)+1)//2):
    i = d[k]
    j = n//i
    while j % i == 0:
        j //= i
    if j % i == 1:
        ans += 1

print(ans)

Solution (Python):
"""
一回以上わるとき、KはNの約数なので、Nの約数を全通り試して1に持っていけるかどうかを検証する。
Nを一回も割らずに1まで持っていけるようなKは、N-1の約数の数だけ存在する。
それぞれカウントすればよい
"""
N = int(input())
ans = 0
if N == 2:
    print(1)
    exit()

divisers = [N]
d = 2
while d*d < N:
    if N % d == 0:
        divisers.append(d)
        divisers.append(N//d)
    d += 1
if d**2 == N:
    divisers.append(d)

for d in divisers:
    dummyN = N
    while dummyN%d == 0:
        dummyN //= d
    if dummyN % d == 1:
        ans += 1

N -= 1
divisers = [N]
d = 2
while d*d < N:
    if N % d == 0:
        divisers.append(d)
        divisers.append(N//d)
    d += 1
if d**2 == N:
    divisers.append(d)

ans += len(divisers)

print(ans)

Solution (Python):
import math
import sys
N = int(input())
if N == 2:
  print(1)
  sys.exit()

def get_divisors(x):
  lim = math.ceil(math.sqrt(x))
  divisors = set()
  for i in range(1,lim+1):
    if x % i == 0:
      divisors.add(i)
      divisors.add(N//i)    
  return divisors
    
ans_1 = 0

divisors = get_divisors(N)
for d in divisors:
  if d == 1: continue
  N_try = N
  while N_try % d == 0:
    N_try //= d
  if N_try % d == 1:
    ans_1 += 1
    

divisors = get_divisors(N-1)
ans_2 = len(divisors)-1
    

print(ans_1+ans_2)

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

def f(x):
  m=int(x**(1/2))
  ret=set()
  for i in range(1,m+1):
    if x%i==0:
      ret.add(i)
      ret.add(x//i)
  return ret


ans=set()
for i in f(n):
  if i==1:
    continue
  g=n
  while g%i==0:
    g=g//i
  if g%i==1:
    ans.add(i)

for j in f(n-1):
  if j==1:
    continue
  if j in ans:
    continue
  ans.add(j)
  
print(len(ans))

Solution (Python):
"""
Nが1になるようなKは、
・K^x = NになるようなKか
・K^x(K*y+1) = N になるようなKである。
後者は前者を包括するので、後者についてのみカウントすればよい。
Kの数を求めるために、後者をさらに2種類に分ける
・x > 0の場合
・x == 0の場合
前者の場合、KはNの約数なので、Nの約数全部に関して条件を満たすか調べればよい。Nの約数はそんなに多くならないので、時間はかからない。
後者の場合だと、KはN-1の約数の数だけ存在するのでN-1の約数の数を求めればよい。
"""
from collections import Counter

def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

N = int(input())
ans = 0


devisers = []
d = 2
while d*d < N:
    if N % d == 0:
        devisers.append(d)
        devisers.append(N//d)
    d += 1
if d*d == N:
    devisers.append(d)

for d in devisers:
    dummyN = N
    while dummyN % d == 0:
        dummyN //= d
    if dummyN%d == 1:
        ans += 1




tmp = []
dummyN = N-1
ceil = int(dummyN**0.5)
for d in range(2,ceil+1):
    while dummyN % d == 0:
        tmp.append(d)
        dummyN //= d
if dummyN != 1:
    tmp.append(dummyN)
    dummyN //= dummyN

divideN = Counter(tmp)
commonDCnt = 1
for v in divideN.values():
    commonDCnt *= (v+1)
ans += commonDCnt

print(ans)

Solution (Python):
N = int(input())
from math import sqrt

def divisor(num):
    max_num = int(sqrt(num))
    divisor_list = []
    for i in range(1, max_num + 1):
        if num % i == 0:
            divisor_list.append(i)
            divisor_list.append(num//i)
    return divisor_list

K0 = divisor(N)
K1 = divisor(N-1)
S = set(K1)
S.remove(1)
for k in K0:
    tmp = N
    if k == 1:
        continue
    while tmp % k == 0 and tmp >= k:
        tmp //= k
    if tmp % k == 1:
        S.add(k)
print(len(S))

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())



def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def main():
    N = in_n()

    yaku = make_divisors(N)
    yaku.remove(1)

    ans = 0
    for x in yaku:
        tn = N
        while tn % x == 0:
            tn /= x
        if tn % x == 1:
            ans += 1

    yaku = make_divisors(N - 1)
    yaku.remove(1)
    ans += len(yaku)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def divisors(n,TF):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if TF == 1:
                if i != n // i:
                    divisors.append(n//i)
    return divisors
N = int(input())
if N == 2:
    print(1)
    sys.exit()

ans = len(divisors(N - 1, 1)) + 2
A = divisors(N, 0)
for i in A:
    x = N
    while x % i == 0:
        x //= i
    if x % i == 1:
        ans += 1
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    ans = 2-(n==2)
    for k in range(2,int(n**0.5)+1):
        if n % k == 1:
            ans += 2
            ans -=k**2+1==n
        elif n % k == 0:
            g = n//k
            while g % k == 0:
                g = g//k
            ans += g % k == 1
    
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def make_divisors(n: int):
    lower_divs = []
    upper_divs = []
    i = 1
    while i**2 <= n:
        if n % i == 0:
            lower_divs.append(i)
            if i != n // i:
                upper_divs.append(n // i)
        i += 1
    return lower_divs + upper_divs[::-1]


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

print(ans)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N = I()
B = make_divisors(N - 1)
b = len(B)

A = make_divisors(N)

cnt = 0
for i in range(1, len(A) // 2 + 1):
    x = A[i]
    y = A[-i - 1]
    while y > x:
        if (y - 1) % x == 0:
            cnt += 1
            break
        elif y % x == 0:
            y //= x
        else:
            break
    if y == x:
        cnt += 1

ans = b - 1 + cnt + 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()

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

        return res

    ans = 0
    ans += len(divisors(N-1)) - 1

    for k in divisors(N)[1:]:
        n = N
        while n % k == 0:
            n //= k
        if n % k == 1:
            ans += 1
    
    print(ans)




if __name__ == "__main__":
    main()

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

    def enum_divisors(n):
        
        divs = []
        for i in range(1, n+1):
            if i*i > n:
                break
            if n % i == 0:
                divs.append(i)
                if n//i != i:
                    
                    divs.append(n//i)
        return divs

    ans = 0
    for k in enum_divisors(N-1):
        if 2 <= k:
            ans += 1

    for k in enum_divisors(N):
        if 2 <= k:
            n = N
            while n > 1 and n % k == 0:
                n //= k
            if n % k == 1:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

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

ans = []

for i in range(1,round((N-1)**0.5)+1):
  if (N-1)%i == 0:
    ans.append(i)
    if (N-1)//i != i:
      ans.append((N-1)//i)

ans.remove(1)
ans.append(N)
for i in range(2,round(N**0.5)+1):
  if N%i == 0:
    n = N
    while n%i==0:
      n//=i
    if n%i==1:
      ans.append(i)

print(len(ans))

Solution (Python):
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

def solve(N):
    if N == 2:
        print(1)
        return
    Ans = [N, N-1]
    for base in range(2, N):
        if base * base > N:
            break
        n = N
        while n % base == 0:
            n //= base
        if n % base == 1:
            Ans.append(base)
        if (N-1) % base == 0:
            Ans.append(base)
            Ans.append((N-1)//base)
    if int(N**0.5)**2 == N:
        Ans.append(int(N**0.5))
    print(len(set(Ans)))

numba_compile([
    [solve, "void(i8)"],
])

N = int(input())
solve(N)

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

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

ans = 0

d = []
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):
import math
N = int(input())

N_d = []
N1_d = []
answer = set()
for i in range(1,math.ceil(N**0.5)+1):
    if N%i == 0:
        N_d.append(i)
        N_d.append(N//i)

for i in range(len(N_d)):
    temp = N
    while temp % N_d[i] == 0:
        temp = temp//N_d[i]
        if N_d[i] == 1:
            break
        
    if temp % N_d[i] == 1:
        answer.add(N_d[i])


for i in range(1,math.ceil((N-1)**0.5)+1):
    if (N-1) %i == 0:
        answer.add(i)
        answer.add((N-1)//i)

answer.remove(1)
print(len(answer))

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def ccc(v, k):
	while v >= k:
		if v % k == 0:
			v = v // k
		else:
			v = v % k
	return v

def cccc(v,k):
	while v >= k:
		if v % k == 0:
			v = v //k
		else:
			v = v-k
	return v


def main_p(n):
	s = n
	
	
	if s == 2:
		return 1
	elif s == 3:
		return 2
	
	ret = 1  
	for i in range(2, s-1):
		if i*i > s+1:
			break
		if (s-1) % i == 0:
			ret += 1 if i*i == s-1 else 2
			
	ret += 1 
	for i in range(2, s):
		if i*i > s+1:
			break
			
		if s % i == 0:
			if ccc(s, i) == 1:
				ret += 1
			oi = s // i
			if oi != i and ccc(s, oi) == 1:
				ret += 1
			
	return ret
	
		
def main():
	n = int(input())
	return main_p(n)

def main_g(n):
	ret = 0
	for i in range(2, n+1):
		if cccc(n, i) == 1:
			ret += 1
	return ret


def maint():
	i=2
	p=0
	g=0
	while p == g:
		p=main_p(i)
		g=main_g(i)
		i+=1
		if p==g:
			print('ok', i-1)
	print(i-1,p,g)
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):

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


N = int(input())
ans = len(calc_divisor(N - 1)) - 1

cand = sorted(calc_divisor(N))[1:]
for k in cand:
    x = N
    while x % k == 0:
        x //= k
    if x % k == 1:
        ans += 1

print(ans)

Solution (Python):
import copy


def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 2
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1] + [n]


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


n = int(input())
if n == 2:
    print(1)
    exit()

div1 = make_divisors(n-1)
cnt = len(div1)

div2 = make_divisors(n)


for i in div2:
    x = copy.deepcopy(n)
    while x >= i:
        if x % i == 0:
            x //= i
        else:
            break
    if x == 1 or x % i == 1:
        cnt += 1

print(cnt)

Solution (Python):
import copy


def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 2
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1] + [n]


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


n = int(input())
if n == 2:
    print(1)
    exit()

div1 = make_divisors(n-1)
cnt = len(div1)

div2 = make_divisors(n)


for i in div2:
    x = copy.deepcopy(n)
    while x >= i:
        if x % i == 0:
            x //= i
        else:
            break
    if x == 1 or x % i == 1:
        cnt += 1

print(cnt)

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

if n == 2:
    print(1)
    exit()
num = n - 1
cnt = 1
lst = [n]
for i in range(2, int(n ** 0.5) + 1):
    if num % i == 0:
        cnt += 2
        if num == i ** 2:
            cnt -= 1
    if n % i == 0:
        lst.append(i)
        if n != i ** 2:
            lst.append(n // i)
for num in lst:
    n2 = n
    while n2 % num == 0:
        n2 //= num
    if n2 % num == 1:
        cnt += 1
print(cnt)

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

"""
引き算のみ
N mod K == -1
N-1 mod K == 0
K はN-1の約数

割り算が含まれる
KはNの約数
大した個数ないので、確かめる。
"""

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

A = make_divisors(N-1)
B = make_divisors(N)
ANS = set(A)
for b in B:
  if b <= 1:
    continue
  wk = N
  while wk % b == 0:
    wk = wk // b
  if wk % b == 1:
    ANS.add(b)
    
print(len(ANS)-1)

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

if N == 2:
  print(1)
  exit()

S = set([N-1])
lst = [N]
i = 2
while i*i <= N-1:
  if (N-1) % i == 0:
    S.add(i)
    S.add((N-1)//i)
  i += 1  
  
i = 2
while i*i < N:
  if N % i == 0:
    lst.append(i)
    lst.append(N//i)
  i += 1
    
if i*i == N:
  lst.append(i)
  
lst.sort()

for l in lst:
  if l in S:
    continue
  _N = N
  while _N % l == 0:
    _N //= l
  if _N % l == 1:
    S.add(l)
    
print(len(S))

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


C = set(make_divisors(N) + make_divisors(N-1))
C.discard(1)


def f(x, k):
    if x % k == 0:
        return x//k
    else:
        return x % k


ans = 0
for i in C:
    x = N
    c = 0
    while x >= i:
        c += 1
        x = f(x, i)
    if x == 1:
        ans += 1

print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





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

N = getN()












ans = set()
for i in make_divisors(N - 1):
    if i != 1:
        ans.add(i)


def dividor(x, k):
    if k == 1:
        return 0
    n = x
    while True:
        if n % k == 0:
            n //= k
        else:
            break
    return n



for prim in make_divisors(N):
    if prim == 1:
        continue
    
    alta = dividor(N, prim)
    if alta == 1:
        ans.add(prim)
        continue
    if alta >= prim and alta % prim == 1:
        ans.add(prim)

print(len(ans))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





def prime_factorize(n):
    divisors = []
    
    temp = n
    for i in range(2, int(math.sqrt(n)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                
                temp //= i
            divisors.append([i, cnt])
    if temp != 1:
        divisors.append([temp, 1])
    if divisors == []:
        divisors.append([n, 1])

    return divisors

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

N = getN()









ans = set()
for i in make_divisors(N - 1):
    if i != 1:
        ans.add(i)


def dividor(x, k):
    if k == 1:
        return 0
    n = x
    while True:
        if n % k == 0:
            n //= k
        else:
            break
    return n


for prim in make_divisors(N):
    if prim == 1:
        continue
    
    alta = dividor(N, prim)
    if alta == 1:
        ans.add(prim)
        continue
    if alta >= prim and alta % prim == 1:
        ans.add(prim)


ans.add(N)
print(len(ans))

Solution (Python):
def div(n):
    r = int(n**(1/2))
    for i in range(1, r + 1):
        if n % i == 0:
            yield i
            if i*i != n:
                yield n // i


n = int(input())
count = len(list(div(n-1)))-1
for i in div(n):
    if i > 1:
        x = n
        while x % i == 0:
            x //= i
        if x % i == 1:
            count += 1

print(count)

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

sys.setrecursionlimit(1000000)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def divisors(N):
    divs = set([1, N])
    i = 2
    while i ** 2 <= N:
        if N % i == 0:
            divs.add(i)
            divs.add(N//i)
        i += 1
    return sorted(list(divs))

def is_ok(N, K):
    if K <= 1:
        return False
    while N % K == 0:
        N //= K
    return N % K == 1

def main():
    N = I()
    ans = 0

    for divisor in divisors(N-1):
        if is_ok(N, divisor):
            ans += 1

    for divisor in divisors(N):
        if is_ok(N, divisor):
            ans += 1

    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):

N = int(input())


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


cand = len(calc_divisor(N - 1))
divisor_n = calc_divisor(N)
for v in divisor_n:
    x = N
    while x % v == 0:
        x //= v

    if x % v == 1:
        cand += 1

print(cand)

Solution (Python):
n = int(input())
if n==2:print(1);exit()
a = [n]
for i in range(2,int(n**0.5+1)):
    if n%i==0:
        a.append(i)
        if i!=n//i:
            a.append(n//i)
cnt =0
for v in a:
    s = n
    while v<=s and s%v==0:
        s = s//v
    if s%v==1: cnt += 1
b = [n-1]
m = n-1
for i in range(2,int(m**0.5+1)):
    if m%i==0:
        b.append(i)
        if i!=m//i:
            b.append(m//i)
print(cnt + len(b))

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

if N == 2:
  print(1)
  exit()

ans = 0

def factorization(n):
  lis = []
  if n % 2 == 0:
    c = 0
    while n%2 == 0:
      n //= 2
      c += 1
    lis.append([2, c])
  k = 3
  while k*k <= n:
    if n%k == 0:
      c = 0 
      while n%k == 0:
        n //= k
        c += 1
      lis.append([k, c])
    else:
      k += 2
  if n > 1:
    lis.append([n, 1])
  return lis

list1 = factorization(N-1)
ans1 = 1
for k in range(len(list1)):
  ans1 *= list1[k][1]+1
ans += ans1-1

def operation(K):
  n = N
  while n%K == 0:
    n //= K
  if n%K == 1:
    return True
  else:
    return False

list2 = factorization(N)
factorlist = [1]
for l in range(len(list2)):
  list3 = []
  for j in range(list2[l][1]):
    for k in range(len(factorlist)):
      list3.append(factorlist[k]*list2[l][0]**(j+1))
  factorlist += list3
factorlist = factorlist[1:-1]
ans += 1
for item in factorlist:
  if operation(item):
    ans +=1
print(ans)