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())
if n==2:
  print(1)
  exit()
nn=n-1
ans=set([nn])
for i in range(2,int(nn**0.5)+1):
  if nn%i==0:
    ans.add(i)
    ans.add(nn//i)
l=set()
l.add(n)
for i in range(2,int(n**0.5)+1):
  if n%i==0:
    l.add(i)
    l.add(n//i)
for j in l:
  m=n
  while m%j==0:
    m//=j
  if m%j==1:
    ans.add(j)
print(len(ans))

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
def check(x,m):
    if m % x:
        return m % x == 1
    return check(x,m//x)

def count(n):
    cnt = 1
    f = defaultdict(int)
    for i in range(2,int(math.sqrt(n))+1):
        if n % i == 0 and f[i] == 0:
            cnt += 1
            f[i] = 1
            if f[n//i] == 0:
                cnt += 1
                f[n//i] = 1
    return cnt

def count2(n):
    cnt = 1
    f = defaultdict(int)
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            if check(i,n) and f[i] == 0:
                cnt += 1
                f[i] = 1
            if check(n//i,n) and f[n//i] == 0:
                cnt += 1
                f[n//i] = 1
    return cnt

if n == 2:
    print(1)
    quit()
ans = count(n-1)
ans += count2(n)
print(ans)

Solution (Python):
from copy import deepcopy


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

N0 = int(input())
ans = 0


K_cand = set(make_divisors(N0) + make_divisors(N0-1))

for K in K_cand:
    N = deepcopy(N0)
    if K == 1:  
        continue
    else:
        while N%K == 0:
            N = N // K  
        N = N%K  
        if N == 1:
            ans += 1

print(ans)

Solution (Python):
n = int(input())
if n == 2:
    print(1)
    exit()
ans = []
divisors = []
for i in range(2,int(n**0.5)+1):
    
    if (n-1) % i == 0:
        ans.append(i)
        if i != (n-1) // i:
            ans.append((n-1)//i)
    
    if n % i == 0:
        divisors.append(i)
        if i != n // i:
            divisors.append(n//i)
for item in divisors:
    num = n
    while num%item == 0:
        num = num//item
    if num%item == 1:
        ans.append(item)


print(len(ans)+2)

'''
import math
n = int(input())
ans = []
divisors = []

for i in range(2,math.ceil(n**0.5)+1):
    num = n
    while num >= i:
        if num%i == 0:
            num //= i
        else:
            num -= i
    print(num)
    if num == 1:
        ans.append(i)
    if n % i == 0:
        divisors.append(i+1)
        if i != n // i:
            divisors.append(n//i+1)

print(ans)
print(divisors)
print(len(ans)+len(divisors))


'''

Solution (Python):
import copy
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)
    divisors=sorted(divisors)
    return divisors
n=int(input())

ans=0
ans+=(len(divisors(n-1))-1)
D=divisors(n)
for d in D:
    tmp=copy.deepcopy(n)
    k=tmp/d
    while tmp%k==0:
        tmp=tmp//k
        if tmp==n:
            break
    if tmp%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)
    divisors.sort()
    return divisors
ans=set(make_divisors(n-1))
for k in make_divisors(n)[1:]:
    if k==1:
        continue
    m=n
    while m>=k:
        if m%k==0:
            m=m//k
        else:
            m=m%k
    if m==1:
        ans.add(k)
print(len(ans)-1)

Solution (Python):
n = int(input())
div = []
ans = []

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

for i in div:
    if i == 1:
        continue
    k = n
    while k%i == 0:
        k//=i
    if k%i== 1:
        ans.append(i)
        
n -= 1

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

Solution (Python):
def ord(N,n):
    if n%N!=0:
        return 0
    else:
        return 1+ord(N,n//N)

def partions(M):
    import math
    d=[]
    i=1
    while math.sqrt(M)>=i:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d

N=int(input())
count=0
kouho=partions(N)
for i in range(1,len(kouho)):
    a=kouho[i]
    m=ord(a,N)
    s=N//pow(a,m)
    if s%a==1:
        count+=1

count+=len(partions(N-1))-1
print(count)

Solution (Python):
def div(x):
    D = set()
    for i in range(1, int(x**0.5)+2):
        if x % i == 0:
            D.add(i)
            D.add(x//i)
    return D


n = int(input())
D0 = div(n)
D1 = div(n-1)
D0.remove(1)
D1.remove(1)
cnt = 0
for d in D0:
    n_ = n
    while n_ % d == 0:
        n_ = n_//d
    if n_ % d == 1:
        cnt += 1
cnt += len(D1)
print(cnt)

Solution (Python):
N = int(input())
A = []
c = 0

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

for i in range(2,int((N-1)**0.5)+1):
    if (N - 1) % i == 0:
        A.append(i)
        A.append((N-1)//i)
        
A = list(set(A))
if N == 2:
    print(1)
else:
    for i in A:
        start = N
        while(True):
            if start % i != 0:
                break
            start = start//i
        if start % i == 1:
            c += 1
    print(c+2)

Solution (Python):
import math


def judge(n, k):
    m = n % k
    while m == 0:
        n //= k
        m = n % k
    return m


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


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

    cnt = len(div_list(N-1)) - 1
    cnt += sum(1 for d in div_list(N) if d != 1 and judge(N, d) == 1)

    print(cnt)


main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
def judge(k, M):
    while M%k==0:
        M //= k
    return M%k == 1

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

l = make_divisors(N)+make_divisors(N-1)
ans = 0
for x in l:
    if x == 1:
        continue
    if judge(x, N):
        ans += 1
print(ans)

Solution (Python):
N = int(input())
A = []
c = 0

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

for i in range(2,int((N-1)**0.5)+1):
    if (N - 1) % i == 0:
        A.append(i)

        A.append((N-1)//i)
A = list(set(A))
if N == 2:
    print(1)
else:
    for i in A:
        start = N
        while(True):
            if start % i != 0:
                break
            start = start//i
        if start % i == 1:
            c += 1
    print(c+2)

Solution (Python):
import math
n = int(input())
 
m = n-1
ans1 = 0
for i in range(1, math.ceil(math.sqrt(m))):
  if m%i == 0:
    ans1 += 2
if math.sqrt(m).is_integer():
  ans1 += 1
ans1 -= 1

ans2 = 0
for i in range(2, math.ceil(math.sqrt(n))):
  if n%i == 0:
    k = n
    while k % i == 0:
      k = k // i
    if k % i == 1:
      ans2 += 1
    k = n
    j = n/i
    while k % j == 0:
      k = k // j
    if k % j == 1:
      ans2 += 1
      
if math.sqrt(n).is_integer():
  ans2 += 1
ans2 += 1

print(ans1+ans2)

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

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

l=make_divisors(N)
la=make_divisors(N-1)
l.extend(la)
l=set(l)

c=0
for i in l:
    if i==1 or i==N:
        continue
    if test(N,i):
        c+=1

print(c+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_given = int(input())


list_found_K = []



divisors_N_minus_1 = make_divisors(N_given-1)

for divs in divisors_N_minus_1:
	if divs != 1:
		list_found_K.append(divs)



divisors_N = make_divisors(N_given)
divisors_N.remove(1)


for candidate_K in divisors_N:
	N_wk = N_given
	
	while N_wk % candidate_K == 0:
		N_wk //=candidate_K

	
	if (N_wk-1) % candidate_K == 0:
		list_found_K.append(candidate_K)

print(len(list_found_K))

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

def check(N,K):
    try:
        if N == K:
            return True
        if N % K ==1:
            return True
        if N<K:
            return False
        
        if N % K ==0:
            return check(N//K,K)
        else:
            return False
    except:
        return False

def resolve():
    N = int(input())
    ys= set(make_divisors(N))
    ys2= set([i for i in make_divisors(N-1) if check(N,i)])

    x =set([i for i in ys if check(N,i)])

    print(len(x | ys2))


if __name__ == "__main__":
    resolve()

Solution (Python):
from collections import Counter

N = int(input())
if N == 2:
    print(1)
    exit()
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 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

pf = make_divisors(N)
ans = 0
for i in pf:
    if i == 1:
        continue
    n = N
    while n >= i:
        if n % i == 0:
            n //= i
        else:
            n %= i
    if n == 1:
        ans += 1

pf = prime_factorize(N-1)
p = list(Counter(pf).values())
z = 1
for i in p:
    z *= (i+1)
z -= 1
print(ans+z)

Solution (Python):
n = int(input())
def make(r):
    rr = [1]
    for i, v in r:
        newrr = rr[:]
        for j in rr:
            for k in range(v):
                newrr.append(j * i ** (k + 1))
        rr = newrr
    return rr
        
def factors(n):
    k = n
    i = 2
    r = []
    while i * i <= k:
        v = 0
        while k % i == 0:
            v += 1
            k //= i
        if v > 0:
            r.append((i, v))
        i += 1
    if k > 1:
        r.append((k, 1))
    return make(r)

def isOK(n, k):
    return n % k == 1

r = 0
for i in factors(n):
    n1 = n
    while n1 % i == 0 and i != 1:
        n1 //= i
    if isOK(n1, i):
        r += 1

r += len(factors(n - 1)) - 1

print(r)

Solution (Python):

def prime_decomposition(n):
    i = 2
    prime2exponent = {}  
    while i*i <= n:
        while n % i == 0:
            n //= i
            if i in prime2exponent:
                prime2exponent[i] += 1
            else:
                prime2exponent[i] = 1
        i += 1
    if n > 1:
        if n in prime2exponent:
            prime2exponent[n] += 1
        else:
            prime2exponent[n] = 1
    return prime2exponent


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
p2e = prime_decomposition(N-1)
temp = 1
for v in p2e.values():
    temp *= (v+1)
temp -= 1
ans += temp



divisors = make_divisors(N)

for div in divisors:
    cur = N
    if div == 1:
        continue
    while cur % div == 0:
        cur //= div
        
    if cur % div == 1:
        ans += 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def divisors(n):
    S,T=[],[]
    for i in range(1,int(n**.5)+1):
        if(n%i==0):
            S.append(i)
            T.append(n//i)
    T.reverse()
    return S+T if(S[-1]!=T[0]) else S+T[1:]

def resolve():
    n = int(input())
    res = set(divisors(n-1))
    res.remove(1)
    res.add(n)

    for s in divisors(n):
        if s == n:
            continue
        tmp = s
        t = n // s
        if s < t: 
            continue
        while s % t == 0:
            s //= t
        s %= t
        if s == 1:
            res.add(tmp)

    print(len(res))
resolve()

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

n=int(input())
Ans=[n]
T=make_divisors(n-1) 
for t in T:
    if t!=1:
        Ans.append(t)

S=make_divisors(n) 
for s in S:
    now=n
    if s!=n and s!=1:
        while now%s==0:
            now=now//s
        if now%s==1:
            Ans.append(s)
        
Ans.sort()
ans=0
cnt=0
for a in Ans:
    if cnt!=a:
        cnt=a
        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

ks=make_divisors(N-1)
ks.remove(1)

ans=ks

divs=make_divisors(N)
divs.remove(1)
for i in divs:
    divN=N
    while divN%i==0:
        divN=divN/i
    
    if (divN-1)%i==0:
        ans.append(i)


print(len(ans))

Solution (Python):



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


n = int(input())
ans = len(divisors(n - 1)) - 1
for k in divisors(n)[1:]:
    t = n
    while t % k == 0:
        t //= k
    if t % k == 1:
        ans += 1
print(ans)

Solution (Python):
import math
def prime(x):
  L = []
  last = math.floor(x ** 0.5) 
  for i in range(1, last + 1):
    if x % i == 0:
      L.append(i)
      if x // i != i:
        L.append(x // i)
  return L

N = int(input())

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

L = prime(N - 1)

ans = len(L) - 1

D = prime(N)

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):
def f_division_or_substraction():
    N = int(input())

    def divisor_list(n):
        """n の正の約数のリスト"""
        ret = set()
        for k in range(1, int(n**0.5) + 1):
            if n % k == 0:
                ret.update({k, n // k})
        return sorted(ret)

    ans = (len(divisor_list(N - 1)) - 1)  
    for k in divisor_list(N):
        if k == 1:
            continue
        n = N
        while n % k == 0:
            n //= k
        ans += 1 if n % k == 1 else 0
    return ans

print(f_division_or_substraction())

Solution (Python):

import sys
sys.setrecursionlimit(10**9)

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

ds = set(make_divisors(N)) | set(make_divisors(N-1))

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

ds.remove(1)
cnt = 0
for d in ds:
    
    if check(N,d):
        cnt+=1
print(cnt)

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


cnt=0
for i in range(2,int(math.sqrt(n))+1):
    
    if (n-1)%i==0:
       
        
        cnt=cnt+2
    if (n)%i==0:
        s=n
        while s%i==0:
            s=s//i
        if s%i==1:
            
            cnt=cnt+1
if int(math.sqrt(n-1)) == math.sqrt(n-1):
    
    cnt=cnt-1

if n==2:
    print(1)
else:
    print(cnt+2)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def prime_decomposition(n): 
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

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 = onem()
co = 0

nnn = make_divisors(n)

mp = make_divisors(n-1)


for i in nnn:
    nn = n
    if i == 1:
        continue
    while True:
        if nn == 1:
            co += 1
            break
        elif nn <= 0:
            break
        if nn % i:
            nn = nn % i if nn//i else 0
        else:
            nn //= i
for i in mp:
    if i != 1:
        co += 1
print(co)

Solution (Python):
import math
N = int(input())
s = math.floor(math.sqrt(N))
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)
for i in range(2, s+1):
    temp = N % i
    if temp == 0:
        temp2 = N // i
        temp = temp2 % i
        while temp == 0:
            temp2 = temp2 // i
            temp = temp2 % i
        if temp == 1 and i not in ans:
            ans.append(i)
    elif temp == 1 and i not in ans:
        ans.append(i)
print(len(ans))

Solution (Python):
def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return (_N-1)%p == 0

def calc_divisors(n):
    m = int(n**0.5)
    left = []
    right = []
    for i in range(1, m+1):
        if n%i == 0:
            left.append(i)
            right.append(n//i)
    if left[-1] == right[-1]:
        right.pop()
    return left + right[::-1]

N = int(input())
P0 = calc_divisors(N)[1:] 
P1 = calc_divisors(N-1)[1:] 
ans = len(P1)
for p in P0:
  ans += check(p)

print(ans)

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

N = int(input())

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

s = set([N - 1, N])


for i in range(2, int(sqrt(N)) + 1):
    tmp = N
    if (tmp - 1) % i == 0:
        s.add(i)
        s.add((tmp - 1) // i)
    elif tmp % i == 0:
        while tmp % i == 0:
            tmp //= i

        if tmp % i == 1:
            s.add(i)

        tmp = N
        while tmp % (N // i) == 0:
            tmp //= (N // i)

        if tmp % (N // i) == 1:
            s.add(N // i)


print(len(s))

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

divisor = set([N, N - 1])
x = N
for i in range(2, int(x ** 0.5) + 1):
    z = x
    while z % i == 0:
        z //= i
    if z % i == 1:
        divisor.add(i)
        
    if i == x // i:
        continue
        
    z = x
    while z % (x // i) == 0:
        z //= (x // i)
    if z % (x // i) == 1:
        divisor.add((x // i))
        
x = N - 1
for i in range(2, int(x ** 0.5) + 1):
    if x % i == 0:
        divisor.add(i)
        divisor.add(x // i)

print(len(divisor) if N > 2 else 1)

Solution (Python):
n=int(input())
def prime_factorize(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    f=3
    while f**2<=n:
        if n%f==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return(a)

import collections
A=collections.Counter(prime_factorize(n-1))
ans=1
cnt=0
for a,b in A.items():
    ans*=(b+1)

import math
li=[]
for i in range(2,math.floor(n**0.5)+1):
    if n%i==0:
        li.append(i)
        if i!=n//i:
            li.append(n//i)
li.append(n)
for i in li:
    x = n
    while x % i == 0:
        x //= i
    if x % i == 1:
        cnt += 1
print(ans - 1 + cnt)

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

def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return (_N-1)%p == 0

n = int(N**0.5) + 1
P0 = set([N])
P1 = set([N-1])
for i in range(2, n+1):
  if (N-1)%i == 0:
    P1.add(i)
    P1.add((N-1)//i)
  if N%i == 0:
    P0.add(i)
    P0.add(N//i)

P0.discard(1)
P1.discard(1)
ans = len(P1)
for p in P0:
  ans += check(p)

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())
divs1=divisors(n)
divs2=divisors(n-1)
cnt=len(divs2)-1
for val in divs1:
  if val==1:
    continue
  tmp=n
  while tmp%val==0:
    tmp=tmp//val
  if tmp%val==1:
    cnt+=1
print(cnt)

Solution (Python):
import numpy as np
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
            if N//i != i:
                ans.append(N//i)
    return ans

def check(K,N):
    while N >= K:
        if N%K == 0:
            N //= K
        else:
            N %= K
    if N%K == 1:
        return True
    else:
        return False

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

for K in factor(N)[1:]:
    if check(K,N):
        ans += 1

print(ans)

Solution (Python):
n=int(input())
c=0
for i in range(2,int(n**0.5)+1):
    d=n
    while d%i==0:
        d//=i
    if n%i==0 and (d-1)%i==0:
        c+=1
for i in range(2,int((n-1)**0.5)+1):
    if (n-1)%i==0:
        if n-1==i**2:
            c+=1
        else:
            c+=2
if n<3:
    print(1)
else:
    print(c+2)

Solution (Python):
import math
import random
import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline
MAX_INT = 2**62-1


def main():
    def check(num, k):
        mod = num % k
        if mod == 1:
            return True
        if mod:
            return False
        exp = k
        while num % exp == 0:
            num //= exp
            exp *= exp
        return check(num, k)

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

    print(ans - (round((N-1)**0.5)**2 == N-1))


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
cnt = 0
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.pop(0)
    return divisors
N1_yakusu = make_divisors(N-1)
N_yakusu = make_divisors(N)
cnt += len(N1_yakusu)
for K in N_yakusu:
    new_N = N
    while(new_N%K==0):
        new_N = new_N//K
    if(new_N%K == 1):
        cnt += 1
print(cnt)

Solution (Python):










import math
N=int(input())
l=[]
ser=[]


pf={}
ans1=1
m=N-1
buf=0
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1

keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])

ans1=1
for i in range(len(keys)):
    ans1=ans1*(l[i][1]+1)
ans1=ans1-1



ans2=0
for i in range(int(math.sqrt(N))):
    a=i+1
    b=N/a
    
    if b.is_integer()==True:
        if a!=b:
            ser.append(a)
            ser.append(int(b))
        else:
            ser.append(a)

for i in range(len(ser)):
    buf=N
    if ser[i]!=1:
        while (buf/ser[i]).is_integer()==True:
            
            buf=buf//ser[i]
        if buf%ser[i]==1:
            ans2=ans2+1

print(ans1+ans2)

Solution (Python):
N = int(input())
ans=0
x = N-1
for i in range(2,int(x**(1/2))+1):
  if x%i==0:
    ans+=2
  
if int(x**(1/2))**2==x:
  ans-=1


for i in range(2,int(N**(1/2))+1):
  a = N
  if a%i==0:
    while a%i==0:
      a//=i
    if a%i==1:
      ans+=1
      
    b = N//i
    if b==i:
      continue
    a = N
    while a%b==0:
      a//=b
    if a%i==1:
      ans+=1
    
print(ans+2)

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())
count = 0
nlis = make_divisors(n)
n1lis = make_divisors(n-1)
for i in nlis:
  if i == 1:
    continue
  num = n
  while num % i == 0:
    num //= i
  num %= i
  if num == 1:
    count += 1
    
count += len(n1lis) - 1
print(count)

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

res = 0

if N == 2:
    res += 1
else:
    res += 2

for i in range(2, int((N - 1)**0.5 + 0.5) + 1):
    if (N - 1) % i != 0:
        continue
    if (N - 1) % i == 0:
        res += 1
    if i ** 2 == N - 1:
        continue
    if (N - 1) % ((N - 1) // i) == 0:
        res += 1

for i in range(2, int(N**0.5 + 0.5) + 1):
    if N % i != 0:
        continue
    tmp = N
    while tmp % i == 0:
        tmp //= i
    if (tmp - 1) % i == 0:
        res += 1
    if i ** 2 == N:
        continue
    tmp = N
    while tmp % (N // i) == 0:
        tmp //= (N // i)
    if (tmp - 1) % (N // i) == 0:
        res += 1

print(res)

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

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

cnt = 0
divisors = make_divisors(N)
divisors_n1 = make_divisors(N-1)
divisors.extend(divisors_n1)
for K in divisors:
    tmp_N = N_tmp
    if K <= 1: continue
    while tmp_N % K == 0:
        tmp_N = tmp_N // K
    tmp_N = tmp_N % K
    if tmp_N == 1:
        cnt += 1

print(cnt)

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

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

a = 0

for i in D(N):
  M = N
  if i == 1:
    continue
  else:
    while M % i == 0:
      M = M//i
    if M % i == 1:
      a += 1

print(len(D(N-1))-1+a)

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

k = 2
count = 1
while k * k <= n:
    m = n
    while m % k == 0:
        m = m / k
    if m % k == 1:
        count += 1
    k += 1

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

if n == 2:
    print(1)
else:
    print(count)

Solution (Python):
import math
import collections

N = int(input())
res = 1


n = 10 ** 6 + 5000
fl = [1] * n
fl[0] = 0
fl[1] = 0
lprime = []
for i in range(n):
    if fl[i] == 1:
        lprime.append(i)
        ti = i * 2
        while ti < n:
            fl[ti] = 0
            ti += i


def prime_factorize(n):
    global lprime
    a = []
    for p in lprime:
        if p * p > n:
            break
        while n % p == 0:
            a.append(p)
            n //= p
    if n != 1:
        a.append(n)
    return a


def yakusuu(N):
    t = math.floor(math.sqrt(N))
    res = []
    for i in range(2, t + 1):
        if N % i == 0:
            res.append(i)
    return res


tres = prime_factorize(N - 1)
ctres = collections.Counter(tres)
for s in ctres.values():
    res *= s + 1
tres = yakusuu(N)
for c in tres:
    t = N
    while t % c == 0:
        t //= c
    if t == 1 or (t - 1) % c == 0:
        res += 1
print(res)

Solution (Python):

import math
n = int(input())
if n == 2:
    print(1)
    exit()

def divisor(n):
    res = [n]
    for i in range(2,1+math.floor(math.sqrt(n))):
        if n % i == 0:
            res.append(i)
            if i != n//i:
                res.append(n//i)
    return res
ans = len(divisor(n-1))

res = []
lis = divisor(n)
for i in lis:
    
    m = n
    while m % i == 0:
        m = m // i 
    if m % i == 1:
        ans += 1
        res.append(i)
        
print(ans)

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

n = int(input())

ans = set()


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

a = make_divisors(n)

for i in a:
    if i == 1:
        continue
    n_ = n
    while n_ % i == 0:
        n_ //= i
    if (n_ - 1) % i == 0:
        ans.add(i)

d = make_divisors(n - 1)

for i in d:
    if i != 1:
        ans.add(i)

ans.add(n)

print(len(ans))

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

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

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