Problem:
 Score : 600 points    Problem Statement Given is a positive integer N .  We will choose an integer K between 2 and N (inclusive), then we will repeat the operation below until N becomes less than K .   Operation: if K divides N , replace N with N/K ; otherwise, replace N with N-K .   In how many choices of K will N become 1 in the end?      Constraints  2 \leq N \leq 10^{12}  N is an integer.         Input Input is given from Standard Input in the following format:  N       Output Print the number of choices of K in which N becomes 1 in the end.        Sample Input 1 6      Sample Output 1 3  There are three choices of K in which N becomes 1 in the end: 2 , 5 , and 6 .  In each of these choices, N will change as follows:   When K=2 : 6 \to 3 \to 1  When K=5 : 6 \to 1  When K=6 : 6 \to 1        Sample Input 2 3141      Sample Output 2 13       Sample Input 3 314159265358      Sample Output 3 9

Solution (Python):
N = int(input())
originalN = 0 +N
if N == 2:
  print(1)
  exit()
ans = 0
"""
primenum = [2]
count = [0 for _ in range(int(N**0.5)+2)]
for k in range(3, len(count), 2):
  if count[k] == 0:
    primenum.append(k)
    for j in range(k, len(count), k):
      count[j] = 1
    
def factorization(n):
  lis = []
  k = 0
  while primenum[k] <= n:
    if n%primenum[k] == 0:
      c = 0 
      while n%primenum[k] == 0:
        n //= primenum[k]
        c += 1
      lis.append([primenum[k], c])
    else:
      k += 1
      if k > len(primenum)-1:
        break
  if n > 1:
    lis.append([n, 1])
  return lis
"""
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
ans1 -= 1
ans += ans1



def operation(K):
  N = originalN
  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]

ans2 = 1
for item in factorlist:
  if operation(item):
    
    ans2 +=1


ans += ans2


print(ans)

Solution (Python):
N = int(input())
originalN = 0 +N
if N == 2:
  print(1)
  exit()
ans = 0
primenum = [2]
count = [0 for _ in range(int(N**0.5)+2)]
for k in range(3, len(count), 2):
  if count[k] == 0:
    primenum.append(k)
    for j in range(k, len(count), k):
      count[j] = 1
    
def factorization(n):
  lis = []
  k = 0
  while primenum[k] <= n:
    if n%primenum[k] == 0:
      c = 0 
      while n%primenum[k] == 0:
        n //= primenum[k]
        c += 1
      lis.append([primenum[k], c])
    else:
      k += 1
      if k > len(primenum)-1:
        break
  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
ans1 -= 1
ans += ans1



def operation(K):
  N = originalN
  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]

ans2 = 1
for item in factorlist:
  if operation(item):
    
    ans2 +=1


ans += ans2


print(ans)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    lower.extend(reversed(upper))
    return lower


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

    D = divisors(N)
    D1 = divisors(N - 1)
    ans = len(D1) - 1

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    lower.extend(reversed(upper))
    return lower


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

    D = divisors(N)
    D1 = divisors(N - 1)
    ans = len(D1) - 1

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    lower.extend(reversed(upper))
    return lower


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

    D = divisors(N)
    D1 = divisors(N - 1)
    ans = len(D1) - 1

    for d in D[1:]:
        n = N
        while n % d == 0:
            n //= d
            if (n - 1) % d == 0:
                ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
from math import gcd

def is_prime_miller_rabin(n):  
    if n < 2:
        return False
    elif n in {2, 3, 5, 7, 11}:
        return True
    elif n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 or n % 11 == 0:
        return False

    if n < 4_759_123_141:
        witnesses = [2, 7, 61]
    elif n < 341_550_071_728_321:
        witnesses = [2, 3, 5, 7, 11, 13, 17]
    else:
        witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]

    d = n - 1
    d = d // (d & -d)

    for a in witnesses:
        y = pow(a, d, n)
        if y == 1:
            continue
        t = d
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1:
                return False
            t <<= 1
    return True

def find_factor_rho(n):  
    if n < 2:
        return None
    m = 1<<n.bit_length() // 8 + 1
    for c in range(1, 99):
        def f(x):
            return (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 is_prime_miller_rabin(g):
                return g
            elif is_prime_miller_rabin(n // g):
                return n // g
    return None

def prime_factorize_dict(n):
    prime_dict = defaultdict(int)
    i = 2
    while i * i <= n:
        while n % i == 0:
            n //= i
            prime_dict[i] += 1
        i += 1 + i % 2
        if i != 101 or n < 1<<20:
            continue
        while n > 1:
            if is_prime_miller_rabin(n):
                prime_dict[n] = n = 1
                break
            j = find_factor_rho(n)
            while n % j == 0:
                n //= j
                prime_dict[j] += 1
    if n > 1:
        prime_dict[n] += 1
    return prime_dict



n = int(input())
ans = 1
for value in prime_factorize_dict(n - 1).values():
    ans *= value + 1
ans -= 1  

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

for divisor in get_divisors(n)[1:]:
    tmp = n
    while tmp % divisor == 0:
        tmp //= divisor
    if tmp % divisor == 1:
        ans += 1

print(ans)

Solution (Python):
import math
N = int(input())
if N == 2:
    print(1)
    exit()
ans = 0
M = int(N**0.5) + 1
for k in range(2, M):
    n = N
    while n:
        if n % k == 0:
            n //= k
        elif n % k == 1:
            ans += n != N
            break
        else:
            break


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


ans2 = 1
for _, i in factorization(N - 1):
    ans2 *= (1 + i)
ans += ans2
print(ans)

Solution (Python):
def main():
    N = int(input())
    if N <= 3:
        print(N - 1)
        return
    
    ans_1 = 0
    k = 2
    while k ** 2 <= N:
        n = N
        while n % k == 0:
            n //= k
        n %= k
        if n == 1:
            ans_1 += 1
        k += 1
    
    
    ans_2 = 1
    n = 1
    while n ** 2 < N:
        if (N - 1) % n == 0 and ((N - 1) // n) ** 2 > N:
            ans_2 += 1
        n += 1
    
    print(ans_1 + ans_2)


if __name__ == '__main__':
    main()

Solution (Python):
from math import sqrt, ceil
n = int(input())
def ans(n):
  if n == 2:
    return 1
  
  count = sum(2*int((n-1)%i==0) for i in range(2, ceil(sqrt(n-1))))
  
  if ceil(sqrt(n-1)) == int(sqrt(n-1)):
    count += 1
  
  count += 1
  
  for i in range(2, ceil(sqrt(n))):
    if n%i==0:
      x = n
      while x%i == 0:
        x = x//i
      count += int((x-1)%i==0)
      other_divisor = n//i
      x = n
      while x%other_divisor == 0:
        x = x//other_divisor
      count += int((x-1)%other_divisor==0)
  
  if ceil(sqrt(n)) == int(sqrt(n)):
    i = int(sqrt(n))
    x = n
    while x%i == 0:
      x = x//i
    count += int((x-1)%i==0)
  
  count += 1
  return(count)
print(ans(n))

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


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


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]


ns = make_divisors(n)

ans = 0
for i in ns:
    if i == 1:
        continue
    p = n
    while p % i == 0:
        p //= i
    if p % i == 1:
        ans += 1


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

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

F = make_divisors(N)
count = 0
for f in F:
  n = N
  while 1:
    if n % f != 0:
      n = n % f
    else:
      n = n // f
    if n < f:
      break
  if n == 1: count += 1
print(count + len(make_divisors(N-1)))

Solution (Python):
n = int(input())
div = []
div2 = []
ans = 0
for i in range(1,10**6+1):
    if n%i == 0:
        div+=[i,n//i]
    if (n-1)%i == 0:
        div2+=[i,(n-1)//i]
div = set(div)
div2 = set(div2)

a = [1]
for i in div:
    if i > 1:    
        t = n
        while t:
            if t%i == 0:
                t = t//i
            else:
                if t%i == 1:
                    ans += 1
                    a += [i]
                break















for i in div2:
    a+=[i]
a = set(a)

print(len(a)-1)

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

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

answer_set=set()
for i in range(2,int(N**0.5)+1):
  N2=N
  while N2%i==0:
    N2//=i
  if N2%i==1:
    answer_set.add(i)


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


answer_set.add(N)
print(len(answer_set))

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter



import bisect
n=int(input())
m=int(pow(n,0.5))
s=set()
t=set()
for i in range(1,m+1):
    if n%i==0:
        s.add(i)
        s.add(n//i)
    if (n-1)%i==0:
       t.add(i)
       t.add((n-1)//i) 
ans=len(t)-1
for i in s:
    if i==1:
      continue
    c=n
    while True:
        if c%i==0:
            c=c//i
        else:
            if c%i==1:
                ans+=1
            break
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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())
ans = len(make_divisors(N-1))-1
lis = make_divisors(N)
for n in lis:
    G = N
    if n==1:
        continue
    while G%n==0:
        G //= n
    if G%n==1:
        ans += 1
print(ans)

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())

def divisore(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

ans_l=divisore(n-1)[1:]

d=divisore(n)
for i in d[1:]:
  nn=n
  while nn%i==0:
    nn//=i
  if nn%i==1:
    ans_l.append(i)

print(len(ans_l))

Solution (Python):
N = int(input())
if N ==2:
  print(1)
  exit()

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 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)
ans = 0 
SET = set([N])

for i in range(1,len(A)):
  M = N*1
  while M%A[i]==0:
    M = M//A[i]
  if M%A[i] == 1:
    ans += 1
    SET.add(A[i])



N -= 1
B = factorization(N)
yakusu = 1

for i in range(len(B)):
  yakusu *= (B[i][1]+1)

ans += yakusu-1
print(ans)

Solution (Python):
n=int(input())
ans=set()
ans.add(n)
i=2
x = 1
while x * x <= n-1 :
  if (n-1) % x == 0:          
    ans.add(x)
    ans.add((n-1)//x)
  x += 1
while i*i<=n:
  t=n
  while t%i==0:
    t/=i
  if t%i==1:
    ans.add(i)
  i+=1
print(len(ans)-1)

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

N = int(input())


def divisor(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 

ans = len(divisor(N-1))-1
b = divisor(N)
for bi in b:
    if bi == 1:
        continue
    a = N
    while a >= bi:
        if a%bi == 0:
            a = a//bi
        else:
            a = a%bi
    if a == 1:
        ans += 1
print(ans)

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

divs = set()
n = 1
while n*n <= N:
    if N%n==0:
        divs.add(n)
        divs.add(N//n)
    n += 1

divs2 = set()
n = 1
while n*n <= (N-1):
    if (N-1)%n==0:
        divs2.add(n)
        divs2.add((N-1)//n)
    n += 1

ans = len(divs2) - 1
for d in divs:
    if d==1: continue
    n = N
    while n >= 1:
        if n==1:
            ans += 1
            break
        if n%d == 0:
            n //= d
        else:
            if n%d == 1:
                ans += 1
            break

print(ans)

Solution (Python):
N=int(input())
P=0
def f(x):
  r=[]
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      r.append(i)
      if x!=i*i:
        r.append(x//i)
  return r

A=f(N)
M=0
for i in range(len(A)):
  if A[i]==1:
    continue
  M=N
  while M%A[i]==0:
    M//=A[i]
  if M%A[i]==1:
    P+=1
P+=len(f(N-1))-1
print(P)

Solution (Python):
import sys
from math import gcd

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

"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
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


factors = factorization(N)
ans = 0


tmp = factors[0][1]
for k, i in factors:
    tmp = gcd(tmp, i)
ptn = 1
if tmp != 1:
    for k, i in factorization(tmp):
        ptn *= i+1
ans += ptn


ptn = 1
for k, i in factorization(N-1):
    ptn *= i+1
ptn -= 1  
ans += ptn


ptn = 0
for f, n in factors:
    for i in range(1, n+1):
        k = f**i
        tmp = N
        while True:
            if tmp%k!=0:
                break
            tmp = tmp/k
        ptn += ((tmp-1)%k==0 and tmp!=1)
ans += ptn

print(ans)

Solution (Python):
from collections import Counter
from math import gcd

N=int(input())

def factorize(x):
    i=2
    ret=[]

    while i*i<=x:
        while x%i==0:
            ret.append(i)
            x//=i
        
        i+=1
    
    if x>1:
        ret.append(x)
    
    return Counter(ret)

ans=1

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

ans-=1

cnt=1
for v in factorize(gcd(N,N-1)).values():
    cnt*=v+1
cnt-=1

ans-=cnt

k=2
while k*k<=N:
    if N%k==0:
        n=N//k
        while n%k==0:
            n//=k
        
        if n%k==1:
            ans+=1
    k+=1
ans+=1

print(ans)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]



MOD = 998244353
INF = int(1e15)


def divisor(N):
    res = []
    i = 2
    while i * i <= N:
        if N % i == 0:
            res.append(i)
            if i != N // i:
                res.append(N // i)
        i += 1
    if N != 1:
        res.append(N)
    return res


def solve():
    N = Scanner.int()
    d0 = divisor(N - 1)
    ans = len(d0)
    d1 = divisor(N)
    for d in d1:
        X = N
        while X % d == 0:
            X //= d
        if X % d == 1:
            ans += 1
    print(ans)


def main():
    
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()

Solution (Python):
def divisor(i):
    s = []
    for j in range(1, int(i ** (1 / 2)) + 1):
        if i % j == 0:
            s.append(i // j)
            s.append(j)
    return sorted(set(s))

n = int(input())
ans = 0
d = divisor(n)
d.pop(0)
for i in d:
    x = n
    while True:
        if not x % i == 0:
            break
        x //= i
    if x % i == 1:
        ans += 1
d = divisor(n - 1)
ans += len(d)
ans -= 1
print(ans)

Solution (Python):



from copy import copy, deepcopy 













import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    n = int(input())

    import math

    

    def make_prime_list_2(num):
        if num < 2:
            return []

        
        prime_list = [i for i in range(num + 1)]
        prime_list[1] = 0  
        num_sqrt = math.sqrt(num)

        for prime in prime_list:
            if prime == 0:
                continue
            if prime > num_sqrt:
                break

            for non_prime in range(2 * prime, num, prime):
                prime_list[non_prime] = 0

        return [prime for prime in prime_list if prime != 0]

    def prime_factorization_2(num):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""

        if num <= 1:
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)

            dict_counter = {}  
            

            for prime in prime_list:
                while num % prime == 0:
                    if prime in dict_counter:
                        dict_counter[prime] += 1
                    else:
                        dict_counter[prime] = 1
                    num //= prime
            if num != 1:
                if num in dict_counter:
                    dict_counter[num] += 1
                else:
                    dict_counter[num] = 1

            return dict_counter

    def divisor_count(num):
        """numの約数の個数を求める"""
        if num < 0:
            return None
        elif num == 1:
            return 1
        else:
            divisor_num = 1
            dict_fact = prime_factorization_2(num)
            for value in dict_fact.values():
                divisor_num *= (value + 1)
            return divisor_num

    ans = divisor_count(n-1)

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

        
        return divisors

    l = make_divisors(n)

    def main():
        cnt = 0
        for i in l:
            if i==1: continue
            v = copy(n)
            while v % i == 0:
                v /= i
            v%=i
            if v==1: cnt += 1
        return cnt

    print(ans+main()-1)


resolve()

Solution (Python):
from collections import defaultdict

roots = defaultdict(list)
for k in range(2, 10 ** 6 + 1):
    ki = k * k
    while ki <= 10 ** 12:
        roots[ki].append(k)
        ki *= k


def factors(n):
    fhead = []
    ftail = []
    for x in range(1, int(n ** 0.5) + 1):
        if n % x == 0:
            fhead.append(x)
            if x * x != n:
                ftail.append(n // x)
    return fhead + ftail[::-1]


def solve(N):
    works = set()
    

    
    for d in factors(N):
        
        k = d
        if (N // d) % k == 1:
            assert k <= N
            works.add(k)
        if d == 1:
            
            works.update(factors(N - 1))
        elif d in roots:
            
            for k in roots[d]:
                if k > N:
                    break
                if (N // d) % k == 1:
                    works.add(k)
    works.discard(1)
    return len(works)


(N,) = [int(x) for x in input().split()]
print(solve(N))


if False:

    def brute(N, K):
        while N >= K:
            if N % K == 0:
                N = N // K
            else:
                N = N - K
        return N

    for N in range(2, 10000):
        count = 0
        for K in range(2, N + 1):
            temp = brute(N, K)
            if temp == 1:
                print(N, K, temp)
                count += 1
        print("
        assert count == solve(N)

Solution (Python):

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

    N = int(input())
    ans = 0

    
    div1 = set(make_divisors(N-1))
    ans += len(div1) - 1

    
    div2 = set(make_divisors(N))
    for k in div2:
        if k == 1:
            continue
        n = N
        while n % k == 0:
            n //= k
        if n % k == 1:
            ans += 1
    print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):
N = int(input())
def cd(n):
  ls = []
  for i in range(1,int(n**(1/2))+1):
    if n % i == 0:
      ls += [i, n//i]
  return ls

ans = len(set(cd(N-1))) - 1
for j in set(cd(N)):
  a = N
  if not j == 1:
    while a % j == 0:
      a //= j    
    if a % j == 1:
      ans += 1
print(ans)

Solution (Python):
N = int(input())
def cd(n):
  ls = []
  for i in range(1,int(n**(1/2))+1):
    if n % i == 0:
      ls += [i, n//i]
  return ls

ans = len(set(cd(N-1))) - 1
for j in set(cd(N)):
  a = N
  if not j == 1:
    while a % j == 0:
      a //= j    
    if a % j == 1:
      ans += 1
print(ans)

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

def chd(x,k):
  while x%k==0:
    x=x//k
  return int((x%k)==1)

count=0
for i in p:
  count+=chd(n,i)
for i in range(2,nms+1):
  if (n-1)%i==0:
    count+=1
    if i!=(n-1)//i:
      count+=1
print(count+1-(n==2))

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())
divsN = make_divisors(N)
divsN2 = make_divisors(N-1)
divsN.pop(0)

ans = len(divsN2)-1

for div in divsN:
    n = N
    while True:
        if n%div != 0 or n==1:
            break
        n //= div
    if n%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())
divsN = make_divisors(N)
divsN2 = make_divisors(N-1)
divsN.pop(0)

ans = len(divsN2)-1

for div in divsN:
    n = N+1-1
    while True:
        if n%div != 0 or n==1:
            break
        n //= div
    if n%div == 1:
        ans += 1

print(ans)

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))




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.remove(1)
    return divisors


def main():
    n = ni()

    ans = set()
    ans.add(n)
    for i in range(2, int(n ** (0.5)) + 1):
        tmp = n
        while tmp % i == 0:
            tmp //= i
        if (tmp - 1) % i == 0:
            ans.add(i)

    yaku = set(make_divisors(n - 1))

    ans = ans | yaku

    print(len(ans))


if __name__ == '__main__':
    main()

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





ans=[2]
if N not in ans:
    ans.append(N)
if (N%(N-1)!=0) and (N-1 not in ans):
    ans.append(N-1)
D=make_divisors(N)
for d in D:
    now=N
    if d==1:
        continue
    while now%d==0:
        now=now//d
    if now%d==1:
        if d not in ans:
            ans.append(d)


ans2=[]
for a in ans:
    i=1
    while a**i<=N:
        x=a**i
        now=N
        while now%x==0:
            now=now//x
        if now%x==1:
            if x not in ans2:
                ans2.append(x)

        i+=1

d2=make_divisors(N-1)
for d in d2:
    if d!=1 and (d not in ans2):
        ans2.append(d)

print(len(ans2))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

        return divisors
    
    N = int(input())

    div_1 = make_divisors(N)
    res = 0
    for k in div_1:
        if k == 1:
            continue
        n = N
        while n > 1:
            if n % k == 0:
                n //= k
            else:
                if n >= k:
                    n %= k
                else:
                    n -= k
        if n == 1:
            res += 1

    div_2 = make_divisors(N - 1)
    res += len(div_2) - 1
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
def main():
    N = int(input())
    P = []
    for k in range(1,1+int((N-1)**(1/2))):
        if (N-1)%k == 0:
            P.append((N-1)//k)
            P.append(k)
    P = set(P)
    ans = len(P)
    for k in range(2,1+int(N**(1/2))):
        if N%k == 0:
            t = N//k
            while t%k == 0:
                t //= k
            if t%k == 1:
                ans += 1
    print(ans)
if __name__ == '__main__':
    main()

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

def make_divs(n):
    divs = []
    i = 1
    
    while i*i<=n:
        if n%i==0:
            divs.append(i)
            
            if i!=n//i:
                divs.append(n//i)
        
        i += 1
    
    return divs

N = int(input())
ds = make_divs(N)
ans = 0

for d in ds:
    if d==1:
        continue
    
    N2 = N
    
    while N2%d==0:
        N2 //= d
    
    if (N2-1)%d==0:
        ans += 1
    
ans += len(make_divs(N-1))-1
print(ans)