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:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

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

mod = 10**9 + 7

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

#################

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

N = I()

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

print(ans+len(D2)-1)

Submission status: Accepted

Solution code:
N = int(input())

def factoring(k): #kを因数分解し、素因数とその個数を辞書に入れて返す。
    import math
    dic = dict()
    n = int(math.sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] = count
    if k != 1: #sqrt(k)までチェックしてもkが1になっていない --> kが素因数
        dic[k] = 1
    return dic



def make_divisors(n):
    import math
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0: #割り切れるとき
            divisors.append(i)
            if i != n//i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

dic1 = factoring(N - 1)

# 素因数分解をすることにより、約数の個数を求める
ans = 1
for i in dic1:
    ans *= (dic1[i] + 1)

ans -= 1 #約数の1つである1は使えない
# print (ans)

lst = make_divisors(N) #Nの約数を全列挙

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



print (ans)
# print (dic1)
# print (lst)

Submission status: Accepted

Solution code:
import math

def divisor(num):
    if num < 0:
        return 0
    if num == 1:
        return [1, ]

    divisor_list = [1, ]
    divisor_list_r = [num, ]

    i = 2
    while i * i <= num:
        if num % i == 0:
            divisor_list.append(i)
            if i != num // i:
                divisor_list_r.append(num//i)
        i += 1

    return divisor_list+divisor_list_r[::-1]


N = int(input())
ans = len(divisor(N-1))-1
cand = divisor(N)

for i, num in enumerate(cand[1:]):
    num2 = N
    while num2 >= num:
        tmp1, tmp2 = divmod(num2, num)
        if tmp2 == 0:
            num2 = tmp1
        else:
            num2 = tmp2
    if num2 == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

ans = set()

def check(k):
    global ans, n
    if k <= 1 or k > n:
        return
    c = n
    while c % k == 0 and c >= k:
        c //= k
    c %= k
    if c == 1:
        ans.add(k)

for i in range(1, n):
    if i ** 2 > n:
        break
    if i ** 2 == n:
        check(i)
    elif n % i == 0:
        check(i)
        check(n // i)

m = n - 1
for i in range(1, m):
    if i ** 2 > m:
        break
    if i ** 2 == m:
        check(i)
    elif m % i == 0:
        check(i)
        check(m // i)

print(len(ans))

Submission status: Accepted

Solution code:
def make_divisors(n: int) -> list:
    """自然数nの約数を列挙したリストを出力する
    計算量: O(sqrt(N))
    入出力例: 12 -> [1, 2, 3, 4, 6, 12]
    """
    divisors = []
    for k in range(1, int(n ** 0.5) + 1):
        if n % k == 0:
            divisors.append(k)
            if k != n // k:
                divisors.append(n // k)
    divisors = sorted(divisors)
    return divisors


n = int(input())
ans = 0
for num in make_divisors(n):
    if num == 1:
        continue
    res = n
    while res >= num:
        if res % num == 0:
            res = res // num
        else:
            res = res - (res // num) * num
    if res == 1:
        ans += 1
print(ans + len(make_divisors(n - 1)) - 1)

Submission status: Accepted

Solution code:
N=int(input())
l=[]
for i in range(2,10**6+1):
    if not N%i:
        if i>N//i:
            break
        if i**2==N:
            l.append(i)
            break
        l+=[i,N//i]
l.append(N)
a=0
for i in l:
    t=N
    while t>=i:
        if t%i:
            t%=i
        else:
            t//=i
    if t==1:
        a+=1
N-=1
for i in range(1,10**6+1):
    if not N%i:
        if i>N//i:
            break
        if i**2==N:
            a+=1
            break
        else:
            a+=2
print(a-1)

Submission status: Accepted

Solution code:
import sys
n = int(input())
if n == 2:
	print(1)
	sys.exit()
divs = []
i = 2
while i*i <= n:
	if n%i == 0:
		divs.append(i)
		if i*i < n:
			divs.append(n//i)
	i += 1
divs.append(n)

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

for d in divs:
	tmp = n
	while tmp%d == 0:
		tmp //= d
	if tmp%d == 1:
		ans.add(d)
print(len(ans))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def divisor_list(N): #約数のリスト
    if N == 1: return [1]
    res = []
    for i in range(1,N):
        if i*i >= N: break
        if N%i == 0:
            res.append(i)
            res.append(N//i)
    if i*i == N: res.append(i)
    return res#sorted(res)

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read


N = int(input())
div = divisor_list(N)
div2 = divisor_list(N-1)

ans = set()
for d in div:
    if d==1: continue
    n = N
    while n%d==0:
        n//=d
    if n%d==1: ans.add(d)

#print(ans,div2)

ans = len(ans)+len(div2)-1
print(ans)

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())
div = make_divisors(n)[1:]
s = set(make_divisors(n - 1))
for d in div:
    t = n
    while t % d == 0:
        t //= d
    if (t - 1) % d == 0:
        s.add(d)
print(len(s) - 1)

Submission status: Accepted

Solution code:
import sys
N = int(input())

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

now = 1
ans = 0

def want(m):

    ns = N
    while ns % m == 0:
        ns = ns // m
    return ns % m

while now ** 2 <= N:

    if N % now == 0:

        n2 = N // now
        #print (now,n2)

        if now != 1:
            rev = want(now)
            if rev == 1:
                ans += 1


        if n2 != now and n2 != 1:

            rev = want(n2)
            if rev == 1:
                ans += 1

    now += 1

now = 1
while now ** 2 <= N-1:

    if (N-1) % now == 0:
        n2 = (N-1) // now

        if now != 1:
            ans += 1
        if now != n2:
            ans += 1
    now += 1
        
print (ans)

Submission status: Accepted

Solution code:
import math

n = int(input())

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

    # divisors.sort()
    return divisors

def factorize(N):
    up = int(math.sqrt(N))+2
    out = {}

    for i in range(2,up):
        if N%i == 0:
            temp = N
            count = 0
            while(True):
                N = N//i
                count += 1
                if N%i != 0:
                    break
            out[i] = count
        else:
            continue
    if N != 1:
        out[N] = 1
    return out

yakusuu = make_divisors(n)[1:]

soinnsuu = factorize(n)
soinnsuu2 = factorize(n-1)

# print(yakusuu)
# print(soinnsuu)
# print(soinnsuu2)

ans = 0
for y in yakusuu:
    hoge = n
    while True:
        if hoge%y == 0:
            hoge = hoge//y
        else:
            break
    if hoge%y == 1:
        ans+=1

ok = {}
for key in soinnsuu2.keys():
    if not key in soinnsuu:
        ok[key] = soinnsuu2[key]
# print(ok)

ex = 1
for key in ok.keys():
    ex *= ok[key]+1

ex-=1

# print(ans)
# print(ex)
print(ans+ex)

# test = []
# for i in range(2,3141):
#     base = 3141
#     while True:
#         if base < i:
#             if base == 1:
#                 test.append(i)
#             break
#         if base%i == 0:
#             base /= i
#         else:
#             base %= i
# print(test)

Submission status: Accepted

Solution code:
n=int(input())
ans=0
for i in range(2,int(n**0.5)+1):
    t=n
    if t%i!=0:
        continue
    while t%i==0:
        t//=i
    if t%i==1:
            ans+=1
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
import collections
c=collections.Counter(prime_factorize(n-1))
t=1
for i in c.values():
    t*=i+1
print(ans+t)

Submission status: Accepted

Solution code:
def examA():
    X, Y, Z = LI()
    X, Y = Y,X
    X,Z = Z, X
    print(X,Y,Z)
    return

def examB():
    N, M = LI()
    A = LI()
    need = (sum(A)-1)//(4*M) + 1
    ans = 0
    #print(need)
    for a in A:
        if a>=need:
            ans += 1
    if ans>=M:
        print("Yes")
    else:
        print("No")
    return

def examC():
    N, K = LI()
    ans = N%K
    if K-ans<ans:
        ans = K-ans
    print(ans)
    return

def examD():
    def bfs(n):
        # 点の数、スタートの点、有向グラフ
        W = [""] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        que = deque()
        for i in range(1,10):
            que.append(str(i))
            W[i-1] = str(i)
        i = 9
        while(i<n):
            now = que.popleft()
            end = now[-1]
            for j in [-1,0,1]:
                ne = int(end)+j
                if 0<=ne<=9:
                    W[i] = now + str(ne)
                    que.append(W[i])
                    i += 1
                    if i==n:
                        break
        return W
    K = I()
    if K<=12:
        ans = K
        print(ans)
        return
    ans = bfs(K)[-1]
    print(ans)
    return

def examE():
    N, K, C = LI()
    S = SI()
    L = set()
    R = set()
    prev = -inf
    for i,s in enumerate(S):
        if s=="x":
            continue
        if prev+C>=i:
            continue
        L.add(i)
        prev = i
    if len(L)>K:
        print()
        return
    prev = inf
    for i in range(N)[::-1]:
        s = S[i]
        if s=="x":
            continue
        if prev-C<=i:
            continue
        R.add(i)
        prev = i
    #print(L,R)
    ans = []
    for i in L:
        if i in R:
            ans.append(i+1)
    if not ans:
        print()
        return
    ans.sort()
    for v in ans:
        print(v)
    return

def examF():
    def factorization(n):
        arr = defaultdict(int)
        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[i] = cnt
        if temp != 1:
            arr[temp] = 1
        if arr == []:
            arr[n] = 1
        return arr

    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 check(n,k):
        if n%k==0:
            n //=k
        else:
            if n%k==1:
                return 1
            else:
                return 0
        return check(n,k)
    N = I()
    F = factorization(N-1)
    #print(F)
    ans = 0
    cur = 1
    for [f,i] in F.items():
        cur *= (i+1)
    ans += cur-1
    M = make_divisors(N)
    #print(M)
    for k in M:
        if k==1:
            continue
        ans += check(N,k)
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examF()

"""

"""

Submission status: Accepted

Solution code:
from collections import defaultdict


def get_divisor(n: int) -> list:
    divisor = []
    for i in range(1, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            divisor.append(i)
            if n // i != i:
                divisor.append(n // i)
    # divisor.sort() # if you want sorted divisors
    return divisor


n = int(input())

d0 = get_divisor(n)
ans0 = 0  # n自身
for di in d0:
    if di == 1:
        continue
    x = n // di
    while x % di == 0:
        x = x // di
    if x % di == 1:
        # print(di)
        ans0 += 1

d1 = get_divisor(n - 1)
ans1 = len(d1) - 1

ans = ans0 + ans1
# print(n - 1, ':', d1)
# print(n, ':', d0)
print(ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1<<32 else [2, 3, 5, 7, 11, 13, 17] if n < 1<<48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)
def calc(n, k):
    if n % k == 0:
        return n // k
    return n % k
def chk(n, k):
    while n >= k:
        n = calc(n, k)
    return 1 if n == 1 else 0

N = int(input())
L = list(set(divisors(N) + divisors(N-1)))
print(len([l for l in L if l > 1 and chk(N, l)]))

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
n = int(input())
ans = 0
for i in make_divisors(n):
    if i != 1:
        x = n
        flag = True
        while flag:
            x //= i
            if x % i != 0:
                flag = False
        if x % i == 1:
            ans += 1
ans += len(make_divisors(n-1))-1
print(ans)

Submission status: Accepted

Solution code:
import copy as cp

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

N = int(input())
div1_l = make_divisors(N-1)
count = len(div1_l)

div_l = make_divisors(N)
for d in div_l:
    n = N
    while True:
        if n%d == 0:
            n = n//d
        else:
            if n%d == 1:
                count += 1
            break
if N == 2:
    count = 1

print(count)

Submission status: Accepted

Solution code:
n = int(input())
ans = 0
for i in range(2,10**6+1):
  m = int(n)
  while True:
    if m % i == 0:
      m //= i
    elif m % i == 1:
      #print(i)
      ans += 1
      break
    else:
      break
for i in range(1,10**6+1):
  if (n-1) % i == 0 and (n-1) // i > 10**6:
    #print((n-1)//i,i)
    ans += 1
if n > 10**6:
  ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from math import sqrt
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    s=set()
    for i in range(1,int(sqrt(N))+1):
        if (N-1)%i==0:
            s.add(i)
            s.add((N-1)//i)
        else:
            if N%i==0:
                tmp=N
                while True:
                    if tmp%i==0:
                        tmp//=i
                    else:
                        tmp-=tmp//i*i
                    if tmp==1:
                        s.add(i)
                        break
                    if tmp<i:
                        break
    print(len(s))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-
import sys
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

N = int(input())

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

for d in divs:
    tn = N
    while tn>=d and tn%d==0:
        tn //= d
    if tn==1 or tn%d==1:
        ans += 1

if N==2:
    print(1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())

def yakusu(n):#約数列挙
    list1 = []
    list2 = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            list1.append(i)
            if i != n // i:
                list2.append(n // i)
    list2.reverse()
    return list1 + list2

def A(x):
    m = l1[len1 - i - 1]
    while m > 0:
        if m % x == 0:
            m //= x
        elif m % x == 1:
            return True
        else:
            return False
    return False

l1 = yakusu(N)
len1 = len(l1)

l2 = yakusu(N - 1)

ans = len(l2) - 1

for i in range(1, len1):
    if A(l1[i]):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def divisors(n):
  ret=[]
  for i in range(2,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())
if n==2:
  print(1)
else:
  divs1=divisors(n)
  divs2=divisors(n-1)
  cand=divs2
  for val in divs1:
    tmp=n
    while tmp%val==0:
      tmp=tmp//val
    if tmp%val==1:
      cand.append(val)
  if n not in cand:
    cand.append(n)
  if n-1 not in cand:
    cand.append(n-1)
  print(len(cand))

Submission status: Accepted

Solution code:
import math
N = int(input())
ans = 0
li = []
for i in range(1,math.floor(math.sqrt(N-1))+1):
    if (N-1)%i==0:
        ans += 1
        if not (N-1)//i == i:
            ans += 1
for i in range(1,math.floor(math.sqrt(N))+1):
    if N%i==0:
        li.append(i)
        if not N//i == i:
            li.append(N//i)
for x in li:
    if x != 1:
        e = 1
        while N%(x**e) == 0:
            e += 1
        m = N//(x**(e-1))
        if m%x == 1:
            ans += 1
print(ans-1)

Submission status: Accepted

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

N = int(input())


def yaku(n):
    ret = []
    for num in range(1, int(math.sqrt(n)+3)):
        if n % num == 0:
            p = n//num
            if num < p:
                ret.append(num)
                ret.append(p)
            elif num == p:
                ret.append(p)
    return ret

ans = len(yaku(N-1))-1
for num in yaku(N):
    if num == 1: continue
    T = N
    while T%num == 0:
        T //= num
    if (T-1)%num == 0:
        ans += 1

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()
divN = divisor(N)
for d in divN:
    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 bisect

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 len(divisors) // 2

n = int(input())
ans = 1
if n == 2:
  print(1)
  exit()
if n == 3:
  print(2)
  exit()
a = []
for i in range(2,int(n ** 0.5)+1):
  now = n
  while not now % i:
    now //= i
  if now % i == 1:
    a.append(i)
    ans += 1
ans += make_divisors(n-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
n=int(input())
if n==2:
  print(1)
  sys.exit()
l=[n]
for i in range(2,int(n**0.5)+1):
  if n%i==0:
    l.append(i)
l=list(set(l))
L=[]
for j in range(len(l)):
  x=n
  k=l[j]
  while x%k==0:
    x=x//k
  if x%k==1:
    L.append(l[j])

l2=[n-1]
for i in range(2,int((n-1)**0.5)+1):
  if (n-1)%i==0:
    l2.append(i)
    l2.append((n-1)//i)
l2=list(set(l2))
l2.sort()

print(len(L+l2))

Submission status: Accepted

Solution code:
from fractions import gcd

def divisor(n):
    divisors = []
    i = 1
    while i * i < n:
        if n % i == 0:
            divisors.append(i)
            divisors.append(n // i)
        i += 1
    if i * i == n:
        divisors.append(i)
    divisors.sort()
    return divisors

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

Submission status: Accepted

Solution code:
n = int(input())
A = [n]
B = []
for i in range(2, int(n**0.5)+1):
    # if n%i==0:
    t = n
    u = n
    f = 0
    g = 0
    while t%i==0:
        t //= i
        f = 1
    while u%(n//i) == 0:
        u //= (n//i)
        g = 1
    if (t - 1) % i == 0 and f==1:
        B.append(i)
    if (u - 1) % (n//i) == 0 and g==1:
        B.append(n//i)

for i in range(1, int((n-1)**0.5) + 1):
    if (n-1)%i == 0:
        B.append(i)
        B.append((n-1)//i)
# AA = A
# # AA = list(set(A))
# A = [[AA[i], n//AA[i]] for i in range(len(AA))]
# print(A)
# B = []
# for i in range(len(A)):
#     a = A[i][0] - 1
#     # for i in range(1, int(a**0.5)+1):
#     #     if a%i==0 and a//i != 1:
#     #         B.append(a//i)
#     if a % A[i][1] == 0:
#         B.append(A[i][0])
# print(B)
print(len(set(B)))

Submission status: Accepted

Solution code:
import math
n=int(input())
s=math.ceil((n**0.5))
a=set([])
if n==2:print(1);exit()
a.add(n)
a.add(n-1)
for i in range(2,int((n-1)**0.5)+1):
    if (n-1)%i==0:
        a.add(i)
        a.add((n-1)//i)
def check(dived,diving):
    while dived>=2:
        if dived<diving:return False
        if dived%diving==0:
            dived//=diving
        else:
            dived%=diving
    return True
for j in range(2,int(n**0.5)+1):
    if n%j==0:
        if check(n,j):a.add(j)
print(len(a))

Submission status: Accepted

Solution code:
import math
N = int(input())

ans = 0

p1_array = [N]
for i in range(2, int(math.sqrt(N) + 1)):
    if N % i == 0:
        if N == i * i:
            p1_array.append(i)
            break
        else:
            p1_array.append(i)
            p1_array.append(N//i)


for p in p1_array:
    n = N
    while(n % p == 0):
        n = n // p
    if n % p == 1:
        ans += 1

if N != 2:
    N = N-1
    p2_array = [N]
    for i in range(2, int(math.sqrt(N) + 1)):
        if N % i == 0:
            if N == i * i:
                p2_array.append(i)
                break
            else:
                p2_array.append(i)
                p2_array.append(N//i)
    ans += len(p2_array)

print(ans)

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[1:]

n = int(input())
ans = set()

divisors = make_divisors(n)
for value in divisors:
  key = n
  while key % value == 0:
    key //= value
  if key%value == 1:
    ans.add(value)

divisors2 = set(make_divisors(n-1))
ans = ans.union(divisors2)
print(len(ans))

Submission status: Accepted

Solution code:
def divisor(n): #約数全列挙
    ans = [n]
    i = 2
    while i**2 <= n:
        if n%i == 0:
            ans.append(i)
            if i**2 < n:
                ans.append(n//i)
        i += 1
    ans.sort()
    return ans

n = int(input())
if n == 2:
    print(1)
    exit()
ans = len(divisor(n-1))
data = divisor(n)
for k in data:
    m = n
    while m%k == 0:
        m //= k
    if (m-1)%k == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

def y(n):
    yaku = set()
    for i in range(1, 10 ** 6 + 1):
        if n % i == 0:
            yaku.add(i)
            yaku.add( n // i)
    yaku.remove(1)
    return yaku

ans = len(y(n - 1))

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def fact(n):
        if n < 4:
            return set([n])
        i = 2
        res = set([n])
        while i ** 2<= n:
            if n%i == 0:
                res.add(i)
                m = n//i
                if m != i:
                    res.add(m)
            i += 1
        return res

    def check(n,i):
        while n >= i:
            if n%i == 0:
                n //= i
            else:
                n -= i
        if n == 1:
            return 1
        return 0
    n = I()
    if n == 2:
        print(1)
        return
    ans = {2,n}
    f = fact(n)
    for i in f:
        m = n
        while not m%i:
            m //= i
        if m % i == 1:
            ans.add(i)
    ans |= fact(n-1)
    print(len(ans))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#nの約数とn-1の約数全部愚直
n = int(input())
fct1 = []
fct2 = []
for i in range(1,int(n**(1/2))+10):
    if n%i==0:
        fct1.append(i)
        fct2.append(n//i)
    if (n-1)%i==0:
        fct1.append(i)
        fct2.append((n-1)//i)

fct = set(fct1+fct2)
if 1 in fct:
    fct.remove(1)
ans = 0
for k in fct:
    n2 = n
    while n2 and n2%k==0:
        n2//=k
    n2%=k
    if n2==1:
        ans += 1
print(ans)

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
x=int(input())
ans=0
di=make_divisors(x)
for i in di:
    if i==1:
        continue
    p=x
    while p%i==0:
        p=p//i
    q=x//p
    if p%i==1 or p==1:
        ans+=1
d=make_divisors(x-1)
print(ans+len(d)-1)

Submission status: Accepted

Solution code:
def factorize_dict(n):
    i=2
    result={}
    while True:
        if i**2>n:
            break
        count=0
        while n%i==0:
            n//=i
            count+= 1
        if count!=0:
            result[i]=count
        i+=1
    if n>1:
        result[n]=1
    return result

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 judge(n,k):
    while n%k==0:
        n//=k
    return n%k

def main():
    n=int(input())
    ans=0
    f_d=factorize_dict(n-1)
    tmp=1
    for v in f_d.values():
        tmp*=(v+1)
    tmp-=1
    ans+=tmp
    D=make_divisors(n)
    for d in D:
        if d==1:
            continue
        if judge(n,d)==1:
            ans+=1
    print(ans)
    
if __name__=='__main__':
    main()