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



Sample input:
6


Sample output:
3

Submission status: Accepted

Solution code:
MAX_PRIME = 10 ** 6
is_prime = [1] * MAX_PRIME
primes = []
is_prime[0] = 0
is_prime[1] = 0
for i in range(MAX_PRIME):
    if is_prime[i]:
        primes.append(i)
        for j in range(2, ((MAX_PRIME-1)//i) + 1):
            is_prime[i*j] = 0

def factorization(n):
    factor = {}
    for p in primes:
        if p ** 2 > n:
            break
        while n % p == 0:
            n //= p
            if p not in factor:
                factor[p] = 1
            else:
                factor[p] += 1
    if n > 1:
        factor[n] = 1
    return factor

n = int(input())
ans = 1
for _, c in factorization(n-1).items():
    ans *= c + 1

f = factorization(n)
k = list(f.keys())
def dfs(num, i):
    ret = 0
    if i == len(k):
        if num != 1:
            x = n
            while x % num == 0:
                x //= num
            if x % num == 1:
                ret += 1
        return ret
    else:
        p = k[i]
        for j in range(f[p]+1):
            ret += dfs(num * p ** j, i+1)
        return ret

print(dfs(1, 0) + ans - 1)

Submission status: Accepted

Solution code:
import math
 
N = int(input())
 
cnt = 0
 
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)
 
    # divisors.sort()
    return divisors
res1 = sorted(make_divisors(N))
res1 = res1[1:math.ceil(len(res1)/2)]
 
for num in res1:
  kensa = N
  while True:
    if kensa % num == 0:
      kensa = kensa // num
      continue
    break
  if kensa % num == 1:
    cnt += 1
 
res2 = sorted(make_divisors(N-1))
cnt += len(res2[1:])+1
 
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

def getDivisors(x):
    anss = set()
    for d in range(1, int(x**0.5)+1):
        if x%d == 0:
            anss.add(d)
            anss.add(x//d)
    return anss

divs = getDivisors(N) | getDivisors(N-1)
#print('divs:', divs)

ans = 0
for k in divs:
    if k == 1: continue
    x = N
    while x >= k:
        if x%k == 0:
            x //= k
        else:
            x %= k
    if x == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
def make_divisors(n):
    divisors = [n]
    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()
    return divisors

if N == 2:
    print(1)
else:   
    cnt = len(make_divisors(N - 1))
    for i in make_divisors(N):
        tmp = N
        while tmp % i == 0:
            tmp //= i
        if tmp % i == 1:
            cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
def primelist(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def factorization(n):
    plist = primelist(int(n**0.5))
    factor = []
    for p in plist:
        k = 0
        while n%p==0:
            k+=1
            n//=p
        if k>0:
            factor.append((p,k))
        if n==1:
            break
    if n!=1:
        factor.append((n,1))

    return factor

def primelist(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def factorization(n):
    plist = primelist(int(n**0.5))
    factor = []
    for p in plist:
        k = 0
        while n%p==0:
            k+=1
            n//=p
        if k>0:
            factor.append((p,k))
        if n==1:
            break
    if n!=1:
        factor.append((n,1))

    return factor

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


def main():
    n = int(input())
    f1 = divisors(n)
    f2 = factorization(n-1)
        
    s = 1
    for f_i in f2:
        s *=(f_i[1]+1)

    for d in f1[1:]:
        t = test(n,d)
        if t==1:
            s+=1

    print(s-1)
    

def test(n,k):

    while n>=k:
        if n%k==0:
            n//=k
        else:
            n%=k
    return n



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n = int(input().strip())
    if n == 2:
        print(1)
        return

    result = 2
    for x in range(2, int(n ** 0.5) + 1):
        if n % x == 1:
            result += 1 if x ** 2 == n - 1 else 2
            continue
        a = n
        while a % x == 0:
            a //= x
        result += a % x == 1
    print(result)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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


Data=[]

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


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

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

print(ans)

Submission status: Accepted

Solution code:
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

divlist = make_divisors(N)
count = 0
for i in divlist[1:]:
    n = N
    while n % i == 0:
        n = n // i
    if n % i == 1:
        count += 1

print(count + len(make_divisors(N-1))-1)

Submission status: Accepted

Solution code:

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

    return divisors


if __name__ == "__main__":
    N = int(input())
    part = len(make_divisors(N-1)) - 1
    cnt = 0
    for k in make_divisors(N):
        if k == 1:
            continue
        tmp_n = N
        while tmp_n % k == 0:
            tmp_n /= k
        if tmp_n % k == 1:
            cnt += 1

    print(part + cnt)

Submission status: Accepted

Solution code:
N = int(input())


def divisor(M):
    div = set()
    for i in range(1, int(N ** 0.5 + 0.5) + 1):
        if M % i == 0:
            div.add(i)
            div.add(M // i)
    return div


def simu(M, X):
    while M % X == 0:
        M //= X
    return M % X == 1


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

A = divisor(N)
A -= {1}
for a in A:
    if simu(N, a):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def isOk(k):
    n = N
    while n % k == 0:
        n //= k
    return n % k == 1

# 約数の全列挙
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.sort(reverse=True)  # ソート
    return divisors

divN = divisors(N)
divN1 = divisors(N - 1)

ans = len([0 for d in divN if d > 1 and isOk(d)]) + len([0 for d in divN1 if d > 1 and isOk(d)])

print(ans)

Submission status: Accepted

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


N = int(input())
ans = set()
div = divisor(N)
for d in div:
    p = N // d
    while d % p == 0 and p != 1:
        d = d // p
    if (d - 1) % p == 0:
        ans.add(p)
for d in divisor(N - 1):
    ans.add(d)
print(len(ans) - 1 if 1 in ans else len(ans))

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

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

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

n = ni()
p = divisor(n)
q = divisor(n-1)
s = set()
ans = 0
for x in p + q:
  m = n
  if x == 1: continue
  while m % x == 0:
    m //= x
  if m % x == 1:
    s.add(x)
print(len(s))

Submission status: Accepted

Solution code:
n=int(input())
m=n-1
c=2 if n>2 else 1
for i in range(2,int(m**.5)+1):
	if m%i==0:
		c+=1
		if m//i!=i:
			c+=1
for i in range(2,int(n**.5)+1):
	if n%i==0:
		j=n//i
		while j%i==0:
			j//=i
		if j%i<=1:
			c+=1
print(c)

Submission status: Accepted

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

    # divisors.sort()
    return divisors
n = int(input())
ans1 = make_divisors(n-1)
ans2 = make_divisors(n)
for i in ans2:
  if i==1:
    continue
  n1 = n
  while n1%i==0:
    n1//=i
  if n1%i==1:
    ans1.append(i)
ans = list(set(ans1))
print(len(ans)-1)

Submission status: Accepted

Solution code:
N = int(input())

def PF(n):
    res = {}
    m = int(n**0.5)
    for i in range(2,m+1):
        cnt = 0
        while n % i == 0:
            n = n//i
            cnt+=1
        if cnt > 0:
            res[i] = cnt
    if n > 1:
        res[n] = 1
    return res

def solve(N):
    ans = 0
# N|K
    pf = PF(N)
    ps,fs = zip(*pf.items())
    cand = []
    pss = []
    for p,f in pf.items():
        pss.extend([p]*f)
    pts = set([1])
    for p in pss:
        nps = [q*p for q in pts]
        pts = pts.union(nps)
    for p in pts:
        if p == 1:
            continue
        M = N
        while M % p == 0:
            M //= p
        if M % p == 1:
            cand.append(p)

    # N |/ K
    M = int(N**0.5+1)
    cand2 = [i for i in range(2,M) if N % i == 1]
    for m in cand2[:]:
        k = (N-1)//m
        cand2.append(k)
    if N >= 3:
        cand.append(N-1)

    cand2 = set(cand2)
    return len(cand)+len(cand2)

print(solve(N))

Submission status: Accepted

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

    divisors.sort()
    return divisors
n = int(input())
ans = []
div_n = make_divisors(n)
for divisor in div_n:
    if divisor == 1:
        continue
    n_ = n
    while n_%divisor == 0:
        n_ = n_//divisor
    if n_ % divisor == 1:
        ans.append(divisor)
ans.extend(make_divisors(n-1))
answer = list(set(ans))
answer.remove(1)

print(len(answer))

Submission status: Accepted

Solution code:
n = int(input())
count = set([n,n-1])

for i in range(2,int((n)**0.5)+5):
    if (n-1)%i == 0:
        count.add(i)
        count.add((n-1)//i)
    if n%i == 0:
        a = n
        while a % i == 0:
            a //= i
        if a%i == 1:
            count.add(i)
    
if 1 in count:
    print(len(count)-1)
else:
    print(len(count))

Submission status: Accepted

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math

#input
#N
#A1 A2 ... AN
N = int(input())


def yakusuu(n):
    #約数全列挙
    l = []
    border = int(math.sqrt(n))
    #print(border) #ここまでしか考えなくて良い
    for i in range(1, border+1):
        #print(i)
        if(n % i == 0):
            l.append(i)
            l.append(int(n/i))
    return l

#print(yakusuu(N))
#print(yakusuu(N-1))
N_yaku = yakusuu(N)
N_1_yaku = yakusuu(N-1)
if(len(N_yaku) != 1):
    del N_yaku[0]
if(len(N_yaku) >= 2 and N_yaku[-1] == N_yaku[-2]):
    del N_yaku[-1]
if(len(N_1_yaku) != 1):
    del N_1_yaku[0]
if(len(N_1_yaku) >= 2 and N_1_yaku[-1] == N_1_yaku[-2]):
    del N_1_yaku[-1]
#print('N_yaku:{}'.format(N_yaku))
#print('N_1_yaku:{}'.format(N_1_yaku))
counter = 0
#N-1の約数であるとき→Nの約数でなければOK
#NとN-1は互いに素なので気にしなくてよかった
'''
for i in N_1_yaku:
    #print(i)
    #print(i in N_yaku)
    if( (i in N_yaku) == False ) :
        print('false_hit:i:{}'.format(i))
        counter += 1
'''
counter += len(N_1_yaku)



#Nの約数であるとき
def hantei_Nyaku(k):
    rep_N = N
    #count = 0
    while True:
        if(rep_N % k == 0):
            rep_N = int(rep_N / k)
            #print(rep_N)
        else:
            break
    if((rep_N - 1) % k == 0):
        return 'Yes'
    else:
        return 'No'



for i in N_yaku:
    #print('i:{}'.format(i))
    #print(hantei_Nyaku(i))
    if(hantei_Nyaku(i) == 'Yes'):
        #print('true_hit')
        counter+=1

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

Submission status: Accepted

Solution code:
import math


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


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

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

    count = len(divisors(N - 1)) - 1

    for div in divisors(N):
        if div == 1:
            continue
        if is_ok(N, div):
            count += 1

    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

    n = int(input())

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

    for i in yakusuu(soinsuu(n)):
        m = n
        while m % i == 0:
            m //= i
        m -= 1
        if m % i == 0:
            ans += 1
    print(ans)


main()

Submission status: Accepted

Solution code:


n = 0

def format_input(filename = None):
	global n
	if filename == None:
		n = int(input())

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 10**12)
		print(n)

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

def get_answer():
	answer = 2
	if n == 2:
		return 1
	for i in range(2, int(n ** 0.5) + 1):
		if (n - 1) % i == 0:
			answer += 2
			if n - 1 == i ** 2:
				answer -= 1
		elif judge(n, i):
			answer += 1
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

def main():
    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
        
    div_n = make_divisors(N)
    ans = 0
    for num in div_n:
        if num == 1:
            continue
        else:
            _N = N
            while _N%num == 0:
                _N //= num
            if _N%num == 1:
                ans += 1
    
    div_n = make_divisors(N-1)
    for num in div_n:
        if num == 1:
            continue
        else:
            _N = N
            while _N%num == 0:
                _N //= num
            if _N%num == 1:
                ans += 1
                
    print(ans)
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import product

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

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
def _num(arr):
    out = 1
    for item in arr:
        out *= (item[1]+1)
    return out

n_orig = int(input())
arr = factorization(n_orig)
arr1 = factorization(n_orig - 1)

if n_orig==2:
    print(1)
elif len(arr)==1 and arr[0][1]==1:
    print(_num(arr1))
else:
    tmp = _num(arr1)-1
    
    for nums in product(*[range(item[1]+1) for item in arr]):
        n = n_orig
        kk = 1
        for num, base in zip(nums, arr):
            base = base[0]
            kk *= base**num
        if (kk==1):
            continue
        while n%kk==0:
            n /= kk
        if ((n - 1) % kk == 0):
            tmp += 1
    print(tmp)

Submission status: Accepted

Solution code:
def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    return array


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

candidates = divisors(n)
candidates.remove(1)
for k in candidates:
    num = n // k
    while num % k == 0:
        num //= k
    residue = num % k
    if residue == 1:
        ans.add(k)

ans.discard(1)
print(len(ans))

Submission status: Accepted

Solution code:
N = int(input())


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


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


cand = divisors(N) + divisors(N - 1)

ans = 0
for d in cand:
    if test(N, d):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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

    # divisors.sort()
    return divisors


n = int(readline())
ans = len(make_divisors(n - 1)) - 1
for check in make_divisors(n):
    if check != 1:
        flag = True
        memo = n
        while flag:
            memo //= check
            if memo % check != 0:
                flag = False
        if memo % check == 1:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
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

L = len(make_divisors(N))

A = make_divisors(N)

ans = 0
for i in range(1,L):
    t = N
    while t%(A[i]) == 0:
        t = t//A[i]
    if t%A[i] == 1:
        ans = ans + 1
        
print(ans + len(make_divisors(N-1)) -1)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(200000)
import math


def divisor(n):
    divs = list()
    i = 1
    while i * i <= n:
        if n % i == 0:
            divs.append(i)
            if i * i != n:
                divs.append(n // i)
        i += 1
    return list(sorted(divs))


def read():
    N = int(input())
    return N,


def solve(N):
    ptn = deque()
    factors_n1 = divisor(N-1)[1:]
    factors_n = divisor(N)[1:]
    count = len(factors_n1)
    for k in factors_n:
        n = N
        while n >= k:
            if n % k == 0:
                n = n // k
            else:
                n = n % k
        if n == 1:
            count += 1
    return count
    

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


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 solve():
    N = int(rl())
    
    divisors1 = set(make_divisors(N - 1)[1:])
    divisors2 = set(make_divisors(N)[1:])
    
    for divisor in divisors2:
        tmp = N
        while tmp % divisor == 0:
            tmp //= divisor
        if tmp % divisor == 1:
            divisors1.add(divisor)
    print(len(divisors1))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def rest(n, i):
    while n%i == 0:
        n //= i
    return n

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

ans = [N-1, N]

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

print(len(set(ans)))

Submission status: Accepted

Solution code:
n = int(input())

ans = [n]
if n != 2:
    ans.append(n - 1)
for k in range(2, min(n - 1, 1000001)):
     tmp = n
     while tmp % k == 0:
         tmp //= k
     tmp %= k
     if tmp == 1:
         ans.append(k)
if 1000000 < n:
    ks = [k for k in ans]
    for k in ks:
        if k < n - 1 and (n - 1) % k == 0:
            ans.append((n - 1) // k)
ans = set(ans)
print(len(ans))

Submission status: Accepted

Solution code:
import sys
import math

input = sys.stdin.readline

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(reverse=True)
    return divisors

arr1 = make_divisors(N)
arr2 = make_divisors(N-1)
arr1.pop()
arr2.pop()

ans = len(arr2)

for value in arr1:
    temp = N
    while temp % value == 0:
        temp = temp // value
        if temp == 0:
            break
    if temp % value == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
if n == 2:
    print(1)
    exit()

fact = [n]
fact1 = [n-1]
i = 2
while i * i <= n:
    if n % i == 0:
        fact += [i]
        if n // i != i:
            fact += [n//i]
    i += 1

i = 2
while i * i <= n-1:
    if (n-1) % i == 0:
        fact1 += [i]
        if (n-1) // i != i:
            fact1 += [(n-1)//i]
    i += 1

ans = 0
for x in fact:
    k = n
    while k % x == 0:
        k //= x
    if k % x == 1:
        ans += 1

print(ans + len(fact1))

Submission status: Accepted

Solution code:
def divisors(n):
    x = set()
    m = 1
    while m * m <= n:
        if n % m == 0:
            x.add(m)
            x.add(n // m)
        m += 1
    return x

n = int(input())
d = divisors(n)
ans = 0
for k in d:
    if k == 1:
        continue
    nn = n
    while nn % k == 0:
        nn = nn // k
    ans += nn % k == 1

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

Submission status: Accepted

Solution code:
import sys
from math import sqrt, floor

def divisors(n):
    res = set()
    for i in range(1, floor(sqrt(n)) + 1):
        if n % i == 0:
            res.add(i)
            res.add(n // i)
    return res

n = int(sys.stdin.readline().rstrip())

def main():
    res = divisors(n - 1)
    cnt = len(res) - 1 + 1
    for i in range(2, floor(sqrt(n)) + 1):
        if i in res: continue
        m = n
        while m % i == 0:
            m //= i
            if (m - 1) % i == 0:
                cnt += 1
    print(cnt)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

if N == 2:
	print(1)
	exit()
if N == 3:
	print(2)
	exit()
def yakusu(n):
	rn = int(n ** 0.5)
	ret = 2
	for i in range(2, rn+1):
		if n % i == 0:
			ret += 2
	if rn*rn == n:
		ret -= 1
	return ret

#A = [True for i in range(10**6 + 1)]
ans = 1 # K = N
rn = int(N ** 0.5)
for i in range(2, rn+1):
	if N % i > 0:
		continue
	n = N
	while n % i == 0:
		n = n // i
	if n % i == 1:
		ans += 1
	n = N
	j = N // i
	if j <= i:
		continue
	while n % j == 0:
		n = n // j
	if n % j == 1:
		ans += 1
print(ans + yakusu(N-1) - 1)

Submission status: Accepted

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

main()

Submission status: Accepted

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

N=int(input())
li=factor(N)
fac=factor(N-1)
res=len(fac)-1
for i in range(len(li)):
    if(li[i]==1):
        continue
    tmp=N
    while(tmp%li[i]==0):
        tmp//=li[i]
    if(tmp%li[i]==1):
        res+=1
print(res)

Submission status: Accepted

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

    # divisors.sort()
    return divisors

N = int(input())
md = make_divisors(N)
mdd = make_divisors(N-1)
se = set(md + mdd)
li = list(se)
ans = 0
for i in li:
  if i != 1:
    n = N
    while n >= i:
      if n % i == 0:
        n = n // i
      else:
        n = n % i
    if n == 1:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

ans = 2 # N and N-1
for K in range(2, N):
    if K*K>N: break
    n = N
    if n%K!=0: continue
    while n%K==0: n//=K
    if n%K==1: ans +=1

y = 0
N_ = N-1
for K in range(2, N):
    if K*K>=N_: break
    if N_%K==0: y +=2
if K*K==N_: y += 1

print(ans+y)

Submission status: Accepted

Solution code:
import math

n=input()
res=2

if n==2:
    print 1
    exit(0)
if n==3:
    print 2
    exit(0)
for i in xrange(2, int(math.sqrt(n)+1)):
    k=n
    while k>1:
        if k%i==0:
            k=k/i
        else:
            k=k%i
            break
        
    if k==1:
        res+=1

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

print res

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
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()
    return divisors
n = int(input())
if n == 2:
    print(1)
elif n == 3:
    print(2)
elif n == 4:
    print(3)
else:
    count = 2
    check_list = make_divisors(n-1)
    count += len(check_list)
    check_list = make_divisors(n)
    for k in check_list:
        temp_n = n // k
        while(True):
            if temp_n % k == 0:
                temp_n = temp_n // k
            elif temp_n % k == 1:
                count += 1
                break
            else:
                break
    print(count)