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

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
import sys
sys.setrecursionlimit(10**7)
def func(N,d):
    if d==1:
        return False
    while N>1:
        if N%d==0:
            N//=d
        else:
            if (N-1)%d==0:
                N=1
            else:
                N=0
    return True if N==1 else False

ans=len(set(make_divisors(n-1)))-1
l=set(make_divisors(n))
for li in l:
    if func(n,li):
        ans+=1
print(ans)

Solution (Python):

def solve1(n):
    
    res = []
    for i in xrange(1, 100):
        u = int(pow(n, 1.0 / i) + 0.1)
        if u ** i == n:
            res.append(u)
    return set(res)

def solve2(n):
    
    m = n - 1

    i = 1
    res = set()
    while i * i <= m:
        if m % i == 0:
            res.add(i)
            res.add(m / i)
        i += 1
    return res ^ set([1])

def solve3(n):
    i = 2
    res = set()
    while i * i <= n:
        if n % i == 0:
            m = n / i
            while m and m % i == 0:
                m /= i
            if m % i == 1:
                res.add(i)
        i += 1
    return res

def brute_force(n):
    res = []
    for i in xrange(2, n + 1):
        m = n
        while m % i == 0:
            m /= i
        m %= i
        if m == 1:
            res.append(i)
    
    return len(res)

def solve(n):
    s1 = solve1(n)
    s2 = solve2(n)
    s3 = solve3(n)
    
    return len(s1 | s2 | s3)

assert solve(6) == 3
assert solve(3141) == 13
assert solve(314159265358) == 9

assert solve(10 ** 12)

import random
for i in xrange(2, 100):
    assert brute_force(i) == solve(i)

n = int(raw_input())
print solve(n)

Solution (Python):

N = int(input())

def prime_cnt(N):
    
    prime, i = set([2]), 1
    while i * i <= N:
        if N % i == 0:
            prime.add(i)
            prime.add(N//i)
        i += 1
    prime.remove(1)
    return prime
import math
ans = 0
ans = prime_cnt(N-1)
p = prime_cnt(N)
for i in p:
    n = N
    while n % i == 0:
        n /= i
    if (n-1) % i == 0:
        ans.add(i)

print(len(ans))

Solution (Python):
def divisor(n):
  list1 = []
  for i in range(1, int(n ** (0.5)) + 1):
    if n % i == 0:
      list1.append(i)
      list1.append(int(n / i))
  list1 = list(set(list1))
  return len(list1) - 1

def function(n):
  ans = 0
  if n >= 2:
    ans += 1
  for i in range(2, int(n ** (0.5)) + 1):
    m = n
    if m % i == 0:
      while m % i == 0:
        m = int(m / i)
      if m % i == 1:
        ans += 1
  ans += divisor(n - 1)
  return ans
n = int(input())
print(function(n))

Solution (Python):
import numpy as np

def divisors(N):
    return sorted(sum((list({n, N // n}) for n in range(1, int(N ** 0.5) + 1) if not N % n), []))

def prime_factorize_dict(n):
    d = dict()
    while not n & 1:
        d[2] = d.get(2, 0) + 1
        n >>= 1
    f = 3
    while f * f <= n:
        if not n % f:
            d[f] = d.get(f, 0) + 1
            n //= f
        else:
            f += 2
    if n != 1:
        d[n] = d.get(n, 0) + 1
    return d

N = int(input())
count = 0
for n in divisors(N)[1:]:
    M = N
    while not M % n:
        M //= n
    count += M % n == 1
fact_Nm1 = np.array(list(prime_factorize_dict(N - 1).values()), dtype=np.int32)
print(count + np.prod(fact_Nm1 + 1) - 1)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def get_yakusu(n):
    ans = set()
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            if i != 1:
                ans.add(i)
            if n // i != i:
                ans.add(n // i)
    return ans

def main():
    N = I()
    cnt = 0
    if N == 2:
        print(1)
        return
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        while True:
            if cpN % n == 0:
                cpN = cpN // n
            else:
                break
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def get_yakusu(n):
    ans = set()
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            if i != 1:
                ans.add(i)
            if n // i != i:
                ans.add(n // i)
    return ans

def main():
    N = I()
    cnt = 0
    if N == 2:
        print(1)
        return
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        while True:
            if n == 1:
                break
            if cpN % n == 0:
                cpN = cpN // n
            else:
                break
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def get_yakusu(n):
    ans = set()
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            if i != 1:
                ans.add(i)
            if n // i != i:
                ans.add(n // i)
    return ans

def main():
    N = I()
    cnt = 0
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    if N == 2:
        print(1)
        return
    for n in yakusu:
        cpN = N
        while True:
            if n == 1:
                break
            if cpN % n == 0:
                cpN = cpN // n
            else:
                break
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def get_yakusu(n):
    ans = set()
    for i in range(1, int(math.sqrt(n)) + 2):
        if n % i == 0:
            if i != 1:
                ans.add(i)
            if n // i != i:
                ans.add(n // i)
    return ans

def main():
    N = I()
    cnt = 0
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        while True:
            if n == 1:
                break
            if cpN % n == 0:
                cpN = cpN // n
            else:
                break
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def get_yakusu(n):
    ans = set()
    for i in range(1, int(math.sqrt(n)) + 2):
        if n % i == 0:
            if i != 1:
                ans.add(i)
            if n // i != i:
                ans.add(n // i)
    return ans

def main():
    N = I()
    cnt = 0
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        loop = 0
        while True:
            loop += 1
            if loop > 100:
                break
            if cpN % n == 0:
                cpN = cpN // n
            else:
                break
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()

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

cnt=0
import math

result=set([])

for i in range(1,int(math.sqrt(n-1))+1):
    if (n-1)%i==0:
        for item in [i,(n-1)//i]:
            if item!=1:result.add(item)

for i in range(1,int(math.sqrt(n))+1):
    if n%i==0:
        for item in [i,n//i]:
            if item!=1:
                N=n
                while N%item==0:N=N//item
                if N==1:result.add(item)
                elif N%item==1:result.add(item)

print(len(result))

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N=int(input())
    Nd=set()
    for n in range(1,int(N**0.5)+1):
        if N%n==0:
            Nd.add(n)
            Nd.add(N//n)
    N1d=set()
    for n in range(1,int((N-1)**0.5)+1):
        if (N-1)%n==0:
            N1d.add(n)
            N1d.add((N-1)//n)
    for d in Nd:
        if d==1: continue
        n=N
        while n%d==0: n//=d
        if n%d==1: N1d.add(d)
    print(len(N1d)-1)

if __name__ == '__main__':
    main()

Solution (Python):
num = int(input())
n = num
num -= 1
result = 1
for i in range(2, int(pow(num, 0.5))+1):
    c = 0
    while num%i==0:
        num //= i
        c += 1
    if c>0:
        result *= c+1

if num > 1:
    result *= 2
result -= 1

r = set()
for i in range(2, int(pow(n, 0.5))+1):
    num = n
    if num%i==0:
        r.add(i)
        r.add(n//i)
r.add(n)
for i in r:
    num = n
    while num%i==0:
        num //= i
    if num%i == 1:
        result += 1

print(result)

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

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

Solution (Python):


import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

def divisor(N):
    res = []

    for i in range(1, int(math.sqrt(N)) + 1):
        if N % i != 0:
            continue

        res.append(i)
        if i * i != N:
            res.append(N/i)
    
    return res

N = I()

ans = 0
for x in divisor(N):
    if x == 1:
        continue
    
    tmp = N
    while tmp % x == 0:
        tmp /= x
    tmp %= x

    if tmp == 1:
        ans += 1

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

print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = [2]
        for j in range(4, m, 2):
            a[j] = False
        for i in range(3, m, 2):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False
        self.ds_memo = {}
        self.ds_memo[1] = set([1])

    def is_prime(self, n):
        return self.A[n]

    def division(self, n):
        d = collections.defaultdict(int)
        for c in self.T:
            while n % c == 0:
                d[c] += 1
                n //= c
            if n < 2:
                break
        if n > 1:
            d[n] += 1
        return d.items()

    
    def divisions(self, n):
        if n in self.ds_memo:
            return self.ds_memo[n]

        for c in self.T:
            if n % c == 0:
                rs = set([c])
                for cc in self.divisions(n // c):
                    rs.add(cc)
                    rs.add(cc * c)
                self.ds_memo[n] = rs
                return rs

        rs = set([n])
        self.ds_memo[n] = rs
        return rs


def main():
    n = I()

    pr = Prime(10**12)
    d = list(pr.division(n))
    r = 0
    l = len(d)
    for i in range(1, 2**l):
        t = [d[j] for j in range(l) if 2**j & i]
        m = min(map(lambda x: x[1], t))
        ok = True
        for k,v in t:
            if v % m > 0:
                ok = False
                break
        if not ok:
            continue
        for j in range(1,m+1):
            if m % j > 0:
                continue
            mk = m // j
            u = 1
            for k,v in t:
                u *= k**((v//m)*mk)
            nn = n
            while nn % u == 0:
                nn //= u
            if nn % u == 1:
                r += 1
            

    d = pr.division(n-1)
    
    k = 1
    for _,v in d:
        k *= v + 1
    r += k - 1

    return r

print(main())

Solution (Python):
def divisor(n):
    res = []
    
    i = 1
    while i*i <= n:
        if not n % i:
            res.append(i)
            if (i*i != n): res.append(n//i)     
        
        i += 1
        
    return res

N = int(input())
ans = 0

for d in divisor(N):
    if d == 1: continue
    n = N
    
    while not n % d:
        n //= d
        
    if n%d == 1: ans += 1
    
print(ans + len(divisor(N-1))-1)

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

def f(N, i):
    if i == 1:
        return False
    while N%i == 0:
        N //= i
    if N%i == 1:
        return True
    else:
        return False
        
ans = 0
i = 1
while i <= N**0.5:
    if N%i > 0:
        i += 1
        continue
    if f(N, i):
        ans += 1
    if i%(N//i) == 1:
        ans += 1
    i += 1

i = 1
while i <= (N-1)**0.5:
    if (N-1)%i > 0:
        i += 1
        continue
    if N%i == 1 and N//i != i:
        ans += 1
    if N%((N-1)//i) == 1:
        ans += 1
    i += 1

print(ans)

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

    
    return divisors

N = int(input())
ans = 0
divs = make_divisors(N)
divs = [x for x in divs if x > 1]
for k in divs:
    x = N
    while x % k == 0:
        x //= k
    if x % k == 1:
        ans += 1

divs = make_divisors(N - 1)
divs = [x for x in divs if x > 1]
ans += len(divs)
print(ans)

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


def factor(n):
    res=set()
    for i in range(2,int(n**(1/2))+10):
        if n%i == 0:
            res.add(i)
            res.add(n//i)

    res.add(n)
    res.discard(1)
    return list(res)

ans = 0

ans += len(factor(n-1))


for k in factor(n):
    n2=n
    if k==1:
        continue
    while n2%k==0:
        n2//=k
    if n2%k == 1:
        ans +=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

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


for i in range(2,int(N ** 0.5) + 1):
  if N % i == 0:
    if check(N,i):
      ans += 1


ans += 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

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


for i in range(2,int(N ** 0.5) + 1):
  if N % i == 0:
    if check(N,i):
      ans += 1


ans += 1

print(ans)

Solution (Python):


import sys
import math










from itertools import starmap                
from itertools import product, permutations  









def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()

    
    
    
    
    
    
    
    
    
    
    
    

    class Eratos:
        def __init__(self, num):
            assert(num >= 1)
            self.table_max = num
            
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            for i in range(2, int(math.sqrt(num)) + 1):
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    
                        self.table[j] = False
            
            self.prime_numbers = [2] if self.table_max >= 2 else []
            for i in range(3, self.table_max + 1, 2):
                if self.table[i]:
                    self.prime_numbers.append(i)
        
        def is_prime(self, num):
            """
            >>> e = Eratos(100)
            >>> [i for i in range(1, 101) if e.is_prime(i)]
            [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
            """
            assert(num >= 1)
            if num > self.table_max:
                raise ValueError('Eratos.is_prime(): exceed table_max({}). got {}'.format(self.table_max, num))
            return self.table[num]
        
        def prime_factorize(self, num):
            """
            >>> e = Eratos(10000)
            >>> e.prime_factorize(6552)
            {2: 3, 3: 2, 7: 1, 13: 1}
            """
            assert(num >= 1)
            if int(math.sqrt(num)) > self.table_max:
                raise ValueError('Eratos.prime_factorize(): exceed prime table size. got {}'.format(num))
            factorized_dict = dict()    
            candidate_prime_numbers = [i for i in range(2, int(math.sqrt(num)) + 1) if self.is_prime(i)]
            
            
            for p in candidate_prime_numbers:
                
                if num == 1:
                    break
                while num % p == 0:
                    num //= p
                    try:
                        factorized_dict[p]
                    except KeyError:
                        factorized_dict[p] = 0
                    finally:
                        factorized_dict[p] += 1
            if num != 1:
                factorized_dict[num] = 1
            return factorized_dict
    

    eratos = Eratos(int(math.sqrt(n)))
    d_1 = eratos.prime_factorize(n - 1)
    
    cnt = 0
    tmp = 1
    for _, v in d_1.items():
        tmp *= (v + 1)
    tmp -= 1
    cnt += tmp
    d_2 = eratos.prime_factorize(n)
    
    
    L = [range(v + 1) for _, v in d_2.items()]
    power_list = list(product(*L))
    prime_list = list(d_2.keys())
    for elm in power_list:
        
        div = 1
        for i in range(len(prime_list)):
            div *= pow(prime_list[i], elm[i])
        
        if div != 1:
            assert(n % div == 0)
            copy_n = n
            while copy_n % div == 0:
                copy_n //= div
            if copy_n % div == 1:
                cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin, stdout
import math
import bisect
import datetime
from collections import defaultdict
import random

def bl_solve(a):
    ans = []
    for k in range(2, a + 1):
        tmp = a
        while tmp > 0:
            if tmp % k == 0:
                tmp = tmp // k
            else:
                tmp -= k
            if tmp == 1:
                ans.append(k)
                break
    return ans

def bl_solve2(a):
    if a == 2:
        ans = 1
    else:
        ans = 2
    for k in range(2, int(math.sqrt(a))+1):
        tmp = a
        while tmp >= k:
            if tmp % k == 0:
                tmp = tmp // k
            else:
                tmp %= k
        if tmp == 1:
            ans+=1
        if (a - 1) % k == 0 and k != math.sqrt(n - 1):
            ans+=1
    return ans

def fj(a):
    arr = defaultdict(int)
    i = 2
    while i <= math.sqrt(a):
        while a % i == 0:
            a //= i
            arr[i] += 1
        i += 1
    if a != 1:
        arr[a] += 1
    ans = 1
    for key, value in arr.items():
        ans *= (value + 1)
    return ans-1

def solve(a):
    if a == 2:
        return 1
    ans = fj(a - 1)
    i = 2
    while True:
        tmp = round(a**(1 / i))
        if tmp ** i == a:
            ans += 1
        if tmp < 2:
            break
        i+=1
    return ans + 1
    

n = int(stdin.readline().strip())

ans = bl_solve2(n)
stdout.writelines(str(ans)+'\n')

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    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
    
    ans=set(make_divisors(N-1))
    ans=ans - set([1])
    ans.add(2)
    
    L=make_divisors(N)
    
    for i in range(1,len(L)):
        temp=L[i]
        N2=N
        while N2>=temp:
            if N2%temp==0:
                N2=N2//temp
            else:
                N2=N2%temp
        if N2==1:
            ans.add(temp)
            
        
            
    
    print(len(ans))

        

main()

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

ans=[]
for K in range(2,int(init**0.5)+1):
    N=init
    while N%K==0:
        N/=K
    if N-(N//K)*K==1:
        ans.append(K)
        
tgt=init-1
cand=[]
for i in range(1,int(init**0.5)+1):
    if tgt%i==0:
        cand.append(i)
        if i!=tgt//i:
            cand.append(tgt//i)
ans=list(set(ans+cand))
print(len(ans))

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

box = make_divisors(n-1)
ans = len(box)-1
boxn = make_divisors(n)
for i in range(1,len(boxn)):
    k = boxn[i]
    nn = copy.deepcopy(n)
    while nn % k == 0 and nn >= k:
        nn = nn // k

    if nn % k == 1:
        ans += 1

print(ans)

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

def yakusu(x):
    xx = 2
    y = []
    while xx**2 < x:
        if x%xx == 0:
            y.append(xx)
            y.append(x//xx)
        xx += 1
    if xx**2 == x:
        y.append(xx)
    y.append(x)
    return y
    
if n == 2:
    ans = 0
else:
    ans = len(yakusu(n-1))

for i in yakusu(n):
    nn = n
    while True:
        if nn%i == 0:
            nn = nn//i
        else:
            break
    if nn%i == 1:
        ans += 1

print(ans)

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict


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


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

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

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

	
	ans = 0
	for i in div:
		if i == 1:
			continue
		N = K
		while True:
			if N % i == 0:
				N = int(N // i)
			else:
				if N % i == 1:
					ans += 1
				break

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

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

	print(ans - 1)



if __name__ == '__main__':
	main()

Solution (Python):
import math
def calc_yakusu_num(n):
    num = 0

    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            if i == n // i:
                num += 1
            else:
                num += 2
    return num - 1
    
def calc_yakusu(n):
    yakusu = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            if i == n // i:
                yakusu.append(i)
            else:
                if i != 1:
                    yakusu.append(i)
                yakusu.append(n // i)
    return yakusu

if __name__ == "__main__":
    ans = 0
    n = int(input())

    ans += calc_yakusu_num(n - 1)
    
    y = calc_yakusu(n)
  

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

Solution (Python):
import math

n = int(input())
ans=2

def go(n,k):
	aux=1
	while(n%k==0):
		n/=k
	if n%k==1:
		return True
	return False

for i in range(2,n):
	if(i*i>n): 
		break
	if n%i==0:
		if(go(n,i)): 
			ans+=1
		if(i!=n/i and go(n,n/i)):
			ans+=1
n-=1

for i in range(2,n):
	if(i*i>n): 
		break
	if n%i==0: 
		ans+=1
		if(i!=n/i):
			ans+=1
if n==1:
	print("1")
else:
	print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
ans=0

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

    
    return divisors

ndivs = make_divisors(n)

n1divs = make_divisors(n-1)
ans += len(n1divs)-1

for i in range(1,len(ndivs)):
    tmp = n
    k = ndivs[i]
    while tmp%k==0:
        tmp //=k
    if tmp%k==1:ans+=1

print(ans)

Solution (Python):

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

    
    return divisors

N = int(input())
ans = len(make_divisors(N-1))-1

for i in make_divisors(N):
  if i == 1:
    continue
    
  Ni = int(N/i)
  
  while Ni % i == 0:
    Ni = int(Ni/i)
    
  if Ni % i == 1:
    ans+=1
    

print(ans)

Solution (Python):

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

  def get_divisors(num):
    divisors = []
    for i in range(1, int(num ** 0.5) + 1):
      if num % i == 0:
        divisors.extend([i, num // i])

    return set(divisors)

  ans = len(get_divisors(n - 1)) - 1

  for k in get_divisors(n):
    if k == 1: continue

    num = n
    while num % k == 0:
      num = num // k

    if num % k == 1:
      ans += 1

  print(ans)

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

a = make_divisors(n)
b = make_divisors(n - 1)

d = list(set(a + b))

ans = 0

for i in list(d):
    if i == 1:
        continue
    x = n
    while x % i == 0:
        x /= i
    
    if x % i == 1:
        ans += 1

print(ans)