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
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())



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


div_n = divisor(N)
div_n1 = divisor(N - 1)

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

    if n % d == 1 or n == 1:
        ans.append(d)

for d in div_n1:
    if d == 1:
        continue
    if N % d == 0:
        nd = N // d
        if nd % d == 1 or nd % d == 0:
            ans.append(d)
    else:
        ans.append(d)


ans = list(set(ans))

print(len(ans))

Solution (Python):


def check_divide(n):
    max_v = int(n ** (1/2))
    divide_nums = []
    for i in range(1,max_v + 1):
        if n % i == 0:
            divide_nums.append(i)
    return divide_nums

def check_divide2(n):
    divide_nums = []
    for K in range(2,n+1):
        tmp = n
        while True:
            if tmp % K ==0:
                tmp = tmp // K
            else:break
        if tmp % K == 1:
            divide_nums.append(K)
    return divide_nums

if __name__ == '__main__':
    N = int(input())
    tmp1 = check_divide(N-1)
    if tmp1[-1] ** 2 == N-1:
        tmp1 = len(tmp1) * 2 - 2
    else:
        tmp1 = len(tmp1) * 2 - 1

    candidates = check_divide(N)[1:]

    tmp2 = [N]
    for val in candidates:
        N_ = N
        while True:
            if N_ % val == 0:
                N_ = N_ / val
            else:break
        if N_ % val == 1:
            tmp2.append(val)
    tmp2 = len(tmp2)
    print(tmp1 + tmp2)

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

def divisor(n):
    if n==1:return []
    ret = [n]
    for i in range(2,n+1):
        if i*i==n:
            ret.append(i)
        elif i*i > n:
            break
        elif n%i==0:
            ret.append(i)
            ret.append(n//i)
    ret.sort()
    return ret

ans = len(divisor(N-1))

for k in divisor(N):
    M = N
    while M%k==0:
        M//=k
    if M%k==1:
        ans += 1
print(ans)

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

n = int(input())
ways = len(find_divisor(n-1)) - 1
Div = find_divisor(n)
for i in range(1, len(Div)):
    quo = n
    while quo % Div[i] == 0:
        quo = quo // Div[i]
    if quo % Div[i] == 1:
        ways += 1
print(ways)

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 main():
    n = int(input())
    
    ans = len(make_divisors(n - 1)) - 1
    
    l = make_divisors(n)[1:]
    for i in l:
        num = n
        while num % i == 0:
            num //= i
        if num % i == 1:
            ans += 1
    print(ans)


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

a = make_divisors(n-1)
ans = len(a)-1
b = make_divisors(n)[1:]
c=[]
for num in b:
    d = n
    while(d%num==0):
        d = d / num
    if(d%num==1):
        c.append(num)
ans += len(c)
print(ans)

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

n=int(input())
ans=0
t=d(n)
for i in t:
    if i==1:
        continue
    tn=n
    while tn>=i:
        if tn%i==0:
            tn//=i
        else:
            tn%=i
    if tn==1:
        ans+=1
ans+=len(d(n-1))-1
print(ans)

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

def make_divisors(n):
    divisors = []
    hei = 0
    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

m_n = make_divisors(N)
m_n.remove(1)
ans = len(make_divisors(N - 1)) - 1

for i in range(len(m_n)):
  x = N
  y = m_n[i]
  while x % y == 0:
    x = x // y
  if x % y == 1:
    ans += 1
    
print(ans)

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

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


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+100):
        if i > temp / i:
            break
        if i * i == temp:
            arr.append(i)
            break
        if temp % i == 0:
            arr.append(i)
            arr.append(temp // i)
    arr.append(n)
    return arr

N_div = factorization(N)
N_1_div = factorization(N-1)


ans = len(N_1_div)
for K in N_div:
    temp = N
    while temp % K == 0:
        temp = temp // K
    if temp % K == 1:
        ans += 1
print(ans)

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

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

for d in divisors(n)[1:]:
  tmp = n
  while tmp%d == 0:
    tmp = tmp//d
  if tmp%d == 1:
    ans += 1
  
print(ans)

Solution (Python):
n = int(input())
p = []
q = []
r = []
for i in range(2,(int(n**0.5)+1)):
    N = n
    if N%i == 0:
        p.append(i)
for i in range(2,(int(n**0.5)+1)):
    N = n - 1
    if N%i == 0:
        r.append(i)
        if i != N//i:
            r.append(N//i)
for i in range(len(p)):
    N = n
    while N % p[i] == 0:
        N = N / p[i]
    if N % p[i] == 1:
        q.append(p[i])
for i in range(len(r)):
    if n % r[i] == 1:
        q.append(r[i])
if n == 2:
    print(1)
else:
    print(len(q)+2)

Solution (Python):
n = int(input())
n2 = int(n ** 0.5) + 1
n3 = n * 1
ans = 0

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

    
    return divisors

a = set(md(n-1))

for i in range(2,n2+1):
    n3 = n * 1
    while True:
        if n3 % i == 0:
            n3 //= i
        else:
            n3 %= i
            if n3 == 1:
                a.add(i)
            break
    
if n != 2:
    print(len(a))
else:
    print(1)

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


def divthensub(v, div):
    while v % div == 0:
        v //= div
    if v % div == 1:
        return True
    else:
        return False


n = int(input())
if n == 2:
    print(1)
else:
    print(len([i for i in gen_divs(n) if divthensub(n, i)]) + len(gen_divs(n - 1)) + 2)

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

n=int(input())
ans1=divisor(n-1)
ans1.remove(1)
as0=divisor(n)
ans0=[]
for x in as0:
  if x!=1:
    m=n
    while m>=x and m%x==0:
      m=m//x
    if m%x==1:
      ans0.append(x)

ans=set(ans0)|set(ans1)
ans=list(ans)




print(len(ans))
"""
ans.sort()
print(ans)
for x in ans:
  m=n
  while m%x==0:
    m=m//x
  print(x,m%x)
"""

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 = 0
divisors = make_divisors(N)[1:]
ans += len(make_divisors(N-1))-1

for divisor in divisors:
        divided_N = N
        while 1:
            if divided_N%divisor!=0:
                break
            else:
                divided_N //=divisor
        if divided_N % divisor == 1:
            ans += 1
print(ans)

Solution (Python):
import math

def prime(x):
  p = {}
  last = math.floor(x ** 0.5)
  if x % 2 == 0:
    cnt = 1
    x //= 2
    while x & 1 == 0:
      x //= 2
      cnt += 1
    p[2] = cnt
  for i in range(3, last + 1, 2):
    if x % i == 0:
      x //= i
      cnt = 1
      while x % i == 0:
        cnt += 1
        x //= i
      p[i] = cnt
  if x != 1:
    p[x] = 1
  return p

N = int(input())

P = prime(N - 1)

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

ans = 1
for i in P.keys():
  ans *= P[i] + 1
ans -= 1

P = prime(N)
D = [1]
for i in P.keys():
  L = len(D)
  n = i
  for j in range(P[i]):
    for k in range(L):
      D.append(D[k] * n)
    n *= i


for i in D:
  if i == 1: continue
  t = N
  while (t / i == t // i):
    t //= i

  t -= 1
  if t / i == t // i:
    ans += 1

print(ans)

Solution (Python):



import sys
input = sys.stdin.readline
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

def main():
    N=int(input())
    ret=0
    if N==2:
        ret=1
    else:
        div=make_divisors(N)
        div=div+make_divisors(N-1)
        div.append(N)
        div.append(N-1)
        for k in div:
            n=N
            while n%k==0:
                n=n//k
            ret += n%k==1
        if N==2:
            ret = 1
    print(ret)

if __name__ == '__main__':
    main()

Solution (Python):

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


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


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

Solution (Python):
from math import sqrt, log


def factor(number):
    i = 2
    s = set()
    while i * i <= number:
        if number % i == 0:
            if i != 2:
                s.add(i)
            if (number // i) != 2:
                s.add(number//i)
        i += 1
    return s


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


n = int(input())
if n == 2:
    print(1)
    exit()
if n == 3:
    print(2)
    exit()
s = set()
s.add(2)
s.add(n-1)
s.add(n)
s = s.union(factor(n-1))
s = s.union(newFactor(n))
print(len(s))

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 make_divisors2(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)

    
    return divisors

n=int(input())
l = make_divisors(n-1)
ans = len(l)

l2 = make_divisors2(n)
for i in l2[1:]:
    n1 = n
    while n1%i == 0:
        n1 = n1//i
    if n1%i == 1:
        ans += 1
print(ans)

Solution (Python):
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()
from math import sqrt


def factor(n):
    """
    nの約数を個数と共にリストにして返す。
    ただしあとの都合上１は除外する。
    """

    if n == 1:
        return 0, []
    if n == 2:
        return 1, [2]
    if n == 3:
        return 1, [3]

    d = int(sqrt(n))
    num = 1
    factor_pre = []
    factor_post = [n]
    for i in range(2, d):
        if n % i == 0:
            factor_pre.append(i)
            factor_post.append(n // i)
            num += 2
    if d * d == n:
        factor_pre.append(d)
        num += 1
    elif n % d == 0:
        factor_pre.append(d)
        factor_post.append(n // d)
        num += 2
    factor_post.reverse()
    return num, factor_pre + factor_post


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

    """
    題を満たすKは、
        N = K^e * n、(n, K) = 1
    として
        n = K * m + 1 (m ¥in ¥mathbb{N})
    とかければ良い。

    ２つ目の式からnとKが互いに素なのは明らかなので、問題文は
        N = K^e * (K * m + 1) (m ¥in ¥mathbb{N})
    なるKを求めることに同値。

    なのでまずはNの約数を全列挙して、あとはNをそれで割った商がKで割って1余るか確かめれば良い。
    """

    _, fact = factor(N)
    ans, ans_list = factor(N - 1)
    

    
    for K in fact:
        n = N
        while n % K == 0:
            n //= K
        if n % K == 1:
            ans += 1
            ans_list.append(K)
            
    
    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
 
N = int(input())
 
 
def divisor(N):
    x = np.arange(1, int(N**(1/2))+1, dtype=np.int64)
    div = set(x[N % x == 0])
    return div | set(N // x for x in div)
 
 
cand = divisor(N) | divisor(N - 1)
 
 
def test(N, K):
    if K == 1:
        return False
    while N % K == 0:
        N //= K
    return N % K == 1
 
 
answer = sum(test(N, d) for d in cand)
print(answer)

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

    def trial_division(n):
        divs = set()
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                if i != 1:
                    divs.add(i)
                if i != n//i:
                    divs.add(n//i)
        return divs

    ans |= (trial_division(N))
    ans |= (trial_division(N-1))
    answer = 0
    for k in ans:
        cur = N
        while cur % k == 0 and cur != 1:
            cur //= k
        if cur == 1 or cur % k == 1:
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):

N = int(input())

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

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


divisors = make_divisors(N)
def dfs(x,N):
    while N % x == 0:
        N //= x

    N %= x

    return N == 1

counta = 0
for i in range(1,len(divisors)):
    if dfs(divisors[i],N):
        counta += 1

ans += counta

print(ans)

Solution (Python):
import math
N = int(input())
if N == 2:
    print(1)
else:
    ans = [N-1,N]

    
    for i in range(2,int(math.sqrt(N-1)+1)):
        if (N-1) % i == 0:
            ans.append(i)
            if i != (N-1)//i:
                ans.append((N-1)//i)

    
    for j in range(2,int(math.sqrt(N))+1):
        if N % j == 0:
            n1 = N
            n2 = N
            while n1 % j == 0:
                n1 = n1/j
            if n1 % j == 1:
                ans.append(j)
            if j != N//j:
                while n2 % N//j == 0:
                    n2 = n2*j//N
                if n2 % j == 1:
                    ans.append(N//j)
        
    print(len(ans))

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from copy import deepcopy

def sieve(n):
    prime = []
    limit = n ** 0.5
    data = [i + 1 for i in range(1,n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e%p != 0]


def main():
    primes = sieve(1000005)
    n = int(input())
    div = set()
    for i in range(2,int(n ** 0.5) + 1):
        if n%i == 0:
            div.add(i)
            div.add(n//i)
    
    ans = 0
    for d in div:
        k = deepcopy(n)
        while k%d == 0:
            k //= d
        if k%d == 1:
            ans += 1
    
    m2 = n - 1
    cnt = 1
    for p in primes:
        tmp = 1
        while  m2%p == 0:
            m2 //= p
            tmp += 1
        cnt *= tmp           
    
    if m2 != 1:
        cnt *= 2
    
    print(ans + cnt)

if __name__ =='__main__':
    main()

Solution (Python):
from math import sqrt
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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


def prime_enumeration(n):
    div = []
    for i in range(1, int(sqrt(n))+1):
        if n % i == 0:
            if i != 1:
                div.append(i)
            if n // i != i:
                div.append(n // i)

    
    return div


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

    div_n = prime_enumeration(N)
    div_n1 = prime_enumeration(N-1)
    
    

    ans = 0
    for d in div_n:
        if is_ok(N, d):
            ans += 1
    
    for d in div_n1:
        if is_ok(N, d):
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

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

ans = []



i = 1
while i * i <= (N - 1):
    if (N - 1) % i == 0:
        ans.append(i)
        if i * i != (N - 1):
            ans.append((N - 1) // i)
    i += 1


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


for d in divisor:
    if d == 1:
        continue
    tmp_N = N
    while tmp_N % d == 0:
        tmp_N = tmp_N // d
    if tmp_N % d == 1:
        ans.append(d)

print(len(set(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
ans = make_divisors(N-1)
del ans[0]
cand = make_divisors(N)
del cand[0]
for one in cand:
    n = N
    while True:
        if n%one==0:
            n = n//one
        else:
            if n%one==1:
                ans.append(one)
            break

print(len(ans))

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

def ch(k):
  global C
  if k < 2:
    return
  
  n = N
  while (n >= k) and (n%k == 0):
    n = n // k
  if ( n%k == 1 ):
    C += 1
  return


ch(N)
ch(N-1)

nn = int( N**0.5 )
for k in range(2,nn+1):
  z = N%k
  if z <= 1:
    ch(k)
    k2 = N//k
    if k!=k2:
      ch(k2)

print(C)

Solution (Python):
import math
N = int(input())
M = int(math.sqrt(N))
M2 = int(math.sqrt(N-1))
y = []
for i in range(1,M2+1):
    if (N-1)%i == 0:
        m = (N-1)//i
        if not m == 1:
            y.append(m)
        if i == 1 or i == m:
            continue
        else:
            y.append(i)
count = len(y)

y = []
for i in range(1,M+1):
    if N%i == 0:
        m = N//i
        y.append(m)
        if i == 1 or i == m:
            continue
        else:
            y.append(i)

for i in y:
    NN = N
    while NN%i == 0:
        NN /= i
    
    if int(NN) % i == 1:
        count += 1
        

print(count)

Solution (Python):
import math


N = int(input())

nn = int(math.sqrt(N))


ans = 1
for x in range(2,nn+1):

    if N % x == 1:
        ans += 1
        continue
    
    if N % x > 1:
        continue

    tmp = N
    while tmp > x:
        tmp = tmp / x
        if tmp % x == 1 :
            ans += 1
            break
        elif tmp % x > 1 :
            break
        elif tmp == x:
            ans += 1
            break

x = 1
tmp = N - 1
while tmp / x  > nn:
    if tmp % x == 0:
        ans += 1
    x += 1

print(ans)

Solution (Python):
from math import sqrt
N = int(input())
ans = 0
divisors = []

for i in range(2, int(sqrt(N))+1):
    if N%i==0:
        divisors.append(i)
        divisors.append(N//i)

for d in set(divisors):
    i = 1
    while N%(d**i)==0:
        i += 1
    n = N//(d**(i-1))
    if n%d==1:
        ans+=1

for i in range(2, int(sqrt(N))+1):
    if (N-1)%i==0:
        if i**2!=N-1:
            ans += 2
        else:
            ans += 1
if N==2:
    print(1)
else:
    print(ans+2)

Solution (Python):
import math
import copy

n = int(input())
m = int(math.sqrt(n)+.1)+1

def f(x):
    a = copy.copy(n)
    while a%x == 0:
        a /= x
    return a%x == 1

ans = {n}
if n > 2:
    ans.add(n-1)

for k in range(2,m):
    if (n-1)%k == 0:
        ans.add(k)
        ans.add((n-1)//k)
    elif f(k):
        ans.add(k)
print(len(ans))

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

def main():
    N=int(input())
    ans=len(make_devisor(N-1))-1
    d=make_devisor(N)
    for i in d:
        if i==1:
            continue
        tmp=0
        n=N
        while tmp==0:
            n//=i
            tmp=n%i
        if tmp==1:
            ans+=1
    print(ans)

main()

Solution (Python):

'''
20
'''

N = int(input())


class Prime(object):
    @staticmethod
    def is_prime(n: int) -> bool:
        """
        素数判定
        >>> p = Prime()
        >>> p.is_prime(2)
        True
        >>> p.is_prime(43)
        True
        >>> p.is_prime(4)
        False
        """

        if n == 1:
            return False
        if n == 2:
            return True

        for i in range(2, n):
            if n % i == 0:
                return False
            if i * i > n:
                return True

    @staticmethod
    def divisor(n: int, sort: bool = False) -> list:
        """
        約数列挙
        >>> p = Prime()
        >>> p.divisor(6)
        [1, 2, 3, 6]
        """
        res = []
        if n == 1:
            return [1]

        for i in range(1, n):
            if n % i == 0:
                res.append(i)
                if i != n / i:
                    res.append(int(n / i))
            if (i+1) * (i+1) > n:
                if sort:
                    res.sort()
                return res



temp1 = Prime.divisor(N - 1, sort=False)

cnt1 = len(temp1) - 1


temp2 = Prime.divisor(N, sort=True)[1:]

cnt2 = 0

for temp in temp2:
    a = N
    while a % temp == 0:
        a = a / temp
    if a % temp == 1:
        cnt2 += 1

print(cnt1 + cnt2)

Solution (Python):
N = int(input())
def divisor(x):
  ret = set()
  for i in range(1,int(x**0.5+1)):
    if x%i == 0:
      ret.add(i)
      ret.add(x//i)
  return ret

ans = 0
for k in divisor(N):
  if k == 1:
    continue
  tmp = N
  while(tmp%k == 0):
    tmp //= k
  if tmp%k == 1:
    ans += 1
ans += len(divisor(N-1))-1
print(ans)

Solution (Python):
import math
def solve():
    n = int(input())

    ans = 0
    for x in calc_divisors(n):
        if x == 1:
            continue
        tmp = n
        while tmp % x == 0:
            tmp /= x
        tmp %= x
        if tmp == 1:
            ans += 1
    
    ans += len(calc_divisors(n-1)) - 1

    print(ans)

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

if __name__ == '__main__':
    solve()

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

ans = make_divisors(n-1) 
y = make_divisors(n) 

for i in y:
    z = n
    while z >= i and z%i == 0: 
        z = int(z / i)
        if z % i == 1: 
            ans.append(i)
            break

set(ans)

print(len(ans))

Solution (Python):

"""
nとn-1の約数の個数が答え
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())

"""約数の個数"""


def factrize(n):
    b = 2
    fct = []
    while b*b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b+1
    if n > 1:
        fct.append(n)
    if len(fct) == 1: 
        return 2 
    
    divisor = dict()
    for i in fct:
        if not i in divisor:
            divisor[i] = 1
        else:
            divisor[i] += 1
    ans = 1
    for i in divisor.values():
        ans *= (i+1)
    return ans
def factrize_all(n):
    b = 2
    fct = []
    while b*b <= n:
        if n%b == 0:
            fct.append(b)
        b += 1
    return fct + [n]

ans = 0
res2 = []
for i in factrize_all(n):
    res = n
    while True:
        if res == 0:
            break
        if res%i != 0:
            res2.append([i,res])
            break
        res = res//i

for i,j in res2:
    if j%i == 1:
        ans += 1

print(ans+factrize(n-1)-1)

Solution (Python):
from math import sqrt, ceil

def factors_set(number):
    factors = set()
    for i in range(1, ceil(sqrt(number))+1):
        if number % i == 0:
            factors.add(i)
            factors.add(number // i)
    return factors

N = int(input())

Ks = factors_set(N-1) | factors_set(N)
Ks.remove(1)

ans = 0
for K in Ks:
    N_tmp = N
    while N_tmp % K == 0:
        N_tmp //= K
    if N_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)
    divisors.sort()
    
    divisors.remove(1)
    return divisors

N = int(input())
ans = len(make_divisors(N-1))
N_divisors = make_divisors(N)
for divisor in N_divisors:
    x = N
    while x % divisor == 0:
        x /= divisor
    if x % divisor == 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

def all_pattern(l):
    global n
    ans=0
    for ds in make_divisors(l)[1:]:
        k=n
        while k%ds==0:
            k//=ds
        ans+=(k%ds==1)
    return ans

n=int(input())
print(all_pattern(n)+all_pattern(n-1))

Solution (Python):
def divisors(N):
  result = {1, N}
  for i in range(2, int(N**0.5)+2):
    if N % i == 0:
      result.add(i)
      result.add(N//i)
  return result

N = int(input().strip())
if N == 2: print(1)
else:
  ans = len(divisors(N-1))-1
  for k in divisors(N):
    if k == 1: continue
    n = N
    while n%k == 0: n = n//k
    if n%k == 1: ans += 1
  print(ans)

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

divisors = set()
for i in range(1, int(-(-n**.5//1))+1):
    if n % i == 0:
        divisors |= {i, n//i}

ans = set()
for div in divisors:
    x = n
    if div == 1:
        continue
    while x % div == 0:
        x = x//div
    if x % div == 1:
        ans |= {div}


n -= 1
for i in range(1, int(-(-n**.5//1))+1):
    if n % i == 0:
        ans |= {i, n//i}

ans ^= {1}
print(len(ans))

Solution (Python):


def calcDivisors(x):
    divs = []
    for i in range(1, int(x ** 0.5)+1):
        if x % i == 0:
            divs.append(i)
            if i * i != x:
                divs.append(x // i)
    return divs

n = int(input())
c = 0


c += len(calcDivisors(n - 1)) - 1


divs = calcDivisors(n)
divs.sort()
for k in divs[1:]:
    r = n
    while r % k == 0:
        r //= k
    if r % k == 1:
        c += 1

print(c)

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

def all_pattern(l):
    global n
    ans=0
    for ds in make_divisors(l)[1:]:
        k=n
        while k%ds==0:
            k//=ds
        ans+=(k%ds==1 or k-k%ds==1)
    return ans

n=int(input())
print(all_pattern(n)+all_pattern(n-1))

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

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

ans = len(divisor(n-1))-1
lst = divisor(n)
for i in lst:
    tmp = n
    if i == 1: continue
    while tmp%i == 0: tmp //= i
    if tmp%i == 1: ans += 1

print(ans)

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

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

ans = len(divisor(n-1))-1
lst2 = divisor(n)
for i in lst2:
    tmp = n
    if i == 1: continue
    while tmp%i == 0: tmp //= i
    if tmp%i == 1: ans += 1

print(ans)

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

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

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

divs = make_divs(N-1)
ans += len(divs)-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())
x = make_divisors(N-1)[1:]
ans = len(x)
d = make_divisors(N)[1:]
for c in d:
  m = N
  while m%c==0:
    m //= c
  if m%c==1:
    ans += 1
print(ans)

Solution (Python):
n=int(input())
ans=0
s=dict()
s[n]=0
for i in range(1,int(n**0.5)+1):
  if n%(i+1)==0:
    if i+1 not in s:
      s[i+1]=0
    if n//(i+1) not in s:
      s[n//(i+1)]=0
s=list(s.items())
for i,j in s:
  if i==1:
    continue
  l=n
  while l%i==0:
    l//=i
  if l%i==1:
    ans+=1
d=dict()
k=n-1
for i in range(1,int((n-1)**0.5)+1):
  t=0
  while k%(i+1)==0:
    k//=(i+1)
    t+=1
  if t>0:
    if i+1 not in d:
      d[i+1]=t
    else:
      d[i+1]+=t
if k>1:
  if k not in d:
    d[k]=1
  else:
    d[k]+=1
d=list(d.items())
m=1
for p,root in d:
  m*=(root+1)
print(ans+m-1)

Solution (Python):
import math

N = int(input())


KMAX = math.floor(math.sqrt(N)) + 1

Kn = [N]  
Kn1 = [N-1]  


for K in range(2,KMAX):
    
    if N % K == 0:
        Kn.append(K)
        tmp = N//K
        if tmp == K:
            continue
        Kn.append(N//K)
        
Knn = []


for K in Kn:
    tN = N
    while tN % K == 0:
        tN = tN // K  
    
    if (tN - 1) % K == 0:
        Knn.append(K)
        

for K in range(2,KMAX):

    if (N - 1) % K == 0:
        Kn1.append(K)
        tmp = (N-1) // K
        if tmp == K:
            continue
        Kn1.append(tmp)

Knn.extend(Kn1)
if 1 in Knn:
    Knn.remove(1)
print(len(Knn))