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
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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)

    divisors.sort()
    return divisors


divs = make_divisors(N)
cnt = 0

for d in divs:
    if d == 1:
        continue
    rest = N // d
    while rest % d == 0:
        rest //= d
    if (rest - 1) % d == 0:
        cnt += 1

divs2 = make_divisors(N-1)
cnt += len(divs2) - 1

print(cnt)

Solution (Python):
N=int(input())
data=[]
for i in range(1,10**6+1):
    if (N-1)%i==0:
        j=(N-1)//i
        k=i
        if j!=1:
            data.append(j)
        if k!=1:
            data.append(k)

if not data:
    data.append(N-1)
    
data=set(data)
data=list(data)
data=sorted(data)
ans=len(data)
if N==2:
   ans=0


Data=[]

for i in range(1,10**6+1):
    if N%i==0:
        j=N//i
        k=i
        if j!=k:
            Data.append(j)
            Data.append(k)
            
        elif j==k:
            Data.append(j)
if not Data:
    Data.append(N)


Data=sorted(Data)
Data=list(set(Data))

from fractions import gcd
for num in Data:
    ori=N
    if num>1:
        while ori>=num :
            if ori%num==0:
                ori=ori//num
            else:
                ori=ori%num
        if ori==1:
            ans+=1
      

print(ans)

Solution (Python):
import sys


from collections import Counter, deque, defaultdict











readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    k = set()

    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

    divisors1 = divisors(n)
    divisors1.sort()

    for d in divisors1[1:]:
        x = n
        while x % d == 0:
            x = x // d
        if x % d == 1:
            k.add(d)

    divisors2 = divisors(n-1)
    divisors2 = set(divisors2)
    k = k.union(divisors2)
    k.discard(1)
    print(len(k))

if __name__ == '__main__':
    main()

Solution (Python):
from math import sqrt
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)

    divisors.sort()
    return divisors














def solve2(n):
    div1 = make_divisors(n-1)
    div2 = make_divisors(n)
    div = list(set(filter(lambda x: x > 1, div1 + div2)))
    ans = []
    for k in div:
        tmp = n
        while tmp % k == 0:
            tmp = tmp // k
            if tmp < k or tmp == 1:
                break
        tmp = tmp % k
        if tmp == 1:
            ans.append(k)
    return len(ans)

print(solve2(n))

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
def pf(x):
  ret={}
  for i in range(2,int(x**0.5)+1):
    while x%i==0:
      ret[i]=ret.get(i,0)+1
      x//=i
  if x>1:
    ret[x]=1
  return ret

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

D1=make_divisors(n)
D2=pf(n-1)
ans=0
cur=1
for i in D2.keys():
  cur*=D2[i]+1
ans+=cur

for i in D1:
  if i!=1:
    nn=n
    chk=False
    while nn%i==0:
      nn//=i
      chk=True
    if chk and nn%i==1:
      ans+=1
print(ans-1)

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


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

    
    return divisors


if n == 2:
    print('1')
elif n == 3:
    print('2')
else:
    div = set(make_divisors(n-1))
    div.add(2)
    div.add(n)
    div.remove(1)
    for i in range(2, 41):
        root = round(n ** (1/i))
        if root ** i == n:
            div.add(root)

    for j in make_divisors(n)[1:-1]:
        k = n // j
        while k % j == 0:
            k = k // j
        if k % j == 1:
            div.add(j)
    print(len(div))

Solution (Python):
a=int(input())
def div(n):
    div=set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.add(i)
            div.add(n//i)
            if i != n // i:
                div.add(i)
    return div
s=list((div(a)|div(a-1))|div(a+1))
def x(n,k):
  if k==1:
    return False
  else:
    while n>1 and n>k-1:
      if n%k==0:
        n=n//k
      else:
        n=n%k
    if n==1:
      return True
    else:
      return False
ans=0
for i in s:
  if x(a,i):
    ans+=1
    
  else:pass
print(ans)

Solution (Python):
import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors 
def main():
    n = int(input())
    r = len(make_divisors(n-1)) - 1
    d = make_divisors(n)
    for i in d:
        if i == 1:
            continue
        if i == 2:
            r += 1
            continue
        t = n
        while t % i == 0:
            t = t // i
        t = t % i
        if t == 1:
            r += 1
    return r
print(main())

Solution (Python):
def check(num,k):
    if(num<k):
        return num==1
    if(num % k==0):
        return check(num//k,k)
    else:
        return check(num%k,k)

n=int(input())

yakusu=[[],[]]
for i in range(2):
    kazu=n-i
    for j in range(1,kazu+1):
        if(j*j>kazu):
            break
        if(kazu%j==0):
            if(j!=1):
                yakusu[i].append(j)
            if(j*j!=kazu):
                yakusu[i].append(kazu//j)
    yakusu[i].sort()





ans=[]

for i in range(2):
    for y in yakusu[i]:
        if(check(n,y)):
            ans.append(y)

ans.sort()

print(len(ans))

Solution (Python):
def main():
    from collections import Counter as ct

    def soinsuu(a):
        yy, j = [], 2
        y = yy.append
        while(a > 1):
            for i in range(j, int(a**0.5)+1):
                if a % i == 0:
                    y(i)
                    a, j = a//i, i
                    break
            else:
                y(a)
                break
        return ct(yy)

    def soinsuu2(a):
        s = {1}
        for i, j in a.items():
            s2 = set()
            for k in range(1, j+1):
                for l in s:
                    s2.add(l*pow(i, k))
            s |= s2
        s.remove(1)
        return s

    n = int(input())

    ans = 0
    s = soinsuu(n)
    s2 = soinsuu2(s)
    for i in s2:
        m = n
        while m % i == 0:
            m //= i
        m -= 1
        if m % i == 0:
            ans += 1

    n -= 1
    ans2 = 1
    for i in soinsuu(n).values():
        ans2 *= i+1
    ans2 -= 1
    print(ans+ans2)


main()

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


N = int(input())
ans = len(make_divisors(N-1)) - 1
divisors = make_divisors(N)
for i in range(1, len(divisors)):
    tmp = N
    d = divisors[i]
    while tmp%d == 0:
        tmp //= d
    if tmp % d == 1:
        ans += 1
print(ans)

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

    divisors.sort()
    return divisors

n=int(input())
ans=len(m(n-1))-1
A=m(n)
for i in range(1,len(A)):
  s=n
  while s%A[i]==0:
    s=s//A[i]
  if s%A[i]==1:
    ans=ans+1
print(ans)

Solution (Python):
N=int(input())
def factors(x):
   t=[]
   for i in range(2, int(x**0.5)+1):
       if x % i == 0:
           t.append(i)
           if x//i!=i:
               t.append(x//i)     
   return t
ans=2+len(factors(N-1))
fac=factors(N)
for i in fac:
    n=N
    while n%i==0:
        n=n//i
    n=n%i
    if n==1:
        ans+=1
if N==2:
    print(1)
else:  
    print(ans)

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

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations
from itertools import accumulate
from math import ceil, sqrt, pi

N = int(input())

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

div1 = divisors(N)
div2 = divisors(N - 1)

cnt = defaultdict(int)
for d in div1:
    cnt[d] += 1
for d in div2:
    cnt[d] += 1

arr = list(cnt.keys())
arr.sort()


answer = 0

def check(n, k):
    
    if n < k:
        if n == 1:
            return 1
        else:
            return 0
    if n % k == 0:
        return check(n // k, k)
    else:
        return check(n % k, k)

for a in arr:
    if 2 <= a <= N:
        if check(N, a):
            answer += 1
print(answer)

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

def calc(n,x):
    if x==1: return n
    while n>=x:
        if n%x == 0:
            n //= x
        else:
            n %= x
    return n

n = int(input())

div_list = divisor(n)
ans = 0

for div in div_list:
    x = calc(n,div)
    if x==1: ans +=1

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

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


n = int(input())

res = -1

for i in range(1,int(n**0.5)+1):
    if (n-1)%i == 0:
        if i*i == n-1:
            res += 1
        else:
            res += 2
def divisor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass


pri = divisor(n)
pri.append(n)


for e in pri:
    tmp = n
    while tmp%e == 0:
        tmp = tmp//e
    if tmp%e == 1:
        res += 1

print(res)

Solution (Python):
import math


def solve(n):
    if n == 2:
        return 1
    res = 0

    
    m = int(math.sqrt(n - 1))
    for i in range(2, m + 1):
        if (n - 1) % i == 0:
            res += 2
    if m * m == n - 1:
        res -= 1
    res += 1

    
    
    res += 1
    divisors = []
    m = int(math.sqrt(n))
    for i in range(2, m):
        if n % i == 0:
            divisors.append(i)
            divisors.append(n // i)
    if n % m == 0 and m * m == n:
        divisors.append(m)
    elif n % m == 0:
        divisors.append(m)
        divisors.append(n // m)
    
    for p in divisors:
        q = n // p
        while q % p == 0:
            q = q // p
        if q % p == 1:
            res += 1
    
    return res


def solve_greed(n):
    for p in range(2, n + 1):
        m = n
        while m % p == 0:
            m = m // p
        if m % p == 1:
            print(p)


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(6) == 3
    assert solve(3141) == 13
    assert solve(314159265358) == 9


if __name__ == "__main__":
    test()
    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

if __name__ == "__main__":
    N = int(input())
    A = make_divisors(N)
    cnt = 0
    for a in A[1:]:
        n = N
        while n%a == 0:
            n = n//a
        if n%a == 1:
            cnt += 1
    print(cnt+len(make_divisors(N-1))-1)

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

    
    return divisors



n=int(input())
a=make_divisors(n)
cnt=0
use=set()
for k in a[1:]:
    t=n
    while t%k==0:
        t//=k
    if t%k==1:
        use.add(k)
b=make_divisors(n-1)
for i in b[1:]:
    use.add(i)
print(len(use))

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

def is_ok(k):
    if(k==1):
        return False
    _N = N
    while(_N>1):
        if(_N%k==0):
            _N//=k
        else:
            _N%=k
            break
    if(_N!=1):
        return False
    else:
        return True

cand = set(make_divisors(N)) | set(make_divisors(N-1))
cnt = 0
for i in list(cand):
    if(is_ok(i)):
        cnt += 1

print(cnt)

Solution (Python):

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)
    ass.sort()
    return ass

n = int(input())
d = divisor(n-1)

ans = len(d)-1
d2 = divisor(n)

for k in d2:
    if k == 1:
        continue
    s = n
    while s%k == 0:
        if s%k == 0:
            s = s//k
    s = s%k
    if s == 1:
        ans += 1
print(ans)

Solution (Python):
import math
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N = int(sys.stdin.buffer.readline())


@lru_cache(maxsize=None)
def func(n, k):
    if n < k:
        return n
    if n % k == 0:
        return func(n // k, k)
    else:
        
        return n % k


def test(N):
    cnt = 0
    for k in range(2, N + 1):
        c = func(N, k)
        if c == 1:
            cnt += 1
        print(k, c)
    print(cnt)


def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :rtype: list of int
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret





ans = len(get_divisors(N - 1))
for k in get_divisors(N):
    if (N - 1) % k == 0:
        continue
    p = N // k
    if p >= k:
        ans += func(N // k, k) == 1
print(ans)

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):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

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

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

    def yakusuu(N):
        n = int(N**.5)+1
        res1 = []
        res2 = []
        for i in range(1, n):
            if N%i==0:
                res1.append(i)
                if N!=i**2:
                    res2.append(N//i)
        res2.reverse()
        return res1+res2
        
    res = 0

    for i in range(2, n):
        if (N%i)!=1:
            res += check(i, N)
    res += len(yakusuu(N-1))

    print(res)

if __name__ == '__main__':
    main()

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


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd

sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def f(x,k,ans):
    if x < k:
        if x == 1:
            ans.append(k)
        return
    if x%k == 0:
        while x%k == 0:
            x //= k
        f(x,k,ans)
    else:
        f(x%k,k,ans)
    return
def divide(x):
    div=[]
    for check in range(1,int(x**0.5)+1):
        if(x%check==0):
            div.append(check)
            div.append(x//check)
    for check in range(1,int((x+1)**0.5)+1):
        if((x+1)%check==0):
            div.append(check)
            div.append((x+1)//check)
    div = list(set(div))
    div.sort()
    return div
def main():
    ans = []
    n = inp()
    Divide = divide(n-1)
    for e in Divide:
        if e == 1:
            continue
        f(n,e,ans)
    print(len(ans))
if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
N=[n]
import collections
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
t=prime_factorize(n-1) 
c = collections.Counter(t)
w=1
for i in c.values():
  w *= 1+i
w-=1



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

for i in t:
  n=N[0]
  while n%i==0:
    n//=i
  if n%i==1:
    w+=1
print(w)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def factor(n):
    res=[]
    for d in range(1,n+1):
        if d*d>n:break
        if n%d==0:
            res.append(d)
            res.append(n//d)
        if res[-1]==res[-2]:res.pop()
    return res[1:]

def main():
    n=II()
    ff=factor(n)
    ans=len(factor(n-1))
    for k in ff:
        for b in range(1,40):
            pw=pow(k,b)
            if n%pw==0 and (n//pw-1)%k==0:
                ans+=1
                
    print(ans)

main()

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    if n==2:
        ans=1
    else:
        ans=2
    for i in range(2,int(n**.5)+1):
        if n%i==0:
            k1=i
            k2=n//i
            N=n
            while N%k1==0:
                N//=k1
            if N%k1==1:
                ans+=1
            if k2!=k1:
                N=n
                while N%k2==0:
                    N//=k2
                if N%k2==1:
                    ans+=1
    n-=1
    for i in range(2,int(n**.5)+1):
        if n%i==0:
            if i==n//i:
            	ans+=1
            else:
                ans+=2
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
from fractions import gcd
n = int(input())
yakusuu = set()
ans = set()
for i in range(1, int((n-1)**(1/2))+1):
    if (n-1) % i == 0:
        yakusuu.add(i)
        yakusuu.add((n-1)//i)

for i in range(1, int(n**(1/2))+1):
    if n % i == 0:
        yakusuu.add(i)
        yakusuu.add(n//i)
yakusuu.remove(1)



for i in yakusuu:
    k = n
    if gcd(i, k) == 1:
        if k % i == 1:
            ans.add(i)
        continue

    k = n
    while k >= i:
        if k % i == 0:
            k //= i
        else:
            if k % i == 1:
                k = 1
            else:
                k = 0
    if k == 1:
        ans.add(i)

print(len(ans))

Solution (Python):
import math

N=int(input())
ans=0
L=[]
M=[]
if N==2:
	print(1)
	exit()
for i in range(2,int(math.sqrt(N))+1):
	if N%i==0:
		L.append(i)
		L.append(N//i)
for i in range(2,int(math.sqrt(N))+1):
	if (N-1)%i==0:
		L.append(i)
		L.append(N//i)

X=set(L)
Y=sorted(X)
for i in range(len(Y)):
	if N%Y[i]==1:
		ans+=1
	elif N%Y[i]==0:
		A=N//Y[i]
		while(1):
			if A%Y[i]==1:
				ans+=1
				break
			elif A%Y[i]==0:
				B=A//Y[i]
				if B==1:
					ans+=1
					break
				else:
					A=B
					continue
			else:
				break
print(ans+2)

Solution (Python):
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)
    divisors.append(n)
    return divisors


n=int(input())
div=make_divisors(n)
tmp_div=div
ctr=0


for k in div:
  tmp_div=div
  k_i=k 
  while n%(k_i*k)==0:
    k_i*=k
  if (n//k_i)%k==1:
    ctr+=1


div=make_divisors(n-1)
for k in div:
  if n%k==1:
    ctr+=1
print(ctr)

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

def mn(n):
    c = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i != 1:
                c += 1
            if i != n // i:
                c += 1
    return c
N = int(input())
r = mn(N-1)
rs = set()
for k in make_divisors(N):
    if k == 1:
        continue
    M = N
    while M%k == 0: 
        M //= k
    if (M-1) % k == 0:
        rs.add(k)
        r += 1

print(r)

Solution (Python):
n=int(input())
ans=0
def count_cases(n):
    n-=1
    cur=1
    cnt=0
    while cur*cur<=n:
        if n%cur==0:
            if n//cur!=cur:
                if (n+1)%(n//cur)==1:
                    cnt+=1

                if (n+1)%cur==1:
                    cnt+=1

            else:
                if (n+1)%cur==1:
                    cnt+=1

        cur+=1
    return cnt

ans+=count_cases(n)



cur=2
while cur*cur<=n:
    
    if n%cur==0:
        num=n
        div=cur
        while num%div==0:
            num//=div
        if num%div==1:
 
            ans+=1
        div=n//cur
        if cur!=(n//cur):
            num=n
            while num%div==0:
                num//=div
 
            if num%div==1:
                ans+=1
    cur+=1
print(1+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)

    divisors.sort()
    return divisors
d=make_divisors(n)[1:]
l=make_divisors(n-1)[1:]

ans=0
for i in d:
    m=n
    while m%i==0:
        m//=i
    if m%i==1:
        ans+=1
print(ans+len(l))

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

ans=0
def f(x):
    out=set()
    for i in range(1, int(x**(1/2))+1):
        if x%i==0:
            out.add(i)
            out.add(x//i)
    out=list(out)
    out.sort()
    return out[1:]

tmp=f(N)
for K in tmp:
    x=N
    while x>=K:
        if x%K==0:
            x=x//K
        else:
            x=x%K
            
    if x==1:
        ans+=1
        
tmp=f(N-1)
ans+=len(tmp)
print(ans)

Solution (Python):
import math
n=int(input())
ans=0
s=set()
s.add(1)
s.add(n)
s.add(n-1)
for i in range(2,math.ceil(math.sqrt(n))+1):
  nn=n
  key=0
  while nn % i ==0:
    nn=nn//i
    key=1
  if nn % i ==1:
    s.add(i)
    if key==0:
      s.add((nn-1)//i)
s.remove(1)
print(len(s))

Solution (Python):
N=int(input())
def make_divisors(n):
	divisors = []
	for i in range(1, int(n**0.5)+1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n//i)
	return divisors
ans=len(make_divisors(N-1))-1
d=make_divisors(N)
for i in d:
	if i==1:
		continue
	p=0
	n=N
	while p==0:
		n=n//i
		p=n%i
	if p==1:
		ans+=1
print(ans)

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

for i in range(2, int(n ** (1 / 2)) + 1):
  k = i
  while k <= n * i:
    k *= i
    if n % k == k // i:
      lst.add(i)
      break

for i in range(2, int(n ** (1 / 2)) + 1):
  if n % i == 1:
    lst.add(i)
    lst.add((n - 1) // i)

if n > 2:
  lst.add(n - 1)
lst.add(n)
print(len(lst))

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

a = []
for i in range(1,int(N**0.5)+1):
    if i**2 == N:
        a.append(i)
    elif N%i==0:
        a.append(i)
        a.append(N//i)

a.sort()

count=0
for i in a:
    if i!=1:
        M = N
        while M%i==0:
            M//=i
        if M%i == 1:
            count+=1

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


for i in b:
    if N%i==1:
        count+=1


print(count)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
count=0
for i in range(2,10**6+1):
    num=1
    while num<=n:
        if n%num==0:
            if (n//num-1)%i==0:
                count+=1
        num=num*i
if n>10**6:
    count+=1
for i in range(1,10**6+1):
    if (n-1)%i==0:
        if (n-1)//i>10**6:
            count+=1
print(count)

Solution (Python):

import sys
input = sys.stdin.readline
inputt = lambda: range(int(input()))
inputn = lambda n = 1: range(n)
inputi = lambda: map(int, input().split())
inputl = lambda: list(inputi())
from math import *
from heapq import *
from bisect import *
from operator import *
from functools import reduce, lru_cache
from collections import Counter, defaultdict
from builtins import *

def factor(n):
    i, l = 2, []
    while i * i <= n:
        if not n % i:
            l.append(i)
            n //= i
        else:
            i += 1
    l.append(n)
    return l

def T(n, k):
    while not n % k:
        n //= k
    return n % k == 1

N, = inputi()
R = reduce(mul, [v + 1 for v in Counter(factor(N - 1)).values()], 1) - 1
D = {1}
for n in factor(N):
    D |= {d * n for d in D}
for d in D:
    if d != 1 and T(N // d, d):
        R += 1
if N == 2:
    print(1)
else:
    print(R)

Solution (Python):
def divisor(n):
    x=[]
    y=[]
    for i in range(1,int(n**.5)+1):
        if n%i==0:
            x.append(i)
            y.append(n//i)
    if y[-1]==x[-1]:
        y=y[:-1]
    return x+y[::-1]
N=int(input())
a=0
d=divisor(N)
for K in d:
    if K==1:continue
    n=N
    while n>=K:
        if n%K==0:
            n//=K
        else:
            n%=K
    if n==1:
        a+=1
if N-1>1 and N-1 not in d:
    a+=len(divisor(N-1))-1
print(a)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
i = 2
ps = []
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
ps = make_divisors(N)
ps2 = make_divisors(N - 1)
res = 0
for x in (ps + ps2):
  if x == 1: continue
  y = N + 0
  while y % x == 0: y //= x
  if y % x == 1: res += 1
print(res)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



def make_divisors(n,sort=False):
    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)
    if sort:
        divisors.sort()
    return divisors

N = I()

D = make_divisors(N)
D2 = make_divisors(N-1)
ans = 0
for d in D:
    if d==1:
        continue
    i = 0
    temp = N
    while 1:
        if temp%d == 0:
            i += 1
            temp = temp//d
        else:
            break
    if temp%d == 1:
        ans += 1

print(ans+len(D2)-1)

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

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

n = ni()
p = divisor(n)
s = set()
for k in p:
    nk = n // k
    for t in divisor(nk - 1):
        s.add(t*k)
ans = 0
s.remove(1)
s.add(n)
for t in s:
    m = n
    while m % t == 0:
        m //= t
    if m % t == 1:
        ans += 1
print(ans)

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

def factoring(k): 
    import math
    dic = dict()
    n = int(math.sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] = count
    if k != 1: 
        dic[k] = 1
    return dic



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

dic1 = factoring(N - 1)


ans = 1
for i in dic1:
    ans *= (dic1[i] + 1)

ans -= 1 


lst = make_divisors(N) 

for i in lst:
    if i == 1:
        continue
    flag = False
    if (N // i) % i == 1:
        flag = True
    else:
        x = 1
        while N % x == 0:
            if x == N:
                flag = True
                break
            if (N // x) % i == 1:
                flag = True
                break
            x *= i
    if flag:
        ans += 1



print (ans)