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 calc_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

def div_or_sub(n, k):
    while k <= n:
        if n % k == 0:
            n //= k
        else:
            n %= k
    return n

n = int(input())
cnt = len(calc_divisors(n - 1)) - 1
n_divisors = calc_divisors(n)
for divisor in n_divisors[1:]:
    if div_or_sub(n, divisor) == 1:
        cnt += 1
print(cnt)

Solution (Python):
from math import sqrt

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

N = int(input())


res = 0
res += len(make_divisors(N-1))
res -= 1 


divisors = make_divisors(N)
divisors.remove(1)
for d in divisors:
    n = N
    while n != 0 and n % d == 0:
        n /= d
    if n % d == 1:
        res += 1

print(res)

Solution (Python):
import sys
from math import sqrt, floor

def divisors(n):
    res = set()
    for i in range(1, floor(sqrt(n)) + 1):
        if not n % i:
            res.add(i)
            res.add(n // i)
    return res - set([1])

n = int(sys.stdin.readline().rstrip())

def main():
    res = divisors(n - 1) 
    cnt = len(res)
    for i in divisors(n):
        m = n
        while not m % i:
            m //= i
        if (m - 1) % i == 0:
            cnt += 1
    print(cnt)

if __name__ ==  '__main__':
    main()

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

k = 2
res = 0

ts = set()
kn = {N}
kn_1 = {N-1}
while k <= math.sqrt(N):
    if N % k == 0:
        nk = N//k
        while nk % k == 0:
            nk //= k

        if nk % k == 1:
            kn.add(k)
        if k % nk == 1:
            kn.add(nk)

        ts.add(k)
        ts.add(nk)

    if (N-1) % k == 0:
        kn_1.add(k)
        kn_1.add((N-1)//k)

    k+=1

kn_1 -= {1}
print(len(kn)+len(kn_1))

Solution (Python):
n,a=int(input()),1
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+(n>2))

Solution (Python):
import sys
from math import sqrt, floor

def divisors(n):
    res = set()
    for i in range(1, floor(sqrt(n)) + 1):
        if n % i == 0:
            res.add(i)
            res.add(n // i)
    return res - set([1])

n = int(sys.stdin.readline().rstrip())

def main():
    res = divisors(n - 1) 
    cnt = len(res)
    for i in divisors(n):
        if i in res: continue
        m = n
        while m % i == 0:
            m //= i
        if (m - 1) % i == 0:
            cnt += 1
    print(cnt)

if __name__ ==  '__main__':
    main()

Solution (Python):
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    N = int(input())
    
    table1 = set()
    i = 1
    while i*i <= N:
        if N%i == 0:
            table1.add(i)
            table1.add(N//i)
        i += 1
    
    cnt = 0
    for p in table1:
        if p == 1:
            continue
        n = N
        while n % p == 0:
            n = n // p
        if n % p == 1:
            cnt += 1
    
    table2 = set()
    N -= 1
    j = 1
    while j*j <= N:
        if N % j == 0:
            table2.add(j)
            table2.add(N//j)
        j += 1

    res = cnt + len(table2) - 1     
    print(res)


if __name__ == '__main__':
    main()

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

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

Solution (Python):
s=set()
a=s.add
def f(n):
  for i in range(1,int(n**.5)+1):
    if n%i<1:
      a(i)
      if i!=n//i:a(n//i)
n=int(input())
f(n-1),f(n)
a=0
for i in s-{1}:
  m=n
  while m%i<1:m//=i
  a+=m%i<2
print(a)

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
  m = n
  while m%i == 0:
    m//=i
  if m%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):
def f(n):
  d=[]
  for i in range(1,int(n**0.5)+1):
    if n%i<1:
      d+=i,
      if i!=n//i:d+=n//i,
  return d[1:]
n=int(input())
a=f(n-1)
for i in f(n):
  m=n
  while m%i<1:m//=i
  if m%i<2:a+=i,
print(len(set(a)))

Solution (Python):
def f(n):
  d=[]
  for i in range(1,int(n**0.5)+1):
    if n%i<1:
      d+=i,
      if i!=n//i:d+=n//i,
  return d[1:]
n=int(input())
a=f(n-1)
for i in f(n):
  m=n
  while m%i<1:m//=i
  if m%i<2:a+=i,
print(len(set(a)))

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

div = []
ans = 0

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

for d in div:
    if d == 1: continue
    tmp = N
    while tmp % d == 0:
        tmp //= d
    if tmp % d == 1:
        ans += 1    

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

print(ans + len(div2)-1)

Solution (Python):
def make_yakusuu(n):
    r_list = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            r_list.append(i)
            r_list.append(n // i)
        i += 1
    return sorted(r_list)
n = int(input())
tmp = make_yakusuu(n)
out = []
for i in tmp:
    m = n
    if i == 1:
        continue
    while m % i == 0:
        m //= i
    if m % i == 1 or m % i == 0:
        out.append(i)

out += make_yakusuu(n - 1)
print(len(set(out)) - 1)

Solution (Python):
import sys,math,copy,queue,itertools,bisect
NI = lambda : int(sys.stdin.readline())
INF = 10**18

N = NI()
if N == 2:
    print (1)
    exit (0)
ans = 0
max_b = int(math.log(N,2))
for x in range(2,int(math.sqrt(N-1))+1):
    if (N-1) % x == 0:
        if (N-1) == x**2:
            ans += 1
        else:
            ans += 2
for x in range(1, int(math.sqrt(N)) + 1):
    if N % x == 0:
        for b in range(1,max_b+1):
            k = round(x**(1/b))
            if k**b == x and k > 1:
                if (N//x-1) % k == 0:
                    ans += 1
            if x**2 != N:
                x = N // x
                k = round(x ** (1 / b))
                if k ** b == x and k > 1:
                    if (N // x - 1) % k == 0:
                        ans += 1

print(ans+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

ans = 2
N = int(input())

div = make_divisors(N)
div_1 = make_divisors(N-1)
ans = 0
for i in div:
    p = N
    if i == 1:
        continue
    while p%i == 0:
        p = p//i
    if p%i == 1:
        ans +=1

print(ans + len(div_1)-1)

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()

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[1:]

d1 = make_divisors(N-1)
answer = len(d1)
d2 = make_divisors(N)
for x in d2:
    M = N
    while M%x == 0:
        M //= x
    if M%x == 1:
        answer += 1

print(answer)

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

def divisor(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)
    
    return d



ls = divisor(n-1)
ls2 = divisor(n)
a1 = len(ls)-1
a2 = 0
for num in ls2:
    cnt = 1
    s = n
    if num ==1:
        continue
    while True:
        if s % num ==0:
            s = s//num
        else:
            if s % num ==1:
                a2 +=1
            break
print(a1+a2)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

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

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


print(ans + len(make_divisors(N-1))-1)

Solution (Python):
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)

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())
out = make_divisors(n)
ans = []
for i in out:
    if i == 1:
        continue
    m = n
    while m % i == 0:
        m //= i
    if m == 1 or m % i == 1:
        ans.append(i)
ans += make_divisors(n - 1)

print(len(set(ans)) - 1)

Solution (Python):
import math

N = int(input())

ans = 0

for i in range(2, N + 1):
    if i * i > N:
        if N == 2:
            ans += 1
        else:
            ans += 2
        break
    if (N - 1) % i == 0:
        ans += 1
        if (N - 1) // i != i:
            ans += 1
    elif N % i == 0:
        cand = [i]
        if N // i != i:
            cand.append(N // i)
        for c in cand:
            tmp = N
            while tmp % c == 0:
                tmp //= c
            if tmp % c == 1:
                ans += 1


print(ans)

Solution (Python):
from math import sqrt


def divisors(x):
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            yield i
            if x // i != i:
                yield x // i


n = int(input())

ans = 0
for e in divisors(n):
    if e == 1:
        continue

    r = n
    while r % e == 0:
        r //= e

    if r % e == 1:
        ans += 1

ans += len(list(divisors(n - 1))) - 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())


ans = make_divisors(N-1)[1:]
n_div = make_divisors(N)[1:]

for d in n_div:
    n = N
    while n % d == 0:
        n //= d
    if n % d == 1:
        ans.append(d)

print(len(ans))

Solution (Python):
def div(x):
    D = set()
    d = 1
    while d*d <= x:
        if x % d == 0:
            D.add(d)
            D.add(x//d)
        d += 1
    return D


n = int(input())
cnt = 0
for d in div(n) | div(n-1):
    if d == 1:
        continue
    tmp = n
    while tmp % d == 0:
        tmp = tmp // d
    if tmp % d == 1:
        cnt += 1
print(cnt)

Solution (Python):
n = int(input())
if n==2: print(1); exit()
Ans = set([n-1])
for i in range(2, int((n-1)**(1/2))+1):
    if (n-1)%i == 0: Ans.add(i); Ans.add((n-1)//i)
Div = set([n])
for i in range(2, int(n**(1/2))+1):
    if n%i == 0: Div.add(i); Div.add(n//i)
for d in Div:
    m = n
    while m%d == 0: m//=d
    if m%d == 1: Ans.add(d)
print(len(Ans))

Solution (Python):
def gen(x):
    root = int(pow(x, 0.5))
    for k in range(1, root + 1):
        if x % k == 0:
            yield k
            if k != x // k:
                yield x // k


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

    
    cnt = sum(1 for _ in filter(lambda x: x > 1, gen(N - 1)))

    
    for k in filter(lambda x: x > 1, gen(N)):
        x = N
        while x % k == 0:
            x //= k

        if x % k == 1:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())
    ans = set()
    divisors = get_divisors(n)
    ans |= set(get_divisors(n-1))
    ans |= set([divisor for divisor in divisors if is_ok(n, divisor)])
    ans -= set([1])
    print(len(ans))

def is_ok(n, d):
    if d < 2:
        return False
    while n%d == 0:
        n //= d
    return n%d == 1

def get_divisors(n):
    out = []
    if n < 1:
        return out
    m = int(n**0.5)
    for i in range(1, m+1):
        if not n%i:
            out.append(i)
            if n != i**2:
                out.append(n//i)
    return out


if __name__ == "__main__":
    main()

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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 = set()

for x in make_divisors(n-1):
    if x != 1:
        ans.add(x)

for x in make_divisors(n):
    if x ==1 :
        continue
    if x == n:
        ans.add(x)
        continue
    m = n
    while m % x == 0:
        m = m//x
    
    if m % x == 1:
        ans.add(x)

print(len(ans))

Solution (Python):
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)


inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""




def divisor(n):
    """ nの約数列挙 """
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass  


def main():
    N = int(input())
    div_1 = divisor(N)
    div_2 = divisor(N-1)
    cnt = 0

    for i in div_1:
        if i == 1:
            continue
        tmp = N
        while tmp % i == 0:
            tmp = tmp / i
        tmp = tmp % i
        if tmp == 1:
            cnt += 1

    cnt += len(div_2) - 1
    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):

import sys


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 solve(N: int):
    ndiv = make_divisors(N)
    count = 0
    for div in ndiv:
        if div == 1:
            continue
        n = N
        while n % div == 0:
            n //= div
        if n % div == 1:
            count += 1
    print(len(make_divisors(N-1))+count-1)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    solve(N)


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

ans = []
l = int(math.log2(N))
for i in range(1,l+1):
  if round(N**(1/i))**i==N:
    ans.append(round(N**(1/i)))

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

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

print(len(ans))

Solution (Python):
def check(i):
	tot=k
	pw=0
	while(tot%i==0):
		tot//=i
		pw+=1
	if(tot%i==1):
		other = tot//i
		if(pw==0 and other>=2 and other<=k):
			setl.add(other)
		setl.add(i)

import math
k=int(input())
if(k==2):
	print(1)
	exit()
setl = set()
setl.add(k); setl.add(k-1)
for x in range(2,int(math.sqrt(k))+1):
	check(x)
	
print(len(setl))

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


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


N = int(input())


divs1 = f1(N - 1)
ans1 = len(divs1) - 1


divs = f1(N)
ans2 = 0
for i in range(1, len(divs)):
    t = N
    d = divs[i]
    while t % d == 0:
        t //= d
    if t % d == 1:
        ans2 += 1

print(ans1 + ans2)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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 main():
    N = int(input())

    divs = make_divisors(N)
    divs2 = make_divisors(N - 1)

    ans = set(divs2)
    for k in divs:
        tmpN = N
        if k == 1:
            continue
        while tmpN % k == 0:
            tmpN /= k

        if tmpN % k == 1:
            ans.add(k)

    print(len(ans) - 1)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
k = 2
count = set()
while k * k <= n:
    if n % k == 1:
        count.add(k)
        count.add((n-1)//k)
    elif n % k == 0:
        n_copy = n
        while n_copy % k == 0:
            n_copy //= k
        if n_copy % k == 1:
            count.add(k)
    k += 1
if n > 2:
    count.add(n-1)
count.add(n)
print(len(count))

Solution (Python):

def factorize(n):
    
    
    
    
    result = []
    tmp = n
    for k in range(2, int(n ** 0.5) + 1):
        cnt = 0
        while tmp % k == 0:
            cnt += 1
            tmp //= k
        if cnt > 0:
            result.append([k, cnt])
    if tmp != 1:
        result.append([tmp, 1])
    return result

def divisorize(n):
    
    
    
    f = factorize(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())
a = []
for k in divisorize(n)[1:]:
    nn = n
    while True:
        if nn < k:
            break
        if nn % k == 0:
            nn = nn // k
        else:
            nn = nn % k
    if nn == 1:
        a.append(k)
s = divisorize(n - 1)
print(len(list(set(a + s))[1:]))

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



ans1 = len(make_divisors(N-1)[1:])


ans2 = make_divisors(N)[1:]
ans3 = []
for i in ans2:
    Nt = N

    if Nt // i == 1:
        ans3.append(i)
        continue

    while True:
        if Nt % i == 0:
            Nt = Nt // i
        else:
            break

    if Nt % i == 1:
        ans3.append(i)

print(ans1 + len(ans3))

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

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

Solution (Python):
import math
INT_MAX=10**18+7
MOD=10**9+7
def INPUT():return list(int(i) for i in input().split())
def LIST_1D_ARRAY(n):return [0 for _ in range(n)]
def LIST_2D_ARRAY(m,n):return [[0 for _ in range(n)]for _ in range(m)]

n=int(input())
def calc(x,n):
    while(n%x==0):
        n//=x
    if n%x==1:
        return True
    else:
        return False

def factors(n):
    A=[]
    i=1
    while(i<=math.sqrt(n)):
        if n%i==0:
            if (n//i)==i:
                A.append(i)
            else:
                A.append(i)
                A.append(n//i)
        i+=1
    return A
x=len(factors(n-1))-1

A=factors(n)
A.sort()

for i in range(1,len(A)):
    if calc(A[i],n) is True:
        x+=1
print(x)

Solution (Python):



N = int(input())


def prime_factor(x):
    m = {}
    i = 2
    while i ** 2 <= x:
        while x % i == 0:
            if i in m:
                m[i] += 1
            else:
                m[i] = 1
            x //= i
        i += 1
    if x != 1:
        m[x] = 1
    return m


def make_divisors(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)
    return divisors


def main():
    m = prime_factor(N - 1)
    ans = 1
    for v in m.values():
        ans *= v + 1
    
    l = make_divisors(N)
    for x in l:
        y = N // x
        while y % x == 0:
            y //= x
        if y % x == 1:
            ans += 1
    
    print(ans)
    

if __name__ == "__main__":
    main()

Solution (Python):
def check(i):
	tot=k
	while(tot%i==0):
		tot//=i
	if(tot%i==1):
		setl.add(i)
import math
k=int(input())
if(k==2):
	print(1)
	exit()
setl = set()
setl.add(k); setl.add(k-1)
for x in range(2,int(math.sqrt(k))+1):
	check(x)
	check(k//x)
print(len(setl))

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

L = [0]*(int((N-1)**(1/2))+1)

for i in range(1,int((N-1)**(1/2))+1):
    if (N-1)%i == 0:
        ans += 2
        L[i] = 1
        
        
        
    if i**2 == N-1:
        ans -= 1

for i in range(1,int(N**(1/2))+1):
    if i < int((N-1)**(1/2))+1 and L[i] == 1:
        continue
    if N%i == 0:
        NN = N
        while NN % i == 0:
            NN //= i
        if NN % i == 1:
            ans += 1
            
        if i**2 == N:
            continue
        NN = N
        j = N//i
        while NN % j == 0:
            NN //= j
        if NN % j == 1:
            ans += 1
            

print(ans)

Solution (Python):
def devisor(n):
    cnt=0
    d=[]
    for i in range(1,round(n**0.5)+1):
        if n%i==0:
            cnt+=1
            d.append(i)
            if n//i!=i:
                cnt+=1
                d.append(n//i)
    return cnt,d

N=int(input())
ans=devisor(N-1)[0]-1

D=devisor(N)[1]

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

print(ans)

Solution (Python):
def waru(n,k):
    while(n >= k):
        if(n%k == 0):
            n //= k
        else:
            n %= k
    if(n == 1):
        return 1
    else:
        return 0
n = int(input())
p = 0
if(n < 100):
    for i in range(2,n+1):
        p += waru(n,i)
    print(p)
else:
    for i in range(2,int(n**0.5)+1):
        if(n%i == 1):
            p += 1
        p += waru(n,i)
    if(int((n-1)**0.5)**2 == n-1):
        p -= 1
    print(p+2)

Solution (Python):
def check(i):
	tot=k
	while(tot%i==0):
		tot//=i
	if(tot%i==1):
		setl.add(i)
import math
k=int(input())
setl = set()
setl.add(k); setl.add(k-1)
for x in range(2,int(math.sqrt(k))+1):
	check(x)
	check(k//x)
if(setl.__contains__(1)):
	setl.remove(1)
print(len(setl))

Solution (Python):
import sys
input = sys.stdin.readline


def inpl():
    return list(map(int, input().split()))


def factor(n):
    ret = {}
    p = 2
    root_n = int(n**0.5)
    while n > 1:
        if n % p == 0:
            n //= p
            ret[p] = ret.get(p, 0) + 1
        elif p <= root_n:
            p += 1
        else:
            p = n
    return ret


def gcd(a, b):
    
    while b > 0:
        a, b = b, a % b

    return a


def backtrack(pn_list, k=1):
    if (not pn_list) and k != 1 and k != N:
        factor_N.append(k)
    elif pn_list:
        
        p, v = pn_list[0]
        pn_list = pn_list[1:]
        
        for i in range(v + 1):
            backtrack(pn_list, k * (p**i))


def check(k):
    t = N
    while t % k == 0:
        t //= k
    return t % k == 1


factor_N = []


def solve():
    pn = factor(N)
    ans = 0
    a = 1
    for v in pn.values():
        a = gcd(a, v)
    for v in factor(a).values():
        a *= v + 1
    ans += a

    a = 1
    for v in factor(N - 1).values():
        a *= v + 1
    ans += a - 1

    pn_list = list(pn.items())
    
    backtrack(pn_list)
    for k in factor_N:
        if check(k):
            ans += 1

    return ans


N = int(input())

print(solve())

Solution (Python):


import math

N = int(input())

Klist = [0]*(int(N**(1/2))+1)
count = 1


for i in range(1,int((N-1)**(1/2))+1):
    if (N-1) % i == 0:
        Klist[i] = 1
        count += 1
        
        
        

if  (N-1)**(1/2) - int((N-1)**(1/2)) < 1e-10 or 1 + int((N-1)**(1/2)) - ((N-1)**(1/2)) < 1e-10:
    count -= 1

M = int(math.log2(N))

for m in range(1,M+1):
    if m >= 2 and (N**(1/m) - int(N**(1/m)) < 1e-10 or 1+int(N**(1/m))-N**(1/m) < 1e-10):
        Klist[round(N**(1/m))] = 1
    for K in range(2,int(N**(1/(m+1))+1)):
        if (N-K**m)%(K**(m+1)) == 0:
            Klist[K] = 1




print(sum(Klist)+count-Klist[1])

Solution (Python):
N = int(input())
cnt = 2 if N > 2 else 1

ret = []
for i in range(2, int(N**0.5)+1):
    if N % i == 0:
        k = N//i
        while k % i == 0:
            k //= i
        if k % i == 1:
            cnt += 1

        if N // i != i:
            j = N // i
            k = i
            while k % j == 0:
                k //= j
            if k % j == 1:
                cnt += 1

M = N - 1
for i in range(2, int((M)**0.5)+1):
    if M % i == 0:
        cnt += 1
        if M // i != i:
            cnt += 1

print(cnt)

Solution (Python):
def yakusu(N):
    if N == 1:
        return []
        
    fin = int(N**0.5)

    num = list()
    for i in range(2, fin+1):
        if N % i == 0:
            num.append(i)
            if N != i**2:
                num.append(N//i)
    num.append(N)
    
    return num


N = int(input())



ans = len(yakusu(N-1))



arr = yakusu(N)
for i in range(len(arr)):
    tmp = N
    while tmp % arr[i] == 0:
        tmp //= arr[i]
    
    if tmp % arr[i] == 1:
        ans += 1

print(ans)

Solution (Python):

import sys
import copy


def solve(N: int):
    divs = make_divisors(N)
    arr = []
    for div in divs:
        if div == 1:
            continue
        n = copy.copy(N)
        while(n % div == 0):
            n //= div
        if n % div == 1:
            arr.append(div)
    cnt = len(set(arr + make_divisors(N - 1))) - 1
    print(cnt)
    return


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 main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    solve(N)

if __name__ == '__main__':
    main()

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

N0 = int(input())
ans = 0


K_cand = set(make_divisors(N0) + make_divisors(N0-1))

for K in K_cand:
    N = N0
    if K == 1:  
        continue
    else:
        while N%K == 0:
            N = N // K  
        N = N%K  
        if N == 1:
            ans += 1

print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
def check(x,m):
    if m % x:
        return m % x == 1
    return check(x,m//x)

def count(n):
    cnt = 1
    f = defaultdict(int)
    for i in range(2,int(math.sqrt(n))+1):
        if n % i == 0 and f[i] == 0:
            cnt += 1
            f[i] = 1
            if f[n//i] == 0:
                cnt += 1
                f[n//i] = 1
    return cnt

def count2(n):
    cnt = 1
    f = defaultdict(int)
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            if check(i,n) and f[i] == 0:
                cnt += 1
                f[i] = 1
            if check(n//i,n) and f[n//i] == 0:
                cnt += 1
                f[n//i] = 1
    return cnt
ans = 0
if n-1 >= 2:
    ans += count(n-1)
ans += count2(n)
print(ans)