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
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

ans = 0

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

for d in make_divisors(N):
    if d == 1: continue
    tmp = N
    while tmp % d == 0:
        tmp //= d
    if tmp % d == 1:
        ans += 1    


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

Submission status: Accepted

Solution code:
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 divisorize(n):
    ## 約数
    f = factorization(n)
    divisors = [1]
    for k in range(len(f)):
        num_divisors = len(divisors)
        for i in range(1, f[k][1] + 1):
            for j in range(num_divisors):
                divisors.append(divisors[j] * f[k][0] ** i)
    return sorted(divisors)
  
n = int(input())
ans = 0
chk = divisorize(n-1)
for i in divisorize(n)[1:]:
  m = n
  while True:
    if m == 1:
        ans += 1
        chk.append(i)
        break
    if m < i:
      break
    if m%i == 0:
      m = m//i
    else:
      m = m%i

chk = set(chk)
print(len(chk)-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

n = int(input())
out = make_divisors(n)
ans = []
for i in out:
    if i == 1:
        continue
    m = n
    while m % i == 0:
        m //= i
    if m == 1 or m % i == 1:
        ans.append(i)
ans += make_divisors(n - 1)
# print(set(out))
print(len(set(ans)) - 1)

Submission status: Accepted

Solution code:
import math

N = int(input())

ans = 0

for i in range(2, N + 1):
    if i * i > N:
        if N == 2:
            ans += 1
        else:
            ans += 2
        break
    if (N - 1) % i == 0:
        ans += 1
        if (N - 1) // i != i:
            ans += 1
    elif N % i == 0:
        cand = [i]
        if N // i != i:
            cand.append(N // i)
        for c in cand:
            tmp = N
            while tmp % c == 0:
                tmp //= c
            if tmp % c == 1:
                ans += 1

# i = N-1, N
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt


def divisors(x):
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            yield i
            if x // i != i:
                yield x // i


n = int(input())

ans = 0
for e in divisors(n):
    if e == 1:
        continue

    r = n
    while r % e == 0:
        r //= e

    if r % e == 1:
        ans += 1

ans += len(list(divisors(n - 1))) - 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())

# 割らない場合
ans = make_divisors(N-1)[1:]
n_div = make_divisors(N)[1:]

for d in n_div:
    n = N
    while n % d == 0:
        n //= d
    if n % d == 1:
        ans.append(d)

print(len(ans))

Submission status: Accepted

Solution code:
def div(x):
    D = set()
    d = 1
    while d*d <= x:
        if x % d == 0:
            D.add(d)
            D.add(x//d)
        d += 1
    return D


n = int(input())
cnt = 0
for d in div(n) | div(n-1):
    if d == 1:
        continue
    tmp = n
    while tmp % d == 0:
        tmp = tmp // d
    if tmp % d == 1:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
if n==2: print(1); exit()
Ans = set([n-1])
for i in range(2, int((n-1)**(1/2))+1):
    if (n-1)%i == 0: Ans.add(i); Ans.add((n-1)//i)
Div = set([n])
for i in range(2, int(n**(1/2))+1):
    if n%i == 0: Div.add(i); Div.add(n//i)
for d in Div:
    m = n
    while m%d == 0: m//=d
    if m%d == 1: Ans.add(d)
print(len(Ans))

Submission status: Accepted

Solution code:
def gen(x):
    root = int(pow(x, 0.5))
    for k in range(1, root + 1):
        if x % k == 0:
            yield k
            if k != x // k:
                yield x // k


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

    # N%K!=0
    cnt = sum(1 for _ in filter(lambda x: x > 1, gen(N - 1)))

    # N%K==0
    for k in filter(lambda x: x > 1, gen(N)):
        x = N
        while x % k == 0:
            x //= k

        if x % k == 1:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ans = set()
    divisors = get_divisors(n)
    ans |= set(get_divisors(n-1))
    ans |= set([divisor for divisor in divisors if is_ok(n, divisor)])
    ans -= set([1])
    print(len(ans))

def is_ok(n, d):
    if d < 2:
        return False
    while n%d == 0:
        n //= d
    return n%d == 1

def get_divisors(n):
    out = []
    if n < 1:
        return out
    m = int(n**0.5)
    for i in range(1, m+1):
        if not n%i:
            out.append(i)
            if n != i**2:
                out.append(n//i)
    return out


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

for x in make_divisors(n-1):
    if x != 1:
        ans.add(x)

for x in make_divisors(n):
    if x ==1 :
        continue
    if x == n:
        ans.add(x)
        continue
    m = n
    while m % x == 0:
        m = m//x
    
    if m % x == 1:
        ans.add(x)

print(len(ans))

Submission status: Accepted

Solution code:
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
#import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""

#from collections import deque, defaultdict, Counter


def divisor(n):
    """ nの約数列挙 """
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass  # sortされていない


def main():
    N = int(input())
    div_1 = divisor(N)
    div_2 = divisor(N-1)
    cnt = 0

    for i in div_1:
        if i == 1:
            continue
        tmp = N
        while tmp % i == 0:
            tmp = tmp / i
        tmp = tmp % i
        if tmp == 1:
            cnt += 1

    cnt += len(div_2) - 1
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


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):
    ndiv = make_divisors(N)
    count = 0
    for div in ndiv:
        if div == 1:
            continue
        n = N
        while n % div == 0:
            n //= div
        if n % div == 1:
            count += 1
    print(len(make_divisors(N-1))+count-1)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = []

for i in range(1,round((N-1)**0.5)+1):
  if (N-1)%i == 0:
    ans.append(i)
    if (N-1)//i != i:
      ans.append((N-1)//i)

ans.remove(1)
ans.append(N)
for i in range(2,round(N**0.5)+1):
  if N%i == 0:
    n = N
    while n%i==0:
      n//=i
    if n%i==1:
      ans.append(i)

print(len(ans))

Submission status: Accepted

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

ans = []
l = int(math.log2(N))
for i in range(1,l+1):
  if round(N**(1/i))**i==N:
    ans.append(round(N**(1/i)))

for i in range(2,round((N-1)**0.5)+1):
  if (N-1)%i == 0:
    ans.append(i)
    if (N-1)//i != i:
      ans.append((N-1)//i)
if N>2:
  ans.append(N-1)

for i in range(2,round(N**0.5)+1):
  if N%i == 0:
    n = N
    while n%i==0:
      n//=i
    if n != 1 and n%i==1:
      ans.append(i)

print(len(ans))

Submission status: Accepted

Solution code:
def check(i):
	tot=k
	pw=0
	while(tot%i==0):
		tot//=i
		pw+=1
	if(tot%i==1):
		other = tot//i
		if(pw==0 and other>=2 and other<=k):
			setl.add(other)
		setl.add(i)

import math
k=int(input())
if(k==2):
	print(1)
	exit()
setl = set()
setl.add(k); setl.add(k-1)
for x in range(2,int(math.sqrt(k))+1):
	check(x)
	# check(k//x)
print(len(setl))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


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


N = int(input())

# N - 1
divs1 = f1(N - 1)
ans1 = len(divs1) - 1

# N
divs = f1(N)
ans2 = 0
for i in range(1, len(divs)):
    t = N
    d = divs[i]
    while t % d == 0:
        t //= d
    if t % d == 1:
        ans2 += 1

print(ans1 + ans2)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = 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)

    # divisors.sort()
    return divisors


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

    divs = make_divisors(N)
    divs2 = make_divisors(N - 1)

    ans = set(divs2)
    for k in divs:
        tmpN = N
        if k == 1:
            continue
        while tmpN % k == 0:
            tmpN /= k

        if tmpN % k == 1:
            ans.add(k)

    print(len(ans) - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
k = 2
count = set()
while k * k <= n:
    if n % k == 1:
        count.add(k)
        count.add((n-1)//k)
    elif n % k == 0:
        n_copy = n
        while n_copy % k == 0:
            n_copy //= k
        if n_copy % k == 1:
            count.add(k)
    k += 1
if n > 2:
    count.add(n-1)
count.add(n)
print(len(count))

Submission status: Accepted

Solution code:

def factorize(n):
    ## 素因数分解
    # arr = factorize(20)
    # arr == [[2, 2], [5, 1]]
    
    result = []
    tmp = n
    for k in range(2, int(n ** 0.5) + 1):
        cnt = 0
        while tmp % k == 0:
            cnt += 1
            tmp //= k
        if cnt > 0:
            result.append([k, cnt])
    if tmp != 1:
        result.append([tmp, 1])
    return result

def divisorize(n):
    ## 約数
    # arr = factorize(20)
    # arr == [2, 4, 5, 10, 20]
    f = factorize(n)
    divisors = [1]
    for k in range(len(f)):
        num_divisors = len(divisors)
        for i in range(1, f[k][1] + 1):
            for j in range(num_divisors):
                divisors.append(divisors[j] * f[k][0] ** i)
    return sorted(divisors)

n = int(input())
a = []
for k in divisorize(n)[1:]:
    nn = n
    while True:
        if nn < k:
            break
        if nn % k == 0:
            nn = nn // k
        else:
            nn = nn % k
    if nn == 1:
        a.append(k)
s = divisorize(n - 1)
print(len(list(set(a + s))[1:]))

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)

    # divisors.sort()
    return divisors


# 割り算をしない場合
ans1 = len(make_divisors(N-1)[1:])

# 割り算をする場合
ans2 = make_divisors(N)[1:]
ans3 = []
for i in ans2:
    Nt = N

    if Nt // i == 1:
        ans3.append(i)
        continue

    while True:
        if Nt % i == 0:
            Nt = Nt // i
        else:
            break

    if Nt % i == 1:
        ans3.append(i)

print(ans1 + len(ans3))

Submission status: Accepted

Solution code:
def make_divisors(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 div

N = int(input())
ans = 0
for x in make_divisors(N):
    if (x == 1):
        continue
    tmp = N
    while(tmp%x == 0):
        tmp /= x
    tmp %= x
    if tmp == 1:
        ans += 1
        
ans +=  len(make_divisors(N-1)) -1
print(ans)

Submission status: Accepted

Solution code:
import math
INT_MAX=10**18+7
MOD=10**9+7
def INPUT():return list(int(i) for i in input().split())
def LIST_1D_ARRAY(n):return [0 for _ in range(n)]
def LIST_2D_ARRAY(m,n):return [[0 for _ in range(n)]for _ in range(m)]
#################################################################################
n=int(input())
def calc(x,n):
    while(n%x==0):
        n//=x
    if n%x==1:
        return True
    else:
        return False

def factors(n):
    A=[]
    i=1
    while(i<=math.sqrt(n)):
        if n%i==0:
            if (n//i)==i:
                A.append(i)
            else:
                A.append(i)
                A.append(n//i)
        i+=1
    return A
x=len(factors(n-1))-1
#print(x)
A=factors(n)
A.sort()
#print(A)
for i in range(1,len(A)):
    if calc(A[i],n) is True:
        x+=1
print(x)

Submission status: Accepted

Solution code:
#!python3

# input
N = int(input())


def prime_factor(x):
    m = {}
    i = 2
    while i ** 2 <= x:
        while x % i == 0:
            if i in m:
                m[i] += 1
            else:
                m[i] = 1
            x //= i
        i += 1
    if x != 1:
        m[x] = 1
    return m


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


def main():
    m = prime_factor(N - 1)
    ans = 1
    for v in m.values():
        ans *= v + 1
    
    l = make_divisors(N)
    for x in l:
        y = N // x
        while y % x == 0:
            y //= x
        if y % x == 1:
            ans += 1
    
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def check(i):
	tot=k
	while(tot%i==0):
		tot//=i
	if(tot%i==1):
		setl.add(i)
import math
k=int(input())
if(k==2):
	print(1)
	exit()
setl = set()
setl.add(k); setl.add(k-1)
for x in range(2,int(math.sqrt(k))+1):
	check(x)
	check(k//x)
print(len(setl))

Submission status: Accepted

Solution code:
N = int(input())
ans = 0

L = [0]*(int((N-1)**(1/2))+1)

for i in range(1,int((N-1)**(1/2))+1):
    if (N-1)%i == 0:
        ans += 2
        L[i] = 1
        ###
        #print(i,(N-1)//i)
        ###
    if i**2 == N-1:
        ans -= 1

for i in range(1,int(N**(1/2))+1):
    if i < int((N-1)**(1/2))+1 and L[i] == 1:
        continue
    if N%i == 0:
        NN = N
        while NN % i == 0:
            NN //= i
        if NN % i == 1:
            ans += 1
            #print(i)
        if i**2 == N:
            continue
        NN = N
        j = N//i
        while NN % j == 0:
            NN //= j
        if NN % j == 1:
            ans += 1
            #print(j)

print(ans)
###1が前半部分で数えられるので, 引く必要があるが, ここで1を数えたことで
###後半でN自身がカウントされていないので+-0

Submission status: Accepted

Solution code:
def devisor(n):
    cnt=0
    d=[]
    for i in range(1,round(n**0.5)+1):
        if n%i==0:
            cnt+=1
            d.append(i)
            if n//i!=i:
                cnt+=1
                d.append(n//i)
    return cnt,d

N=int(input())
ans=devisor(N-1)[0]-1

D=devisor(N)[1]

for d in D:
    if d==1:
        continue
    n=N
    while n%d==0:
        n=n//d
    if n%d==1:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
def waru(n,k):
    while(n >= k):
        if(n%k == 0):
            n //= k
        else:
            n %= k
    if(n == 1):
        return 1
    else:
        return 0
n = int(input())
p = 0
if(n < 100):
    for i in range(2,n+1):
        p += waru(n,i)
    print(p)
else:
    for i in range(2,int(n**0.5)+1):
        if(n%i == 1):
            p += 1
        p += waru(n,i)
    if(int((n-1)**0.5)**2 == n-1):
        p -= 1
    print(p+2)

Submission status: Accepted

Solution code:
def check(i):
	tot=k
	while(tot%i==0):
		tot//=i
	if(tot%i==1):
		setl.add(i)
import math
k=int(input())
setl = set()
setl.add(k); setl.add(k-1)
for x in range(2,int(math.sqrt(k))+1):
	check(x)
	check(k//x)
if(setl.__contains__(1)):
	setl.remove(1)
print(len(setl))

Submission status: Accepted

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


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


def factor(n):
    ret = {}
    p = 2
    root_n = int(n**0.5)
    while n > 1:
        if n % p == 0:
            n //= p
            ret[p] = ret.get(p, 0) + 1
        elif p <= root_n:
            p += 1
        else:
            p = n
    return ret


def gcd(a, b):
    # greatest common divisor
    while b > 0:
        a, b = b, a % b

    return a


def backtrack(pn_list, k=1):
    if (not pn_list) and k != 1 and k != N:
        factor_N.append(k)
    elif pn_list:
        # print(pn_list, k)
        p, v = pn_list[0]
        pn_list = pn_list[1:]
        # print(pn_list)
        for i in range(v + 1):
            backtrack(pn_list, k * (p**i))


def check(k):
    t = N
    while t % k == 0:
        t //= k
    return t % k == 1


factor_N = []


def solve():
    pn = factor(N)
    ans = 0
    a = 1
    for v in pn.values():
        a = gcd(a, v)
    for v in factor(a).values():
        a *= v + 1
    ans += a

    a = 1
    for v in factor(N - 1).values():
        a *= v + 1
    ans += a - 1

    pn_list = list(pn.items())
    # print(pn_list)
    backtrack(pn_list)
    for k in factor_N:
        if check(k):
            ans += 1

    return ans


N = int(input())

print(solve())

Submission status: Accepted

Solution code:
###草

import math

N = int(input())

Klist = [0]*(int(N**(1/2))+1)
count = 1###int(N**(1/2))+1以上についてカウント
###あらかじめK=Nはカウント

for i in range(1,int((N-1)**(1/2))+1):
    if (N-1) % i == 0:
        Klist[i] = 1
        count += 1
        ###
        #print(i,(N-1)//i)
        ###

if  (N-1)**(1/2) - int((N-1)**(1/2)) < 1e-10 or 1 + int((N-1)**(1/2)) - ((N-1)**(1/2)) < 1e-10:
    count -= 1

M = int(math.log2(N))

for m in range(1,M+1):
    if m >= 2 and (N**(1/m) - int(N**(1/m)) < 1e-10 or 1+int(N**(1/m))-N**(1/m) < 1e-10):###m=1のときはK=Nの話なのでpass
        Klist[round(N**(1/m))] = 1
    for K in range(2,int(N**(1/(m+1))+1)):
        if (N-K**m)%(K**(m+1)) == 0:
            Klist[K] = 1
###
#print("count",count)
#print(Klist[:100])
###
print(sum(Klist)+count-Klist[1])

Submission status: Accepted

Solution code:
N = int(input())
cnt = 2 if N > 2 else 1

ret = []
for i in range(2, int(N**0.5)+1):
    if N % i == 0:
        k = N//i
        while k % i == 0:
            k //= i
        if k % i == 1:
            cnt += 1

        if N // i != i:
            j = N // i
            k = i
            while k % j == 0:
                k //= j
            if k % j == 1:
                cnt += 1

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

print(cnt)

Submission status: Accepted

Solution code:
def yakusu(N):
    if N == 1:
        return []
        
    fin = int(N**0.5)

    num = list()
    for i in range(2, fin+1):
        if N % i == 0:
            num.append(i)
            if N != i**2:
                num.append(N//i)
    num.append(N)
    
    return num


N = int(input())


#N-1の約数の個数(から1を除く)
ans = len(yakusu(N-1))


#Nの約数の内、条件を満たすもの
arr = yakusu(N)
for i in range(len(arr)):
    tmp = N
    while tmp % arr[i] == 0:
        tmp //= arr[i]
    
    if tmp % arr[i] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import copy


def solve(N: int):
    divs = make_divisors(N)
    arr = []
    for div in divs:
        if div == 1:
            continue
        n = copy.copy(N)
        while(n % div == 0):
            n //= div
        if n % div == 1:
            arr.append(div)
    cnt = len(set(arr + make_divisors(N - 1))) - 1
    print(cnt)
    return


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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

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

N0 = int(input())
ans = 0

# N = K^a (bK + 1) と表現できるので K は N or N-1 の約数であることが必要
K_cand = set(make_divisors(N0) + make_divisors(N0-1))

for K in K_cand:
    N = N0
    if K == 1:  # K = 1 を除外
        continue
    else:
        while N%K == 0:
            N = N // K  # 割れるだけ割る
        N = N%K  # 引けるだけ引く
        if N == 1:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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
ans = 0
if n-1 >= 2:
    ans += count(n-1)
ans += count2(n)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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)

Submission status: Accepted

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

# N = K^a (bK + 1) と表現できるので K は N or N-1 の約数であることが必要
K_cand = set(make_divisors(N0) + make_divisors(N0-1))

for K in K_cand:
    N = deepcopy(N0)
    if K == 1:  # K = 1 を除外
        continue
    else:
        while N%K == 0:
            N = N // K  # 割れるだけ割る
        N = N%K  # 引けるだけ引く
        if N == 1:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
if n == 2:
    print(1)
    exit()
ans = []
divisors = []
for i in range(2,int(n**0.5)+1):
    #n-1の約数は全部
    if (n-1) % i == 0:
        ans.append(i)
        if i != (n-1) // i:
            ans.append((n-1)//i)
    #nの約数はやってみる
    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(divisors)
#print(ans)
print(len(ans)+2)#k=n,n-1がはいっていないので+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))

#[2, 3, 4, 5, 10, 20, 157, 314, 628, 785, 1570, 3140, 3141]
'''

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def ord(N,n):#N,nは正の整数、Nで割り切れる回数、許容はN^1000
    if n%N!=0:
        return 0
    else:
        return 1+ord(N,n//N)

def partions(M):#Mの約数列 O(n^(0.5+e))
    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)

Submission status: Accepted

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