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):
import math

def divisor(num):
    if num < 0:
        return 0
    if num == 1:
        return [1, ]

    divisor_list = [1, ]
    divisor_list_r = [num, ]

    i = 2
    while i * i <= num:
        if num % i == 0:
            divisor_list.append(i)
            if i != num // i:
                divisor_list_r.append(num//i)
        i += 1

    return divisor_list+divisor_list_r[::-1]


N = int(input())
ans = len(divisor(N-1))-1
cand = divisor(N)

for i, num in enumerate(cand[1:]):
    num2 = N
    while num2 >= num:
        tmp1, tmp2 = divmod(num2, num)
        if tmp2 == 0:
            num2 = tmp1
        else:
            num2 = tmp2
    if num2 == 1:
        ans += 1
print(ans)

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

ans = set()

def check(k):
    global ans, n
    if k <= 1 or k > n:
        return
    c = n
    while c % k == 0 and c >= k:
        c //= k
    c %= k
    if c == 1:
        ans.add(k)

for i in range(1, n):
    if i ** 2 > n:
        break
    if i ** 2 == n:
        check(i)
    elif n % i == 0:
        check(i)
        check(n // i)

m = n - 1
for i in range(1, m):
    if i ** 2 > m:
        break
    if i ** 2 == m:
        check(i)
    elif m % i == 0:
        check(i)
        check(m // i)

print(len(ans))

Solution (Python):
def make_divisors(n: int) -> list:
    """自然数nの約数を列挙したリストを出力する
    計算量: O(sqrt(N))
    入出力例: 12 -> [1, 2, 3, 4, 6, 12]
    """
    divisors = []
    for k in range(1, int(n ** 0.5) + 1):
        if n % k == 0:
            divisors.append(k)
            if k != n // k:
                divisors.append(n // k)
    divisors = sorted(divisors)
    return divisors


n = int(input())
ans = 0
for num in make_divisors(n):
    if num == 1:
        continue
    res = n
    while res >= num:
        if res % num == 0:
            res = res // num
        else:
            res = res - (res // num) * num
    if res == 1:
        ans += 1
print(ans + len(make_divisors(n - 1)) - 1)

Solution (Python):
N=int(input())
l=[]
for i in range(2,10**6+1):
    if not N%i:
        if i>N//i:
            break
        if i**2==N:
            l.append(i)
            break
        l+=[i,N//i]
l.append(N)
a=0
for i in l:
    t=N
    while t>=i:
        if t%i:
            t%=i
        else:
            t//=i
    if t==1:
        a+=1
N-=1
for i in range(1,10**6+1):
    if not N%i:
        if i>N//i:
            break
        if i**2==N:
            a+=1
            break
        else:
            a+=2
print(a-1)

Solution (Python):
import sys
n = int(input())
if n == 2:
	print(1)
	sys.exit()
divs = []
i = 2
while i*i <= n:
	if n%i == 0:
		divs.append(i)
		if i*i < n:
			divs.append(n//i)
	i += 1
divs.append(n)

ans = set()
i = 2
while i*i <= n-1:
	if (n-1)%i == 0:
		ans.add(i)
		if i*i < (n-1):
			ans.add((n-1)//i)
	i += 1
ans.add(n-1)

for d in divs:
	tmp = n
	while tmp%d == 0:
		tmp //= d
	if tmp%d == 1:
		ans.add(d)
print(len(ans))

Solution (Python):



def divisor_list(N): 
    if N == 1: return [1]
    res = []
    for i in range(1,N):
        if i*i >= N: break
        if N%i == 0:
            res.append(i)
            res.append(N//i)
    if i*i == N: res.append(i)
    return res

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read


N = int(input())
div = divisor_list(N)
div2 = divisor_list(N-1)

ans = set()
for d in div:
    if d==1: continue
    n = N
    while n%d==0:
        n//=d
    if n%d==1: ans.add(d)



ans = len(ans)+len(div2)-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())
div = make_divisors(n)[1:]
s = set(make_divisors(n - 1))
for d in div:
    t = n
    while t % d == 0:
        t //= d
    if (t - 1) % d == 0:
        s.add(d)
print(len(s) - 1)

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

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

now = 1
ans = 0

def want(m):

    ns = N
    while ns % m == 0:
        ns = ns // m
    return ns % m

while now ** 2 <= N:

    if N % now == 0:

        n2 = N // now
        

        if now != 1:
            rev = want(now)
            if rev == 1:
                ans += 1


        if n2 != now and n2 != 1:

            rev = want(n2)
            if rev == 1:
                ans += 1

    now += 1

now = 1
while now ** 2 <= N-1:

    if (N-1) % now == 0:
        n2 = (N-1) // now

        if now != 1:
            ans += 1
        if now != n2:
            ans += 1
    now += 1
        
print (ans)

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


n = int(input())
ans = set(divisors(n-1))

candidates = divisors(n)
candidates.remove(1)
for k in candidates:
    num = n // k
    while num % k == 0:
        num //= k
    residue = num % k
    if residue == 1:
        ans.add(k)

ans.discard(1)
print(len(ans))

Solution (Python):
import math

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

def factorize(N):
    up = int(math.sqrt(N))+2
    out = {}

    for i in range(2,up):
        if N%i == 0:
            temp = N
            count = 0
            while(True):
                N = N//i
                count += 1
                if N%i != 0:
                    break
            out[i] = count
        else:
            continue
    if N != 1:
        out[N] = 1
    return out

yakusuu = make_divisors(n)[1:]

soinnsuu = factorize(n)
soinnsuu2 = factorize(n-1)





ans = 0
for y in yakusuu:
    hoge = n
    while True:
        if hoge%y == 0:
            hoge = hoge//y
        else:
            break
    if hoge%y == 1:
        ans+=1

ok = {}
for key in soinnsuu2.keys():
    if not key in soinnsuu:
        ok[key] = soinnsuu2[key]


ex = 1
for key in ok.keys():
    ex *= ok[key]+1

ex-=1



print(ans+ex)

Solution (Python):
n=int(input())
ans=0
for i in range(2,int(n**0.5)+1):
    t=n
    if t%i!=0:
        continue
    while t%i==0:
        t//=i
    if t%i==1:
            ans+=1
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
import collections
c=collections.Counter(prime_factorize(n-1))
t=1
for i in c.values():
    t*=i+1
print(ans+t)

Solution (Python):
def examA():
    X, Y, Z = LI()
    X, Y = Y,X
    X,Z = Z, X
    print(X,Y,Z)
    return

def examB():
    N, M = LI()
    A = LI()
    need = (sum(A)-1)//(4*M) + 1
    ans = 0
    
    for a in A:
        if a>=need:
            ans += 1
    if ans>=M:
        print("Yes")
    else:
        print("No")
    return

def examC():
    N, K = LI()
    ans = N%K
    if K-ans<ans:
        ans = K-ans
    print(ans)
    return

def examD():
    def bfs(n):
        
        W = [""] * n
        
        que = deque()
        for i in range(1,10):
            que.append(str(i))
            W[i-1] = str(i)
        i = 9
        while(i<n):
            now = que.popleft()
            end = now[-1]
            for j in [-1,0,1]:
                ne = int(end)+j
                if 0<=ne<=9:
                    W[i] = now + str(ne)
                    que.append(W[i])
                    i += 1
                    if i==n:
                        break
        return W
    K = I()
    if K<=12:
        ans = K
        print(ans)
        return
    ans = bfs(K)[-1]
    print(ans)
    return

def examE():
    N, K, C = LI()
    S = SI()
    L = set()
    R = set()
    prev = -inf
    for i,s in enumerate(S):
        if s=="x":
            continue
        if prev+C>=i:
            continue
        L.add(i)
        prev = i
    if len(L)>K:
        print()
        return
    prev = inf
    for i in range(N)[::-1]:
        s = S[i]
        if s=="x":
            continue
        if prev-C<=i:
            continue
        R.add(i)
        prev = i
    
    ans = []
    for i in L:
        if i in R:
            ans.append(i+1)
    if not ans:
        print()
        return
    ans.sort()
    for v in ans:
        print(v)
    return

def examF():
    def factorization(n):
        arr = defaultdict(int)
        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[i] = cnt
        if temp != 1:
            arr[temp] = 1
        if arr == []:
            arr[n] = 1
        return arr

    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 check(n,k):
        if n%k==0:
            n //=k
        else:
            if n%k==1:
                return 1
            else:
                return 0
        return check(n,k)
    N = I()
    F = factorization(N-1)
    
    ans = 0
    cur = 1
    for [f,i] in F.items():
        cur *= (i+1)
    ans += cur-1
    M = make_divisors(N)
    
    for k in M:
        if k==1:
            continue
        ans += check(N,k)
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examF()

"""

"""

Solution (Python):
from collections import defaultdict


def get_divisor(n: int) -> list:
    divisor = []
    for i in range(1, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            divisor.append(i)
            if n // i != i:
                divisor.append(n // i)
    
    return divisor


n = int(input())

d0 = get_divisor(n)
ans0 = 0  
for di in d0:
    if di == 1:
        continue
    x = n // di
    while x % di == 0:
        x = x // di
    if x % di == 1:
        
        ans0 += 1

d1 = get_divisor(n - 1)
ans1 = len(d1) - 1

ans = ans0 + ans1


print(ans)

Solution (Python):
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1<<32 else [2, 3, 5, 7, 11, 13, 17] if n < 1<<48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)
def calc(n, k):
    if n % k == 0:
        return n // k
    return n % k
def chk(n, k):
    while n >= k:
        n = calc(n, k)
    return 1 if n == 1 else 0

N = int(input())
L = list(set(divisors(N) + divisors(N-1)))
print(len([l for l in L if l > 1 and chk(N, l)]))

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 = 0
for i in make_divisors(n):
    if i != 1:
        x = n
        flag = True
        while flag:
            x //= i
            if x % i != 0:
                flag = False
        if x % i == 1:
            ans += 1
ans += len(make_divisors(n-1))-1
print(ans)

Solution (Python):
import copy as cp

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)
    
    return divisors

N = int(input())
div1_l = make_divisors(N-1)
count = len(div1_l)

div_l = make_divisors(N)
for d in div_l:
    n = N
    while True:
        if n%d == 0:
            n = n//d
        else:
            if n%d == 1:
                count += 1
            break
if N == 2:
    count = 1

print(count)

Solution (Python):
n = int(input())
ans = 0
for i in range(2,10**6+1):
  m = int(n)
  while True:
    if m % i == 0:
      m //= i
    elif m % i == 1:
      
      ans += 1
      break
    else:
      break
for i in range(1,10**6+1):
  if (n-1) % i == 0 and (n-1) // i > 10**6:
    
    ans += 1
if n > 10**6:
  ans += 1
print(ans)

Solution (Python):

import sys
from math import sqrt
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    s=set()
    for i in range(1,int(sqrt(N))+1):
        if (N-1)%i==0:
            s.add(i)
            s.add((N-1)//i)
        else:
            if N%i==0:
                tmp=N
                while True:
                    if tmp%i==0:
                        tmp//=i
                    else:
                        tmp-=tmp//i*i
                    if tmp==1:
                        s.add(i)
                        break
                    if tmp<i:
                        break
    print(len(s))

if __name__ == '__main__':
    main()

Solution (Python):


import sys
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

N = int(input())

divs = make_divisors(N)
ans = len(make_divisors(N-1))

for d in divs:
    tn = N
    while tn>=d and tn%d==0:
        tn //= d
    if tn==1 or tn%d==1:
        ans += 1

if N==2:
    print(1)
else:
    print(ans)

Solution (Python):
import math

N = int(input())

def yakusu(n):
    list1 = []
    list2 = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            list1.append(i)
            if i != n // i:
                list2.append(n // i)
    list2.reverse()
    return list1 + list2

def A(x):
    m = l1[len1 - i - 1]
    while m > 0:
        if m % x == 0:
            m //= x
        elif m % x == 1:
            return True
        else:
            return False
    return False

l1 = yakusu(N)
len1 = len(l1)

l2 = yakusu(N - 1)

ans = len(l2) - 1

for i in range(1, len1):
    if A(l1[i]):
        ans += 1

print(ans)

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

n=int(input())
if n==2:
  print(1)
else:
  divs1=divisors(n)
  divs2=divisors(n-1)
  cand=divs2
  for val in divs1:
    tmp=n
    while tmp%val==0:
      tmp=tmp//val
    if tmp%val==1:
      cand.append(val)
  if n not in cand:
    cand.append(n)
  if n-1 not in cand:
    cand.append(n-1)
  print(len(cand))

Solution (Python):
import math
N = int(input())
ans = 0
li = []
for i in range(1,math.floor(math.sqrt(N-1))+1):
    if (N-1)%i==0:
        ans += 1
        if not (N-1)//i == i:
            ans += 1
for i in range(1,math.floor(math.sqrt(N))+1):
    if N%i==0:
        li.append(i)
        if not N//i == i:
            li.append(N//i)
for x in li:
    if x != 1:
        e = 1
        while N%(x**e) == 0:
            e += 1
        m = N//(x**(e-1))
        if m%x == 1:
            ans += 1
print(ans-1)

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

N = int(input())


def yaku(n):
    ret = []
    for num in range(1, int(math.sqrt(n)+3)):
        if n % num == 0:
            p = n//num
            if num < p:
                ret.append(num)
                ret.append(p)
            elif num == p:
                ret.append(p)
    return ret

ans = len(yaku(N-1))-1
for num in yaku(N):
    if num == 1: continue
    T = N
    while T%num == 0:
        T //= num
    if (T-1)%num == 0:
        ans += 1

print(ans)

Solution (Python):
def divisor(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 sorted(div)


N = int(input())
ans = set()
divN = divisor(N)
for d in divN:
    p = N // d
    while d % p == 0 and p != 1:
        d = d // p
    if (d - 1) % p == 0:
        ans.add(p)
for d in divisor(N - 1):
    ans.add(d)
print(len(ans) - 1 if 1 in ans else len(ans))

Solution (Python):
import bisect

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 len(divisors) // 2

n = int(input())
ans = 1
if n == 2:
  print(1)
  exit()
if n == 3:
  print(2)
  exit()
a = []
for i in range(2,int(n ** 0.5)+1):
  now = n
  while not now % i:
    now //= i
  if now % i == 1:
    a.append(i)
    ans += 1
ans += make_divisors(n-1)
print(ans)

Solution (Python):
import sys
n=int(input())
if n==2:
  print(1)
  sys.exit()
l=[n]
for i in range(2,int(n**0.5)+1):
  if n%i==0:
    l.append(i)
l=list(set(l))
L=[]
for j in range(len(l)):
  x=n
  k=l[j]
  while x%k==0:
    x=x//k
  if x%k==1:
    L.append(l[j])

l2=[n-1]
for i in range(2,int((n-1)**0.5)+1):
  if (n-1)%i==0:
    l2.append(i)
    l2.append((n-1)//i)
l2=list(set(l2))
l2.sort()

print(len(L+l2))

Solution (Python):
from fractions import gcd

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

N = int(input())
ans = len(divisor(N-1)) - 1
divisors = divisor(N)
for K in divisors[1:]:
    n = N
    while n % K == 0:
        n //= K
    if (n - 1) % K == 0:
        ans += 1
print(ans)

Solution (Python):
n = int(input())
A = [n]
B = []
for i in range(2, int(n**0.5)+1):
    
    t = n
    u = n
    f = 0
    g = 0
    while t%i==0:
        t //= i
        f = 1
    while u%(n//i) == 0:
        u //= (n//i)
        g = 1
    if (t - 1) % i == 0 and f==1:
        B.append(i)
    if (u - 1) % (n//i) == 0 and g==1:
        B.append(n//i)

for i in range(1, int((n-1)**0.5) + 1):
    if (n-1)%i == 0:
        B.append(i)
        B.append((n-1)//i)













print(len(set(B)))

Solution (Python):
import math
n=int(input())
s=math.ceil((n**0.5))
a=set([])
if n==2:print(1);exit()
a.add(n)
a.add(n-1)
for i in range(2,int((n-1)**0.5)+1):
    if (n-1)%i==0:
        a.add(i)
        a.add((n-1)//i)
def check(dived,diving):
    while dived>=2:
        if dived<diving:return False
        if dived%diving==0:
            dived//=diving
        else:
            dived%=diving
    return True
for j in range(2,int(n**0.5)+1):
    if n%j==0:
        if check(n,j):a.add(j)
print(len(a))

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

ans = 0

p1_array = [N]
for i in range(2, int(math.sqrt(N) + 1)):
    if N % i == 0:
        if N == i * i:
            p1_array.append(i)
            break
        else:
            p1_array.append(i)
            p1_array.append(N//i)


for p in p1_array:
    n = N
    while(n % p == 0):
        n = n // p
    if n % p == 1:
        ans += 1

if N != 2:
    N = N-1
    p2_array = [N]
    for i in range(2, int(math.sqrt(N) + 1)):
        if N % i == 0:
            if N == i * i:
                p2_array.append(i)
                break
            else:
                p2_array.append(i)
                p2_array.append(N//i)
    ans += len(p2_array)

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

n = int(input())
ans = set()

divisors = make_divisors(n)
for value in divisors:
  key = n
  while key % value == 0:
    key //= value
  if key%value == 1:
    ans.add(value)

divisors2 = set(make_divisors(n-1))
ans = ans.union(divisors2)
print(len(ans))

Solution (Python):
def divisor(n): 
    ans = [n]
    i = 2
    while i**2 <= n:
        if n%i == 0:
            ans.append(i)
            if i**2 < n:
                ans.append(n//i)
        i += 1
    ans.sort()
    return ans

n = int(input())
if n == 2:
    print(1)
    exit()
ans = len(divisor(n-1))
data = divisor(n)
for k in data:
    m = n
    while m%k == 0:
        m //= k
    if (m-1)%k == 0:
        ans += 1

print(ans)

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

def y(n):
    yaku = set()
    for i in range(1, 10 ** 6 + 1):
        if n % i == 0:
            yaku.add(i)
            yaku.add( n // i)
    yaku.remove(1)
    return yaku

ans = len(y(n - 1))

for i in y(n):
    nn = n
    while nn % i == 0:
        nn //= i
    if nn % i == 1:
        ans += 1
print(ans)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def fact(n):
        if n < 4:
            return set([n])
        i = 2
        res = set([n])
        while i ** 2<= n:
            if n%i == 0:
                res.add(i)
                m = n//i
                if m != i:
                    res.add(m)
            i += 1
        return res

    def check(n,i):
        while n >= i:
            if n%i == 0:
                n //= i
            else:
                n -= i
        if n == 1:
            return 1
        return 0
    n = I()
    if n == 2:
        print(1)
        return
    ans = {2,n}
    f = fact(n)
    for i in f:
        m = n
        while not m%i:
            m //= i
        if m % i == 1:
            ans.add(i)
    ans |= fact(n-1)
    print(len(ans))
    return


if __name__ == "__main__":
    solve()

Solution (Python):

n = int(input())
fct1 = []
fct2 = []
for i in range(1,int(n**(1/2))+10):
    if n%i==0:
        fct1.append(i)
        fct2.append(n//i)
    if (n-1)%i==0:
        fct1.append(i)
        fct2.append((n-1)//i)

fct = set(fct1+fct2)
if 1 in fct:
    fct.remove(1)
ans = 0
for k in fct:
    n2 = n
    while n2 and n2%k==0:
        n2//=k
    n2%=k
    if n2==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)

    
    return divisors
x=int(input())
ans=0
di=make_divisors(x)
for i in di:
    if i==1:
        continue
    p=x
    while p%i==0:
        p=p//i
    q=x//p
    if p%i==1 or p==1:
        ans+=1
d=make_divisors(x-1)
print(ans+len(d)-1)

Solution (Python):
def factorize_dict(n):
    i=2
    result={}
    while True:
        if i**2>n:
            break
        count=0
        while n%i==0:
            n//=i
            count+= 1
        if count!=0:
            result[i]=count
        i+=1
    if n>1:
        result[n]=1
    return result

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 judge(n,k):
    while n%k==0:
        n//=k
    return n%k

def main():
    n=int(input())
    ans=0
    f_d=factorize_dict(n-1)
    tmp=1
    for v in f_d.values():
        tmp*=(v+1)
    tmp-=1
    ans+=tmp
    D=make_divisors(n)
    for d in D:
        if d==1:
            continue
        if judge(n,d)==1:
            ans+=1
    print(ans)
    
if __name__=='__main__':
    main()

Solution (Python):
def factors(N): 
    from collections import deque
    ret = deque()
    middle = int( N**(1/2))
    for i in range(1, middle):
        if N%i == 0:
            ret.append(i)
            ret.append(N//i)
            
    if N%middle == 0:
        ret.append(middle)
        if middle != N//middle:
            ret.append(N//middle)
    return ret



def main():
    N = int( input())
    ans = 0
    F = factors(N)
    for k in F:
        if k == 1:
            continue
        x = N
        while x%k == 0:
            x //= k
        x %= k
        if x == 1:
            ans += 1
    G = factors(N-1)
    for k in G:
        if k == 1:
            continue
        x = N
        while x%k == 0:
            x //= k
        x %= k
        if x == 1:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()

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

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

if N <= 10**6:
    ans = 0
    for i in range(2, N + 1):
        if isOk(i):
            ans += 1
    print(ans)
    exit()

ans = 0
V = set()
for i in range(2, int(N**0.5) + 10):
    if isOk(i):
        ans += 1
        V.add(i)


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)
    
    return divisors

divN = divisors(N - 1)

ans += len([d for d in divN if not d in V])
print(ans)

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

cnt = 0

def check(d):
    tmp = n
    while tmp % d == 0:tmp //= d
    tmp %= d
    return tmp == 1

d = 1
while d * d <= n:
    if n % d != 0:
        d+=1
        continue
    if d != 1:
        cnt += check(d)
    if n // d > d:
        cnt += check(n // d)
    d += 1

n -= 1
d = 1
while d * d <= n:
    if n % d != 0:
        d+=1
        continue
    if d != 1:
        cnt += 1
    if n // d > d:
        cnt += 1
    d += 1

print(cnt)

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

    def PrimeDecomposition(N):
        ret = {}
        n = int(N ** 0.5)
        for d in range(2, n + 1):
            while N % d == 0:
                if d not in ret:
                    ret[d] = 1
                else:
                    ret[d] += 1
                N //= d
            if N == 1:
                break
        if N != 1:
            ret[N] = 1
        return ret

    N = int(input())
    n = int(N**0.5)

    ans = 0
    for k in range(2, n+1):
        M = N
        while M >= k:
            if M%k==0:
                M //= k
            else:
                M %= k
        if M == 1:
            ans += 1

    prime = PrimeDecomposition(N-1)
    ans2 = 1
    for p in prime:
        ans2 *= (prime[p] + 1)
    print(ans + ans2//2 + 1)


if __name__ == '__main__':
    main()

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

l1 = []
for n in range(1,int(N**0.5)+1):
    if N%n==0:
        l1.append(n)
        l1.append(N//n)
l1 = list(set(l1))
l1.sort()

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

l1 = l1[1:]
l2 = l2[1:]

ans = l2

def cal(n,k):
    if n%k==0:
        return cal(n//k,k)
    else:
        return n%k

for i in l1:
    if cal(N,i)==1:
        ans.append(i)

ans = len(set(ans))
print(ans)

Solution (Python):
n = int(input())
ans = 1
pr = []
if n == 2:
  print(1)
  exit()
if n == 3:
  print(2)
  exit()
for i in range(1,int(n**0.5)):
  if (n-1)%i == 0:
    pr.append((n-1)//i)
ans += len(pr)
for i in range(2,int(n**0.5+2)):
  t = n
  while t > i:
    if t%i:
      t %= i
    else:
      t //= i
  if t == 1 or t == i:
    ans += 1
if int(n**0.5+0.5)**2 == n:
  ans -= 1
print(ans)

Solution (Python):
def f(x):
    s=set()
    for i in range(1,int(x**(0.5))+6):
        if x%i==0: s.add(i);s.add(x//i)
    return s 


ans=set()
n=int(input())
ans=f(n-1)
ans1=f(n)
ans1.remove(1)

for x in ans1:
    p=n
    while p>=x:
        if p%x==0: p//=x
        else: p%=x
    if p==1: ans.add(x)

if 1 in ans: ans.remove(1)
print(len(ans))