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 sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    ans = {N}
    if N > 2: ans |= {N-1}
    for i in range(2, N): 
        if i ** 2 > N: break
        if (N - 1) % i == 0:
            ans |= {i}
            if i ** 2 < N - 1:
                ans |= {(N - 1) // i}
        if N % i == 0:
            k = N
            while k % i == 0:
                k //= i
            if k % i == 1: ans |= {i}
            if i ** 2 < N:
                k = N
                while k % i == 0:
                    k //= i
                if k % i == 1: ans |= {i}
    print(len(ans))
    


    return 0

if __name__ == "__main__":
    solve()

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

tmp = n - 1
ret = len(make_divisors(tmp)) - 1

tmplen = make_divisors(n)

for item in tmplen:
    if item == 1:
        continue
    val = n
    while True:
        if val % item == 0:
            val = val // item
        else:
            if val % item == 1:
                ret += 1
            break

print(ret)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    if n == 2:
        print(1)
        exit()

    def al_div(n):
        pn = 1
        div = []
        while pn**2 < n:
            if n%pn == 0:
                div.append(pn)
                div.append(n//pn)
            pn += 1
        if pn**2 == n:
            div.append(pn)
        return div
    ans = 0
    for i in al_div(n-1):
        if i == 1:
            continue
        else:
            if n%i == 1:
                ans += 1
    for i in al_div(n):
        if i == 1:
            continue
        ni = n
        while ni%i == 0:
            ni //= i
        if ni%i == 1:
            ans += 1

    print(ans)

    return

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

N = int(input())
divs = make_divisors(N)

divs2 = make_divisors(N-1)
ans = len(sorted(divs2))-1
for div in divs[1:]:
    tmp = N
    while tmp%div == 0:
        tmp //= div
    if tmp%div == 1:
        ans += 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2000)
def joken(a,n):
  if n==1:
    return 0
  elif a%n==0 and a//n>=n:
    return joken(a//n,n)
  elif a%n==1:
    return 1
  elif a%n==0 and a//n==1:
    return 1
  else:
    return 0
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())
c=len(make_divisors(N-1))
d=make_divisors(N)
a=0
for i in range(len(d)):
  a+=joken(N,d[i])
print(a+c-1)

Solution (Python):
import math
import copy
def prime_factorize(n):
    a = [n]
    for i in range(2, math.floor(n ** 0.5) + 1):
        if n % i == 0:
            a.append(i)
            if n // i != i:
                a.append(n // i)
    return a

N = int(input())
prime_n = prime_factorize(N)
prime_n_1 = prime_factorize(N - 1)

ans = 0
for i in prime_n:
    n = copy.deepcopy(N)
    while (n % i) == 0:
            n = n // i
    if (n % i) == 1:
        ans += 1
ans += len(prime_n_1)
if N > 2:
    print(ans)
else:
    print(1)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")

INF = float("inf")











N = int(input())
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
ans = {N}
li1 = make_divisors(N-1)[1:]
for er in li1:
    ans.add(er)
li0 = make_divisors(N)[1:-1]
for i in li0:
    n = N
    while n % i == 0:
        n /= i
    if (n-1) % i == 0:
        ans.add(i)
print(len(ans))

Solution (Python):
N=int(input())
import math
a=0
for i in range(1,int(math.sqrt(N-1))+1):
  if (N-1)%i==0:
    a+=2
    i+=1
  else:
    i+=1
a-=1

if int(math.sqrt(N-1))==math.sqrt(N-1):
  a-=1
for i in range(2,int(math.sqrt(N))+1):
  if N%i==0:
    t=N
    while t%i==0:
      t=t/i
    if t%i==1:
      a+=1
      i+=1
    else:
      i+=1
a+=1
print(a)

Solution (Python):
N=int(input())
import math
ans=0
for i in range(1,int(math.sqrt(N-1))+1):
  if (N-1)%i==0:
    ans+=2
    i+=1
  else:
    i+=1
ans-=1

if int(math.sqrt(N-1))==math.sqrt(N-1):
  ans-=1
for i in range(2,int(math.sqrt(N))+1):
  if N%i==0:
    temp=N
    while temp%i==0:
      temp=temp/i
    if temp%i==1:
      ans+=1
      i+=1
    else:
      i+=1
ans+=1
print(ans)

Solution (Python):

def pf(x):
    plist = [1]
    p = 2
    while x>1:
        t = 0
        while x%p==0:
            x /= p
            t += 1
        now = list(plist)
        for i in range(t):
            now = list(map(lambda y:int(y*p), now))
            plist.extend(now)
        if p>int(x**0.5)+1:
            p = x
        elif p==2:
            p = 3
        else:
            p += 2
    return plist
        
N = int(input())
ans = len(pf(N-1))-1
for x in pf(N)[1:]:
    M = N
    while M>1 and M%x==0:
        M //= x
    if M==1 or M%x==1:
        ans += 1
print(ans)

Solution (Python):
N=int(input())
k=2
ans=1
factors=[]
i=1
while i*i<N-1:
  if (N-1)%i==0:
    ans+=1
  i+=1
while k*k<=N:
  n=0
  while pow(k,n)<=N:
    if (N-pow(k,n))%(pow(k,n+1))==0:
      ans+=1
      break
    n+=1
  k+=1
print(ans)

Solution (Python):

import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def nu_of_factors1(n):
    result_set = set()
    sqrtn = int(n**0.5)
    for i in range(1,sqrtn+1):
        q, r = n/i, n%i
        if r == 0:
            result_set.add(q)
            result_set.add(i)
    return len(result_set)


def getDivisors(n):
    
    factors = []
    i = 1
    while i <= sqrt(n):

        if (n % i == 0):

            
            if (n / i == i):
                factors.append(i)
            else:
                
                factors.append(i)
                factors.append(n//i)
        i = i + 1
    return factors

n = INT()
ans = 0

ans+=nu_of_factors1(n-1) - 1

divisors = getDivisors(n)


for el in divisors:
    if(el!=1):
        temp = n
    else:
        continue

    flag = 1
    while(temp!=1):
        if((temp/el).is_integer()):
            temp/=el
            continue
        else:
            if(temp%el==1):
                ans+=1
            flag = 0
            break

    if(flag==1):
        ans+=1
print(ans)

Solution (Python):
"""
0, K, 2K, 3K, 4K, ... = N-1 のとき, 答え.
"""
def makediv(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 = 0
themakedivlist = makediv(n-1)
for i in themakedivlist:
	if i >= 2:
		ans += 1
k = makediv(n)
k.remove(1)
for i in k:
	tmpn = n
	while True:
		if tmpn == 1:
			ans += 1
			break
		elif tmpn % i == 0:
			tmpn //= i
		elif (tmpn-1) % i == 0:
			ans += 1
			break
		else:
			break
print(ans)

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np

Mod = 1000000007
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  
    def divisor(n):
        res = []
        for i in range(1, int(np.sqrt(n)) + 1):
            if n % i == 0:
                res.append(i)
                j = n // i
                if j != i:res.append(j)
        res.sort(reverse = True)
        return res[::-1]
    n = int(input())
    div1 = divisor(n - 1)
    div2 = divisor(n)
    ans = len(div1) - 1
    for d in div2:
        if d == 1: continue
        nn = n
        while nn % d == 0:
            nn //= d
        if nn % d == 1:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

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]


c = collections.Counter(prime_factorize(N-1))
ans = 1
lis = make_divisors(N)

for i in c.values():
    ans *= i+1
ans -=1

for i in lis:
    if i==1:continue
    tmp = N
    while tmp%i==0:
        tmp //= i
    if tmp%i==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())
l = make_divisors(n - 1)
l2 = make_divisors(n)
del l2[0]
ans = len(l) - 1
for i in l2:
    k2 = n
    while True:
        if k2 % i == 1:
            ans += 1
        k2 /= i
        if k2 % 1 != 0:
            break
print(ans)

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


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


L1 = factorization(N - 1)
s = 1

for [a, b] in L1:
    s *= (b + 1)



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]


for i in set(make_divisors(N))-{1}:
    temp = N
    while temp % i == 0:
        temp //= i
    if (temp-1) % i == 0:
        s += 1
s -= 1
if N == 2:
    print(1)
else:
    print(s)

Solution (Python):
n=int(input())
orgn=n
m=n-1
orgm=m
ncounter=1
mcounter=1
for i in range(2,int(m**0.5)+1):
	if m % i == 0:
		tmpc=1
		m //= i
		while m % i ==0:
			tmpc += 1
			m //= i
		mcounter *= tmpc + 1

if m == orgm and m != 1:
	mcounter += 1
elif m > int(orgm**0.5):
	mcounter *= 2
mcounter -= 1


for i in range(2,int(n**0.5)+1):
	if orgn % i == 0:
		n = orgn // i
		while n % i ==0:
			n //= i
		if n % i == 1:
			ncounter += 1

print(ncounter+mcounter)

Solution (Python):


import sys
sys.setrecursionlimit(300000)


def solve(N: int):
    if N < 5:
        print(N - 1)
        return
    i = 2
    ret = 2
    while i * i <= N:
        tmp = N
        while tmp % i == 0:
            tmp //= i
        tmp %= i
        if tmp == 1:
            ret += 1

        if N % i == 1 and i * i + 1 != N:
            ret += 1
        i += 1
    print(ret)
    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())
from math import sqrt


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

K_1 = divisor(N-1)
K_2 = divisor(N)
K_3 = []
count = 0
for k in K_2:
    temp = N
    while temp % k == 0:
        temp //= k
    if temp == 1 or temp % k == 1:
        count += 1
        K_3.append(k)
kk = K_1 + K_3
ans = len(set(kk))
print(ans)

Solution (Python):
from math import sqrt, ceil


def divisors(n):
    out = []
    nn = ceil(sqrt(n))
    for i in range(1, nn):
        if n % i == 0:
            out.append(i)
            out.append(n//i)

    if nn ** 2 == n:
        out.append(nn)

    out.sort()
    return out


n = int(input())
a = len(divisors(n-1)[1:])

d = divisors(n)
for dd in d[1:]:
    nn = n
    while nn % dd == 0:
        nn = nn // dd
    if nn % dd == 1:
        a += 1

print(a)

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


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


def main():
    N = int(input())
    ans = 0
    for cand in divisors(N):
        if is_ok(N, cand):
            ans += 1
    for cand in divisors(N-1):
        if is_ok(N, cand):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

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

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

cnt = 0
for i in range(1, int((n-1)**0.5)+1):
    if (n - 1) % i == 0:
        if i ** 2 == n - 1:
            cnt += 1
        else:
            cnt += 2

res = cnt - 1
for v in div[1:]:
    tmp = n
    while tmp % v == 0:
        tmp //= v
    if tmp % v == 1:
        res += 1

print(res)

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

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

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

divs1 = make_divisors(n - 1)
divs2 = make_divisors(n)
ans = set(divs1[1:])

for kk in divs2[1:]:
    A = n
    while True:
        if A % kk == 0:
            A //= kk
        else:
            break

    if (A - 1) % kk == 0:
        ans.add(kk)

ans.add(n)
print(len(ans))

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


for i in range(1,int(pow(n-1,0.5)) + 1):
    if (n-1) % i == 0:
        ans.add((n-1)//i)
        ans.add(i)

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

Solution (Python):

def check(N,K):
    while N % K == 0:
        N //= K
    return (N % K == 1)

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


N = int(input())

divi = divisor(N)

ans = 0

for x in divi:
    if x > 1:
        ans += int(check(N,x))

ans += len(divisor(N - 1)) - 1
print(ans)

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

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

    
    return divisors

ans = len(make_divisors(N-1))-1
ls = make_divisors(N)[1:]

for i in ls:
    n = N
    while n % i == 0:
        n //= i
    if n % i == 1:
        ans += 1

print(ans)

Solution (Python):
N = int(input())
ans = 0
wnasi = []
for i in range(1, int(pow(N - 1, 0.5)) + 1):
    if (N - 1) % i == 0:
        wnasi.append(i)
        if i != (N - 1) // i:
            wnasi.append((N - 1) // i)
ans += len(wnasi) - 1
wari = []
for i in range(2, int(pow(N, 0.5)) + 1):
    if N % i == 0:
        wari.append(i)
        if i != N // i:
            wari.append(N // i)

for i in wari:
    if i == 1:
        continue
    tmpN = N
    while True:
        if tmpN % i == 0:
            tmpN //= i
        else:
            if tmpN % i == 1:
                ans += 1
            break

print(ans + 1)

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

def divisors(n):
    ret1 = []
    ret2 = []
    i = 1
    while i**2 <= N:
        if n%i == 0:
            ret1 += [i]
            ret2 += [n//i]
        i += 1
    return ret1 + ret2

ans1 = len(set(divisors(N-1))) - 1
ans2_cand = set(divisors(N))
ans2 = 0
for k in ans2_cand:
    if k == 1: continue
    n = N
    while n%k == 0:
        n = n//k
    if n%k == 1:
        ans2 += 1


print(ans1 + ans2)

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

def divisors(n):
    ret1 = []
    ret2 = []
    i = 1
    while i**2 <= N:
        if n%i == 0:
            ret1 += [i]
            ret2 += [n//i]
        i += 1
    return ret1 + ret2

ans1 = set(divisors(N-1))
ans2_cand = set(divisors(N))
ans2 = 0
for k in ans2_cand:
    if k == 1: continue
    n = N
    while n%k == 0:
        n = n//k
    if n%k == 1:
        ans2 += 1


print(len(ans1) + ans2 -1)

Solution (Python):

import sys

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

N = ir()

answer = 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)
    divisors.sort()
    return divisors[1:]

cand = make_divisors(N) + make_divisors(N-1)
for x in cand:
    M = N
    while M % x == 0:
        M //= x
    r = M % x
    if r == 1:
        answer += 1

print(answer)

Solution (Python):



N = int(input())

"""
愚直にやると、Kを2～Nの範囲で全部調べて数え上げる。N <= 10**12 なので間に合わない。


たとえば N=100だと、
[2, 3, 4, 9, 10, 11, 33, 99, 100]
が条件を満たす数字になる。

割り算を行わないとき、明らかに N % K = 1 になる
これは、「NをKで割ったら、１あまる」であるから、「N-1をKでわったら割り切れる」ともいえる。
なので、割り算が起こらないものは、N-1の約数。

割り算が起こるやつは、割れるだけ割った後、余りを調べればよい。
"""



def solve(n):
    i = 1
    ret = set()
    while i * i <= n:
        if n % i == 0:
            ret.add(i)
            ret.add(n // i)
        i += 1

    return ret


div_N_sub_1 = solve(N-1)
div_N = solve(N)

ans = len(div_N_sub_1) - 1

for i in div_N:
    if i == 1:
        continue
    tmp = N
    while tmp % i == 0:
        tmp //= i
    if tmp % i == 1:
        ans += 1


print(ans)

Solution (Python):



import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
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
u=len(make_divisors(n-1))-1
lis=make_divisors(n)
lis.remove(1)

def divsub(n,k):
    flag=True
    while flag==True:
        n//=k
        if n%k==1:
            return 1
            flag=False
        elif n%k!=0:
            return 0
            flag=False

ans=0
for i in range(len(lis)):
    ans+=divsub(n,lis[i])
print(ans+u)

Solution (Python):
N = int(input().split()[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

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

for d in divs:
    c = N
    while True:
        if d == 1:
            break
        if c%d == 1:
            Nod.append(d)
            break
        elif c%d == 0:
            c = c//d;
            continue
        else:
            break

print(len(Nod)-1)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    max_i = int(math.log2(N))
    div = []
    for i in range(1,int(math.sqrt(N))+1):
        if N % i == 0:
            div.append((i,N//i)); div.append((N//i,i))

    ans = 0
    for a,b in div:
        if a == 1:
            for i in range(1,int(math.sqrt(b-1))+1):
                if (b-1) % i == 0:
                    p = 2 - (i*i == b-1) - (i == 1)
                    ans += p
        else:
            for i in range(1,max_i+1):
                c = round(math.pow(a,1/i))
                if c ** i == a:
                    if b % c == 1: ans += 1
    print(ans)

if __name__ == '__main__':
    main()

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



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

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

Solution (Python):
from sys import stdin, setrecursionlimit


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


def main():
    input = stdin.buffer.readline
    n = int(input())
    ans = 1
    if n > 2:
        ans += 1
    for i in range(2, int((n - 1) ** 0.5) + 1):
        if (n - 1) % i == 0:
            ans += 1
            if i != (n - 1) // i:
                ans += 1
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            if check(n, i):
                ans += 1
            if check(n, n // i) and i != n // i:
                ans += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

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

def check(N, k):
    if k<2:
        return False
    N //= k
    while N:
        if (N-1)%k==0:
            return True
        if N%k:
            return False
        N //= k

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

ans.remove(1)
print(len(ans))

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

def check(N, k):
    if k<2:
        return False
    N //= k
    while N:
        if (N-1)%k==0:
            return True
        if N%k:
            return False
        N //= k
    return False


for k in range(1, int(N**0.5)+1):
    if (N-1)%k==0:
        k1, k2 = k, (N-1)//k
        ans.add(k1)
        ans.add(k2)
    if N%k==0:
        k1, k2 = k, N//k
        if check(N, k1):
            ans.add(k1)
        if check(N, k2):
            ans.add(k2)

ans.remove(1)
print(len(ans))

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

if n == 2:
  count = 1
else:
  count = 2
divisor = []

d = 2
while d * d < n - 1:
  if (n - 1) % d == 0:
    count += 2
  d += 1
if d * d == n - 1:
  count += 1

d = 2
while d * d < n:
  if n % d == 0:
    divisor.append(d)
    divisor.append(n // d)
  d += 1
if d * d == n:
  divisor.append(d)

for d in divisor:
  tmp = n
  while tmp % d == 0:
    tmp //= d
  if tmp % d == 1:
    count += 1

print(count)

Solution (Python):






import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


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 lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count





N = inputI()

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

def Base_10_to_n(X, n):
  if (int(X/n)):
     return Base_10_to_n(int(X/n), n)+" "+str(X%n)
  return " "+str(X%n)

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

d = make_divisors(N)+make_divisors(N-1)



ans = 0
for x in d:
  l = list(Base_10_to_n(N, x).split())
  for i in l[::-1]:
    if i == "0":
      continue
    else:
      if i == "1":
        ans += 1
        break
      else:
        break

print(ans+2)

Solution (Python):
import queue

N = int(input())

def common_divisors(n):
    i = 1
    res = []
    while i*i <= n:
        if n % i == 0:
            res.append(i)
            res.append(n//i)
        if i*i == n:
            res.pop()
        i += 1
    return res

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

for i in common_divisors(N):
    if i == 1:
        continue
    n = N
    while n % i == 0:
        n /= i
    if n % i == 1:
        ans += 1
print(ans)

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

    divisors.sort()
    return divisors


N = int(input())
N_div = make_divisors(N)[1:]
N1_div = make_divisors(N-1)[1:]

ans = len(N1_div)

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

Solution (Python):
def check(n, i):
    while n >= i and n % i == 0:
        n //= i
    return n % i == 1

def main():
    N = int(input())
    i = 2
    r = set()
    while i * i <= N:
        if N % i == 0:
            if check(N, i):
                r.add(i)
            if check(N, N // i):
                r.add(N // i)
        elif N % i == 1:
            r.add(i)
            if check(N, N // i):
                r.add(N // i)
        i += 1
    if N > 2:
        r.add(N - 1)
    r.add(N)
    return len(r)

print(main())