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:
from collections import Counter
from functools import reduce
from itertools import product
from math import gcd
from operator import mul
from random import randrange


class PrimeFactor:
    def __init__(self):
        pass

    def is_prime(self, N):
        """ミラーラビン"""
        v = [2, 7, 61] if N < 4_759_123_141 else \
            [2, 3, 5, 7, 11, 13, 17] if N < 341_550_071_728_321 else \
            [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
        if N < 2:
            return False
        if N in v:
            return True
        d = N - 1
        s = 0
        while d % 2 == 0:
            d //= 2
            s += 1

        for a in v:
            if pow(a, d, N) != 1:
                ok = True
                for r in range(s):
                    if pow(a, d * 1 << r, N) == N - 1:
                        ok = 0
                        break
                if ok:
                    return False
        return True

    def f(self, x, n, c):
        return (x * x + c) % n

    def get_factor(self, n):
        c = randrange(1, n)
        if n % 2 == 0:
            return 2
        if self.is_prime(n):
            return n
        x = randrange(1, n)
        y, d = x, 1

        while d == 1:
            x = self.f(x, n, c)
            y = self.f(self.f(y, n, c), n, c)
            d = gcd(abs(x - y), n)
        if d == n:
            return self.get_factor(n)
        return self.get_factor(d)

    def factorization(self, N):
        """素因数分解"""
        if N == 1:
            return [1]
        arr = []
        while N > 1:
            k = self.get_factor(N)
            cnt = 0
            while N % k == 0:
                cnt += 1
                N //= k
                arr.append(k)
        return arr

    def divisors(self, N):
        """約数列挙"""
        if N == 1:
            return [1]
        c = Counter(self.factorization(N))
        mul_list = []
        for i in c:
            tmp = [1] * (c[i] + 1)
            for j in range(c[i]):
                tmp[j + 1] = tmp[j] * i
            mul_list.append(tmp)
        res = [reduce(mul, v) for v in product(*mul_list)]
        return res

    def count_divisors(self, N):
        """約数の個数"""
        if N == 1:
            return 1
        res = 1
        for i in Counter(self.factorization(N)).values():
            res *= i + 1
        return res


n = int(input())
p = PrimeFactor()
a = p.divisors(n)[1:]
ans = 0
for i in a:
    k = n
    while k % i == 0:
        k //= i
    if k % i == 1:
        ans += 1
ans += p.count_divisors(n - 1) - 1
print(ans)

Submission status: Accepted

Solution code:
# 約数の列挙
#############################################################
def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
#############################################################

N = int(input())

# Nの約数
div1 = make_divisors(N)
# N-1の約数
div2 = make_divisors(N - 1)

#　マージして、不適な1は除く
div_set = set(div1 + div2)
div_set.remove(1)
# print(div_set)

# div_setの中身をそれぞれシミュレート
# N -> N-K　を愚直にやると時間がかかる、modK == 1となるか否かで判定
ans = 0
for div in div_set:
    tmp = N
    while tmp % div == 0:
        tmp = tmp // div

    if tmp % div == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# 約数の列挙
#############################################################
def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
#############################################################

N = int(input())
div1 = make_divisors(N)
div2 = make_divisors(N - 1)
div_set = set(div1 + div2)
div_set.remove(1)
# print(div_set)
ans = 0
for div in div_set:
    tmp = N
    while tmp % div == 0:
        tmp = tmp // div

    if tmp % div == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
if N == 2:
    print(1)
    exit()
ans = 1
divisors = []
d = 2
while d*d < N:
    if N % d == 0:
        divisors.append(d)
        divisors.append(N//d)
    d += 1
if d*d == N:
    divisors.append(d)

for d in divisors:
    dummyN = N
    while dummyN % d == 0:
        dummyN //= d
    if dummyN % d == 1:
        ans += 1

N -= 1
divisors = []
d = 2
while d*d < N:
    if N % d == 0:
        divisors.append(d)
        divisors.append(N//d)
    d += 1
if d*d == N:
    divisors.append(d)

ans += len(divisors)+1
print(ans)

Submission status: Accepted

Solution code:
def divisors(n):
    i = 1
    table = set()
    while i * i <= n:
        if not n % i:
            table.add(i)
            table.add(n//i)
        i += 1
    table = list(table)
    return table
N = int(input())
k = 2
res = 0
while k*k<=N:
    n = N
    while not n%k:
        n//=k
    if (n%k==1 or n==1) and n!=N:
        res += 1
    k += 1
a = divisors(N-1)
print(len(a)+res)

Submission status: Accepted

Solution code:
n = int(input())

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# その数自身
ans = 1
# 1以外のn-1の約数
ans += len(make_divisors(n-1)) - 1

d = make_divisors(n)
for k in range(1,(len(d)+1)//2):
    i = d[k]
    j = n//i
    while j % i == 0:
        j //= i
    if j % i == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
"""
一回以上わるとき、KはNの約数なので、Nの約数を全通り試して1に持っていけるかどうかを検証する。
Nを一回も割らずに1まで持っていけるようなKは、N-1の約数の数だけ存在する。
それぞれカウントすればよい
"""
N = int(input())
ans = 0
if N == 2:
    print(1)
    exit()

divisers = [N]
d = 2
while d*d < N:
    if N % d == 0:
        divisers.append(d)
        divisers.append(N//d)
    d += 1
if d**2 == N:
    divisers.append(d)

for d in divisers:
    dummyN = N
    while dummyN%d == 0:
        dummyN //= d
    if dummyN % d == 1:
        ans += 1

N -= 1
divisers = [N]
d = 2
while d*d < N:
    if N % d == 0:
        divisers.append(d)
        divisers.append(N//d)
    d += 1
if d**2 == N:
    divisers.append(d)

ans += len(divisers)

print(ans)

Submission status: Accepted

Solution code:
import math
import sys
N = int(input())
if N == 2:
  print(1)
  sys.exit()

def get_divisors(x):
  lim = math.ceil(math.sqrt(x))
  divisors = set()
  for i in range(1,lim+1):
    if x % i == 0:
      divisors.add(i)
      divisors.add(N//i)    
  return divisors
    
ans_1 = 0
#約数について
divisors = get_divisors(N)
for d in divisors:
  if d == 1: continue
  N_try = N
  while N_try % d == 0:
    N_try //= d
  if N_try % d == 1:
    ans_1 += 1
    
#約数でない数について
divisors = get_divisors(N-1)
ans_2 = len(divisors)-1
    
#print(ans_1, ans_2)
print(ans_1+ans_2)

Submission status: Accepted

Solution code:
n=int(input())

def f(x):
  m=int(x**(1/2))
  ret=set()
  for i in range(1,m+1):
    if x%i==0:
      ret.add(i)
      ret.add(x//i)
  return ret


ans=set()
for i in f(n):
  if i==1:
    continue
  g=n
  while g%i==0:
    g=g//i
  if g%i==1:
    ans.add(i)

for j in f(n-1):
  if j==1:
    continue
  if j in ans:
    continue
  ans.add(j)
  
print(len(ans))

Submission status: Accepted

Solution code:
"""
Nが1になるようなKは、
・K^x = NになるようなKか
・K^x(K*y+1) = N になるようなKである。
後者は前者を包括するので、後者についてのみカウントすればよい。
Kの数を求めるために、後者をさらに2種類に分ける
・x > 0の場合
・x == 0の場合
前者の場合、KはNの約数なので、Nの約数全部に関して条件を満たすか調べればよい。Nの約数はそんなに多くならないので、時間はかからない。
後者の場合だと、KはN-1の約数の数だけ存在するのでN-1の約数の数を求めればよい。
"""
from collections import Counter

def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

N = int(input())
ans = 0
#x>0の場合を調べる
#Nを素因数分解する
devisers = []
d = 2
while d*d < N:
    if N % d == 0:
        devisers.append(d)
        devisers.append(N//d)
    d += 1
if d*d == N:
    devisers.append(d)

for d in devisers:
    dummyN = N
    while dummyN % d == 0:
        dummyN //= d
    if dummyN%d == 1:
        ans += 1


#x == 0 になるようなKの数を調べる。
#N-1を素因数分解する。
tmp = []
dummyN = N-1
ceil = int(dummyN**0.5)
for d in range(2,ceil+1):
    while dummyN % d == 0:
        tmp.append(d)
        dummyN //= d
if dummyN != 1:
    tmp.append(dummyN)
    dummyN //= dummyN

divideN = Counter(tmp)
commonDCnt = 1
for v in divideN.values():
    commonDCnt *= (v+1)
ans += commonDCnt

print(ans)

Submission status: Accepted

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

def divisor(num):
    max_num = int(sqrt(num))
    divisor_list = []
    for i in range(1, max_num + 1):
        if num % i == 0:
            divisor_list.append(i)
            divisor_list.append(num//i)
    return divisor_list

K0 = divisor(N)
K1 = divisor(N-1)
S = set(K1)
S.remove(1)
for k in K0:
    tmp = N
    if k == 1:
        continue
    while tmp % k == 0 and tmp >= k:
        tmp //= k
    if tmp % k == 1:
        S.add(k)
print(len(S))

Submission status: Accepted

Solution code:
import sys

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


# 約数列挙 0(√N)
def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def main():
    N = in_n()

    yaku = make_divisors(N)
    yaku.remove(1)

    ans = 0
    for x in yaku:
        tn = N
        while tn % x == 0:
            tn /= x
        if tn % x == 1:
            ans += 1

    yaku = make_divisors(N - 1)
    yaku.remove(1)
    ans += len(yaku)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def divisors(n,TF):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if TF == 1:
                if i != n // i:
                    divisors.append(n//i)
    return divisors
N = int(input())
if N == 2:
    print(1)
    sys.exit()

ans = len(divisors(N - 1, 1)) + 2
A = divisors(N, 0)
for i in A:
    x = N
    while x % i == 0:
        x //= i
    if x % i == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    ans = 2-(n==2)
    for k in range(2,int(n**0.5)+1):
        if n % k == 1:
            ans += 2
            ans -=k**2+1==n
        elif n % k == 0:
            g = n//k
            while g % k == 0:
                g = g//k
            ans += g % k == 1
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def make_divisors(n: int):
    lower_divs = []
    upper_divs = []
    i = 1
    while i**2 <= n:
        if n % i == 0:
            lower_divs.append(i)
            if i != n // i:
                upper_divs.append(n // i)
        i += 1
    return lower_divs + upper_divs[::-1]


n = int(input())
ans = len(make_divisors(n - 1)) - 1
for x in make_divisors(n)[1:]:
    if x == 1:
        continue
    z = n
    while z % x == 0:
        z = z // x
    z = z % x
    if z == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N = I()
B = make_divisors(N - 1)
b = len(B)

A = make_divisors(N)

cnt = 0
for i in range(1, len(A) // 2 + 1):
    x = A[i]
    y = A[-i - 1]
    while y > x:
        if (y - 1) % x == 0:
            cnt += 1
            break
        elif y % x == 0:
            y //= x
        else:
            break
    if y == x:
        cnt += 1

ans = b - 1 + cnt + 1
print(ans)

Submission status: Accepted

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()

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

        return res

    ans = 0
    ans += len(divisors(N-1)) - 1

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




if __name__ == "__main__":
    main()

Submission status: Accepted

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

    def enum_divisors(n):
        # 約数列挙
        divs = []
        for i in range(1, n+1):
            if i*i > n:
                break
            if n % i == 0:
                divs.append(i)
                if n//i != i:
                    # i が平方数でない
                    divs.append(n//i)
        return divs

    ans = 0
    for k in enum_divisors(N-1):
        if 2 <= k:
            ans += 1

    for k in enum_divisors(N):
        if 2 <= k:
            n = N
            while n > 1 and n % k == 0:
                n //= k
            if n % k == 1:
                ans += 1

    print(ans)


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:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

def solve(N):
    if N == 2:
        print(1)
        return
    Ans = [N, N-1]
    for base in range(2, N):
        if base * base > N:
            break
        n = N
        while n % base == 0:
            n //= base
        if n % base == 1:
            Ans.append(base)
        if (N-1) % base == 0:
            Ans.append(base)
            Ans.append((N-1)//base)
    if int(N**0.5)**2 == N:
        Ans.append(int(N**0.5))
    print(len(set(Ans)))

numba_compile([
    [solve, "void(i8)"],
])

N = int(input())
solve(N)

Submission status: Accepted

Solution code:
N = int(input())

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

ans = 0

d = []
for x in divisor(N):
  if x==1: continue
  tmp = N
  while tmp%x==0: tmp //= x
  tmp %= x
  if tmp == 1: ans += 1

ans += len(divisor(N-1)) - 1
print(ans)

Submission status: Accepted

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

N_d = []
N1_d = []
answer = set()
for i in range(1,math.ceil(N**0.5)+1):
    if N%i == 0:
        N_d.append(i)
        N_d.append(N//i)

for i in range(len(N_d)):
    temp = N
    while temp % N_d[i] == 0:
        temp = temp//N_d[i]
        if N_d[i] == 1:
            break
        
    if temp % N_d[i] == 1:
        answer.add(N_d[i])


for i in range(1,math.ceil((N-1)**0.5)+1):
    if (N-1) %i == 0:
        answer.add(i)
        answer.add((N-1)//i)

answer.remove(1)
print(len(answer))

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def ccc(v, k):
	while v >= k:
		if v % k == 0:
			v = v // k
		else:
			v = v % k
	return v

def cccc(v,k):
	while v >= k:
		if v % k == 0:
			v = v //k
		else:
			v = v-k
	return v


def main_p(n):
	s = n#int(input())
	#b , c = tin()
	#s = input()
	if s == 2:
		return 1
	elif s == 3:
		return 2
	
	ret = 1  #s-1, 1は範囲外なので。
	for i in range(2, s-1):
		if i*i > s+1:
			break
		if (s-1) % i == 0:
			ret += 1 if i*i == s-1 else 2
			
	ret += 1 #s
	for i in range(2, s):
		if i*i > s+1:
			break
			
		if s % i == 0:
			if ccc(s, i) == 1:
				ret += 1
			oi = s // i
			if oi != i and ccc(s, oi) == 1:
				ret += 1
			
	return ret#print(ret)
	
		
def main():
	n = int(input())
	return main_p(n)

def main_g(n):
	ret = 0
	for i in range(2, n+1):
		if cccc(n, i) == 1:
			ret += 1
	return ret


def maint():
	i=2
	p=0
	g=0
	while p == g:
		p=main_p(i)
		g=main_g(i)
		i+=1
		if p==g:
			print('ok', i-1)
	print(i-1,p,g)
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:

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


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

cand = sorted(calc_divisor(N))[1:]
for k in cand:
    x = N
    while x % k == 0:
        x //= k
    if x % k == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy

# 約数列挙
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 2
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1] + [n]

# 素因数分解
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


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

div1 = make_divisors(n-1)
cnt = len(div1)

div2 = make_divisors(n)


for i in div2:
    x = copy.deepcopy(n)
    while x >= i:
        if x % i == 0:
            x //= i
        else:
            break
    if x == 1 or x % i == 1:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())

if n == 2:
    print(1)
    exit()
num = n - 1
cnt = 1
lst = [n]
for i in range(2, int(n ** 0.5) + 1):
    if num % i == 0:
        cnt += 2
        if num == i ** 2:
            cnt -= 1
    if n % i == 0:
        lst.append(i)
        if n != i ** 2:
            lst.append(n // i)
for num in lst:
    n2 = n
    while n2 % num == 0:
        n2 //= num
    if n2 % num == 1:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

"""
引き算のみ
N mod K == -1
N-1 mod K == 0
K はN-1の約数

割り算が含まれる
KはNの約数
大した個数ないので、確かめる。
"""

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

A = make_divisors(N-1)
B = make_divisors(N)
ANS = set(A)
for b in B:
  if b <= 1:
    continue
  wk = N
  while wk % b == 0:
    wk = wk // b
  if wk % b == 1:
    ANS.add(b)
    
print(len(ANS)-1) # 1を除く

Submission status: Accepted

Solution code:
N = int(input())

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

S = set([N-1])
lst = [N]
i = 2
while i*i <= N-1:
  if (N-1) % i == 0:
    S.add(i)
    S.add((N-1)//i)
  i += 1  
  
i = 2
while i*i < N:
  if N % i == 0:
    lst.append(i)
    lst.append(N//i)
  i += 1
    
if i*i == N:
  lst.append(i)
  
lst.sort()

for l in lst:
  if l in S:
    continue
  _N = N
  while _N % l == 0:
    _N //= l
  if _N % l == 1:
    S.add(l)
    
print(len(S))

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


C = set(make_divisors(N) + make_divisors(N-1))
C.discard(1)


def f(x, k):
    if x % k == 0:
        return x//k
    else:
        return x % k


ans = 0
for i in C:
    x = N
    c = 0
    while x >= i:
        c += 1
        x = f(x, i)
    if x == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            # √nで無い数についてもう一個プラス
            if i != n // i:
                divisors.append(n // i)
    return sorted(divisors)

N = getN()

# 手順としては
# ①　kで出来るだけ割る
# ②　kで引いていく　N = mk + d(d = 1, 2, 3...)とすると,　引いて残る数はm(k - 1) + d
# つまりkで割り切れず、引いても引いても永遠に①に戻ることはない

# N = k ** i * (mk + 1)となるkの数を求める
# i == 0の時
# kがなんであれk ** iは１になるので
# N = mk + 1、つまりN - 1がkの倍数であればそのkは条件を満たす
# N - 1の約数（１以外）が候補

ans = set()
for i in make_divisors(N - 1):
    if i != 1:
        ans.add(i)

# 割れるだけ割る関数
def dividor(x, k):
    if k == 1:
        return 0
    n = x
    while True:
        if n % k == 0:
            n //= k
        else:
            break
    return n

# i >= 1の時
# 候補はNの約数
for prim in make_divisors(N):
    if prim == 1:
        continue
    # Nを割れるだけ割る
    alta = dividor(N, prim)
    if alta == 1:
        ans.add(prim)
        continue
    if alta >= prim and alta % prim == 1:
        ans.add(prim)

print(len(ans))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

def prime_factorize(n):
    divisors = []
    # 27(2 * 2 * 7)の7を出すためにtemp使う
    temp = n
    for i in range(2, int(math.sqrt(n)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                # 素因数を見つけるたびにtempを割っていく
                temp //= i
            divisors.append([i, cnt])
    if temp != 1:
        divisors.append([temp, 1])
    if divisors == []:
        divisors.append([n, 1])

    return divisors

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            # √nで無い数についてもう一個プラス
            if i != n // i:
                divisors.append(n // i)
    return sorted(divisors)

N = getN()

# 手順としては
# ①　kで出来るだけ割る
# ②　kで引いていく　N = mk + d(d = 1, 2, 3...)とすると,　引いて残る数はm(k - 1) + d
# つまりkで割り切れず、引いても引いても永遠に①に戻ることはない

# N = k ** i * (mk + 1)となるkの数を求める
# i == 0の時
# N - 1の約数の数 - 1(1)
ans = set()
for i in make_divisors(N - 1):
    if i != 1:
        ans.add(i)

# 割れるだけ割る関数
def dividor(x, k):
    if k == 1:
        return 0
    n = x
    while True:
        if n % k == 0:
            n //= k
        else:
            break
    return n

# i >= 1の時
for prim in make_divisors(N):
    if prim == 1:
        continue
    # Nを割れるだけ割る
    alta = dividor(N, prim)
    if alta == 1:
        ans.add(prim)
        continue
    if alta >= prim and alta % prim == 1:
        ans.add(prim)

# Nが素数でない場合はN自身が追加されない
ans.add(N)
print(len(ans))

Submission status: Accepted

Solution code:
def div(n):
    r = int(n**(1/2))
    for i in range(1, r + 1):
        if n % i == 0:
            yield i
            if i*i != n:
                yield n // i


n = int(input())
count = len(list(div(n-1)))-1
for i in div(n):
    if i > 1:
        x = n
        while x % i == 0:
            x //= i
        if x % i == 1:
            count += 1

print(count)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

sys.setrecursionlimit(1000000)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def divisors(N):
    divs = set([1, N])
    i = 2
    while i ** 2 <= N:
        if N % i == 0:
            divs.add(i)
            divs.add(N//i)
        i += 1
    return sorted(list(divs))

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

def main():
    N = I()
    ans = 0

    for divisor in divisors(N-1):
        if is_ok(N, divisor):
            ans += 1

    for divisor in divisors(N):
        if is_ok(N, divisor):
            ans += 1

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

N = int(input())


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


cand = len(calc_divisor(N - 1))
divisor_n = calc_divisor(N)
for v in divisor_n:
    x = N
    while x % v == 0:
        x //= v

    if x % v == 1:
        cand += 1

print(cand)

Submission status: Accepted

Solution code:
n = int(input())
if n==2:print(1);exit()
a = [n]
for i in range(2,int(n**0.5+1)):
    if n%i==0:
        a.append(i)
        if i!=n//i:
            a.append(n//i)
cnt =0
for v in a:
    s = n
    while v<=s and s%v==0:
        s = s//v
    if s%v==1: cnt += 1
b = [n-1]
m = n-1
for i in range(2,int(m**0.5+1)):
    if m%i==0:
        b.append(i)
        if i!=m//i:
            b.append(m//i)
print(cnt + len(b))