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

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

    for j in range(2,int(N**0.5)+1):
        if N%j == 0:
            n = N
            while n%j == 0:
                n = n//j
            if n%j == 1:
                count += 1
            if N//j != j:
                n = N
                while n%(N//j) == 0:
                    n = n//(N//j)
                if n%(N//j) == 1:
                    count += 1
    print(count+2)

Submission status: Accepted

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

n=int(input())
ans=set([])
for k in divisors(n):
    if k==1:continue
    N=n
    while  N%k==0:
        N//=k
    N%=k
    if N==1:
        ans.add(k)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def divisor(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 = I()

l = divisor(N)
l = list(set(l))

cnt = 0
for x in l:
  if x == 1:
    continue
  num = N
  while num%x == 0:
    num //= x
  if num%x == 1:
    cnt += 1

l = []

k = divisor(N-1)
cnt += len(k) - 1
print(cnt)

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())
a=make_divisors(n)[1:]
ans=0
for i in a:
    k=n
    while k%i==0:
        k//=i
    if k%i==1:
        ans+=1
ans+=len(make_divisors(n-1))-1
print(ans)

Submission status: Accepted

Solution code:
import sys
def solve():
    input = sys.stdin.readline
    N = int(input())
    if N == 2: print(1)
    else:
        K = {N, N-1}
        for i in range(2, N + 1):
            if i ** 2 > N: break
            if N % i == 0:
                k = N
                while k % i == 0:
                    k //= i
                if k % i == 1: K |= {i}
            
            if (N - 1) % i == 0:
                K |= {i}
                if i ** 2 != N - 1: K |= {(N - 1) // i}
        print(len(K))
        #print(K)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from copy import copy

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())
cand = set(make_divisors(N0) + make_divisors(N0-1))

ans = 0
for K in cand:
    if K == 1:
        continue
    N = copy(N0)
    while N%K == 0:
        N //= K
    N %= K
    if N == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())

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

    # divisors.sort()
    return divisors
a = make_divisors(N)
b = make_divisors(N - 1)
s = set(a + b)
res = 0
for x in s:
  if x == 1: continue
  t = N + 0
  while t % x == 0: t //= x
  res += (t % x == 1)
print(res)

Submission status: Accepted

Solution code:
N = int(input())

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

# 約数の全列挙
def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort(reverse=True)  # ソート
    return divisors

div1 = divisors(N)
div2 = divisors(N - 1)

ans = len([0 for d in div1 if d != 1 and isOk(d)]) + len([0 for d in div2 if d != 1 and isOk(d)])
print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())

def enumerate_divisors(N):
  all_divisors = set()
  for divisor in range(1, int(math.sqrt(N)) + 1):
    if N%divisor == 0:
      if divisor == 1:
        all_divisors.add(N/divisor)
      else:
        all_divisors = all_divisors | {divisor, N/divisor}

  all_divisors = list(all_divisors)
  return all_divisors

def calculate_reminder(N, d):
  while True:
    reminder = N%d
    if reminder == 0:
      N /= d
    else:
      return reminder

if N == 2:
  counter = 1
else:
  counter = len(enumerate_divisors(N-1))
  for div in enumerate_divisors(N):
    if calculate_reminder(N, div) == 1:
      counter += 1

print(counter)

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

d1 = make_divisors(n)
d2 = make_divisors(n-1)

ans = 0
for k in d1:
    if k == 1:
        continue
    temp = n
    while temp%k == 0:
        temp //= k
    if temp%k == 1:
        ans += 1
ans += len(d2)-1
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
def div(n):
    s = set()
    for i in range(1, int(sqrt(n))+2):
        if n%i == 0:
            s.add(i)
            s.add(n//i)
    return s

def solve(x, n):
    while n % x == 0:
        n //= x
    if n % x == 1:
        return True
    return False

def main():
    n = int(input())
    t = div(n) | div(n-1)
    ans = 0
    for v in t:
        if v != 1 and solve(v, n):
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#  not resolved
n_ori =int(input())
n_dif = n_ori - 1
sq_ori = int(n_ori**.5)
sq_dif = int(n_dif**.5)
divisor_ori = []
divisor_dif = []

for i in range(1, sq_ori+1):
	if n_ori % i == 0:
		divisor_ori.append(i)
		if i != n_ori // i:
			divisor_ori.append(n_ori//i)

for i in range(1, sq_dif+1):
	if n_dif % i == 0:
		divisor_dif.append(i)
		if i != n_dif // i:
			divisor_dif.append(n_dif//i)
			
cnt = 0
for k in divisor_ori:
	if k == 1:
		continue
	else:
		tmp = n_ori
		while tmp % k == 0:
			tmp = tmp//k

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

print(cnt + len(divisor_dif) - 1)



# # num = n - 1
# # sq = int(num**.5)
# # if sq == 1:

# # for k in range(2, sq+1):
# # 	if k == sq and num % k == 0:
# # 		cnt += 1
# # 	elif num % k == 0:
# # 		cnt += 2
# # cnt += 1

# # sq2 = int(n ** .5)
# # for k in range(2, sq2+1):
# # 	x = n
# # 	if x % k == 0:
# # 		while x % k == 0:
# # 			x = x//k
# # 		if x % k == 1:
# # 			cnt += 1

# # cnt += 1

# # print(cnt)

Submission status: Accepted

Solution code:
def divisors(n):
    lst = []; i = 1
    while i * i <= n:
        q, r = divmod(n, i)
        if r == 0:
            lst.append(i)
            if i != q: lst.append(q)
        i += 1
    return lst

N = int(input())
ans = len(divisors(N-1)) - 1
divs = divisors(N)
for k in divs:
    if k == 1: continue
    temp = N
    while temp % k == 0: temp //= k
    if temp % k == 1: ans += 1
print(ans)

Submission status: Accepted

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

# 1以外のNの約数
divisors = []
for i in range(1, int(math.sqrt(n)) + 1):
    if n % i == 0:
        divisors.append(i)
        if i ** 2 != n:
            divisors.append(n // i)
divisors.sort()

candidates = set()
for k in divisors[1:]:
    tmp = n
    while True:
        if tmp % k != 0:
            break
        tmp = tmp // k
    if (tmp - 1) % k == 0:
        candidates.add(k)

# N-1の約数
divisors = []
for i in range(1, int(math.sqrt(n-1)) + 1):
    if (n-1) % i == 0:
        divisors.append(i)
        if i ** 2 != n-1:
            divisors.append((n-1) // i)

for k in divisors[1:]:
    candidates.add(k)

print(len(candidates))

Submission status: Accepted

Solution code:
from sys import stdin
import math

data = stdin.readline().rstrip().split()
N = int(data[0])

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

    # divisors.sort()
    return divisors

div_list = sorted(make_divisors(N))
count = 0

for i in div_list:
    if i == 1:
        continue
    tmp_N = N
    while(1):
        if tmp_N % i == 0:
            tmp_N = tmp_N // i
        else:
            r = tmp_N % i
            if r == 1:
                count += 1
            break
            

div_list_2 = sorted(make_divisors(N-1)) 
        
print(count + len(div_list_2) - 1)

Submission status: Accepted

Solution code:
import math

n = int (input())
sqr = int (math.sqrt(n))
ans = 1 # n itself

def check (x) :
    tmp = n
    while (tmp % x == 0) :
        tmp /= x
    return True if tmp % x == 1 else False

for i in range (2, sqr + 1) :
    if (n % i == 0) :
        if (check (i)) :
            ans += 1
        if (i != n / i and check (n / i)) :
            ans += 1
    
m = n - 1
if (m > sqr) :
    ans += 1 # m
    for i in range (2, sqr + 1) :
        if (m % i == 0) :
            ans += 1 
            if (i != m / i) :
                ans += 1

print (ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

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 = ni()
ans = len(make_divisors(n-1))-1
ls = make_divisors(n)[1:]

for i in ls:
    nn = n
    while nn%i == 0:
        nn = nn//i
    if nn%i == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

result = 2 # K = N - 1, N
for K in range(2, int(N ** 0.5 + 1)):
    t = N
    while t >= K and t % K == 0:
        t //= K
    if t % K == 1:
        result += 1

    if (N-1) % K == 0 and (N-1) // K > K:
        result += 1
print(result)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc161/tasks/abc161_f
def make_divisors(n: int, 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 = int(input())

# 重要な考察
# 1. N%K!=0のものは、ずっと引き続けられる。その結果1になりたいんだからN%K==1の条件を満たすKは答えの候補である(しかも必ず条件を満たす)。
# 2. N%K==0のものも操作ができるので答えの候補である。(ただし条件を満たさない可能性はある)
# 1の候補は(N-1)の約数、2の候補はNの約数なので、O(√N)で探索が可能

# 具体的にはすべての候補のkに対して、割り切れなくなるまでN//=k。N%k==1ならば、答えに加算する。


# 確実にカウントできる1から
ans = len(make_divisors(N - 1)) - 1  # 1は答えに入らない

# 2の方をカウント
candi = make_divisors(N)[1:]  # 1は考えないでおく
for k in candi:
    n = N
    while n % k == 0:
        n //= k
    if n % k == 1:
        ans += 1
print(ans)

Submission status: Accepted

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

n = int(input())
s = decomposition(n)
t = decomposition(n-1)
ans = 0
for num in s:
    if num==1:
        continue
    tmp = n
    while tmp%num==0:
        tmp = tmp//num
    if tmp%num==1:
        ans += 1
print(ans+len(t)-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)
    return(divisors)

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

for i in l1:
    m=N
    while m%i==0 and m!=1 and m!=0 and i!=1:
        m//=i
    if m%i==1:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
sqrt_N = int(N ** 0.5)

dividers_for_N = []
ans_list = []

for i in range(1, sqrt_N + 1):
    if (N - 1) % i == 0:
        ans_list.append(i)
        if i != (N - 1) // i:
            ans_list.append((N - 1) // i)

    if N % i == 0:
        dividers_for_N.append(i)
        if i != N // i:
            dividers_for_N.append(N // i)

dividers_for_N.remove(1)
ans_list.remove(1)
        
for i in dividers_for_N:
    num = N
    while num % i == 0:
        num //= i
    if num % i == 1:
        ans_list.append(i)

ans = len(ans_list)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
sqrt_N = int(N ** 0.5)

dividers_for_N = set()
ans_set = set()

for i in range(1, sqrt_N + 1):
    if (N - 1) % i == 0:
        ans_set.add(i)
        ans_set.add((N - 1) // i)

    if N % i == 0:
        dividers_for_N.add(i)
        dividers_for_N.add(N // i)

dividers_for_N -= {1}
ans_set -= {1}

for i in dividers_for_N:
    num = N
    while num % i == 0:
        num //= i
    if num % i == 1:
        ans_set.add(i)

ans = len(ans_set)

print(ans)

Submission status: Accepted

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))
def prime_decomposition(n):
    i = 2
    table = []
    while i*i <= n:
        while n%i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table
def prime_decomposition2(n):
    i = 2
    table = defaultdict(int)
    while i*i <= n:
        while n%i == 0:
            n //= i
            table[i] += 1
        i += 1
    if n > 1:
        table[n] += 1
    return table
def make_divisor(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())
list_pd1 = make_divisor(N)
list_pd1.sort()
dict_pd2 = prime_decomposition2(N-1)
#print(N, ':', list_pd1)
#print(N-1, ':', dict_pd2)

cnt = 1

# -1 nohou
for val in dict_pd2.values():
    cnt *= (val+1)
cnt -= 1
#print(cnt)

for k in list_pd1[1:]:
    #print('k:', k)
    sN = N
    while sN >= k:
        if sN%k==0:
            sN //= k
        else:
            sN %= k
    if sN == 1:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
nn = 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 = len(make_divisors(nn-1)) - 1
lis = make_divisors(nn)
del lis[0]

for i in lis:
  t = nn
  while t%i==0 and t != 0:
    t = t//i
  if t%i == 1:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
def make_divisors(n):
    mod0 = set()
    mod1 = set()
    for i in range(2, int(n**0.5)+1):
        if n%i==0:
            mod0.add(i)
            mod0.add(n/i)
        if (n-1)%i==0:
            mod1.add(i)
            mod1.add((n-1)/i)
    return mod0,mod1

N=list(map(int,(stdin.readline().strip().split())))

num=N[0]
if num==2:print(1)
else:
    K=0
    mod0,mod1=(make_divisors(num))
    # mod0.remove(1)
    # mod1.remove(1)
    for i in mod0:
        num = N[0]
        while(num % i == 0):
            num/=i

        if num%i==1:
            K+=1
    K+=len(mod1)+2
    print(K)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

from collections import Counter


def factorial(n):
    prime_count = Counter()

    for i in range(2, int(n**0.5) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def num_divisors(prime_count):
    num = 1

    for prime, count in prime_count.items():
        num *= (count + 1)

    return num


def divisors(n):
    ret = set()
    for i in range(1, int(n ** 0.5) + 1):
        d, m = divmod(n, i)
        if m == 0:
            ret.add(i)
            ret.add(d)
    return sorted(ret)


def solve(N: int):

    f = factorial(N-1)
    ans = num_divisors(f)-1

    divs = divisors(N)
    for k in divs:
        if k == 1:
            continue
        n = N
        while n % k == 0:
            n = n//k
            if n == 1:
                break
        if n % k == 1:
            ans += 1
    print(ans)

    return


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 divisor(N:int):
    res = set()
    i = 1
    while i * i <= N:
        if N % i == 0:
            res.add(i)
            if i != N // i:
                res.add(N // i)
        i += 1
    return res

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

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

    ans = set()
    for K in divisor(N):
        if K == 1: continue
        if check(N, K):
            ans.add(K)

    ans |= divisor(N - 1)

    ans.remove(1)

    print(len(ans))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def divisor(N:int):
    res = set()
    i = 1
    while i * i <= N:
        if N % i == 0:
            res.add(i)
            if i != N // i:
                res.add(N // i)
        i += 1
    return res

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

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

    ans = set()
    for K in divisor(N):
        if K == 1: continue
        if check(N, K):
            ans.add(K)

    ans |= divisor(N - 1)

    ans.remove(1)

    print(len(ans))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
def make_divisors(n):
    mod0 = set()
    mod1 = set()
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            mod0.add(i)
            mod0.add(n/i)
        if (n-1)%i==0:
            mod1.add(i)
            mod1.add((n-1)/i)

    return mod0,mod1

N=list(map(int,(stdin.readline().strip().split())))
num=N[0]
K=0
mod0,mod1=(make_divisors(num))
mod0.remove(1)
mod1.remove(1)
for i in mod0:
    num = N[0]
    while(num % i == 0):
        num/=i

    if num%i==1:
        K+=1
K+=len(mod1)
print(K)

Submission status: Accepted

Solution code:
from sys import stdin
def make_divisors(n):
    mod0 = set()
    mod1 = set()
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            mod0.add(i)
            mod0.add(n/i)
        if (n-1)%i==0:
            mod1.add(i)
            mod1.add((n-1)/i)

    return mod0,mod1

N=list(map(int,(stdin.readline().strip().split())))
num=N[0]
K=0
mod0,mod1=(make_divisors(num))
mod0.remove(1)
mod1.remove(1)
for i in mod0:
    num = N[0]
    while(num % i == 0):
        num//=i

    if num%i==1:
        K+=1
K+=len(mod1)
print(K)

Submission status: Accepted

Solution code:
from sys import stdin
def make_divisors(n):
    mod0 = set()
    mod1 = set()
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            mod0.add(i)
            mod0.add(n//i)
        if (n-1)%i==0:
            mod1.add(i)
            mod1.add((n-1)//i)
    return mod0,mod1

N=list(map(int,(stdin.readline().strip().split())))
num=N[0]
K=0
mod0,mod1=(make_divisors(num))
mod0.remove(1)
mod1.remove(1)
for i in mod0:
    num = N[0]
    while(num % i == 0):
        num//=i

    if num%i==1:
        K+=1
K+=len(mod1)
print(K)

Submission status: Accepted

Solution code:
# input
N = int(input())

# 約数
def getDivs(n):
    divs = [n]
    for i in range(2, n):
        if i * i > n:
            break
        if n % i == 0:
            divs.append(i)
            if i != n//i:
                divs.append(n//i)
    return divs

# process
if N == 2:
    print(1)
else:
    pf1 = getDivs(N)
    pf2 = getDivs(N-1)
    cnt = len(pf2)

    for x in pf1:
        n = N
        while n%x == 0:
            n //= x
        n %= x 
        
        if n == 1:
            cnt += 1

    # print(pf1)
    # print(pf2)
    print(cnt)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

ans = 0

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


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

div_N = divisor(N)

for num in div_N:
    tmp = N
    while tmp % num == 0:
        tmp //= num
    if tmp == 1:
        ans += 1
        continue    
    if (tmp-1) % num == 0:
        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[1:]

n = int(input())

a = make_divisors(n-1)

b = make_divisors(n)
count = 0

for kk in b:
    mom = n
    while mom % kk == 0:
        mom //= kk
    if mom % kk == 1:
        count +=1

print(len(a) + count)

Submission status: Accepted

Solution code:
import math
def divs(n):
    res = []
    for i in range(1, n+1):
        if i * i > n:
            break
        if n % i == 0:
            res.append(i)
            if i != n//i:
                res.append(n//i)
    return res

def one(n, k):
    if k == 1:
        return False
    while n % k == 0:
        n //= k
    n %= k
    return n == 1


n = int(input())

ans = sorted(set(divs(n) + divs(n-1)))

ok = 0
for x in ans:
    if one(n, x):
        ok += 1

print(ok)

Submission status: Accepted

Solution code:
import math


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

d2 = make_divisors(n - 1)
ans = len(d2)

for k in make_divisors(n):
    if k == 1:
        continue
    tmp = n
    while tmp % k == 0:
        tmp //= k

    if tmp % k == 1:
        d2.append(k)

print(len(d2) - 1)

Submission status: Accepted

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


n=int(input())
#n%k!=0
cnt=len(make_divisors(n-1))-1

#n%k==0
lst=make_divisors(n)
for k in lst:
	if k!=1:
		t=n
		while t%k==0:
			t//=k
		if (t-1)%k==0:
			cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N=input()

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

#整数N-1の約数は全て答えにカウントして良い
ans=set(make_divisors(N-1))
wrong_ans=set(make_divisors(N-1))

K=make_divisors(N)  #Nの約数の集合
#整数Nの約数について条件にマッチングするかを1つ1つ調べる
for k in K:
    if k==1: continue
    n=N
    while n%k==0:
        n/=k
    else:
        if n==1 or n%k==1:
            ans.add(k)
print len(ans)-1

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N=input()

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

#整数N-1の約数は全て答えにカウントして良い
ans=set(make_divisors(N-1))
wrong_ans=set(make_divisors(N-1))

K=make_divisors(N)  #Nの約数の集合
#整数Nの約数について条件にマッチングするかを1つ1つ調べる
for k in K:
    if k==1: continue
    n=N
    while n%k==0:
        n/=k
    else:
        #if n==1 or n%k==1:   #AC
        if n%k==1:
            ans.add(k)
print len(ans)-1

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N=input()

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

#整数N-1の約数は全て答えにカウントして良い
ans=set(make_divisors(N-1))

K=make_divisors(N)  #Nの約数の集合
#整数Nの約数について条件にマッチングするかを1つ1つ調べる
for k in K:
    if k==1: continue
    n=N
    while n%k==0:
        n/=k
    else:
        #print "n,k :: ",n,k
        if n%k==1:
        #if n==1 or n%k==1:
            ans.add(k)
print len(ans)-1

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N=input()

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

#整数N-1の約数は全て答えにカウントして良い
ans=set(make_divisors(N-1))

K=make_divisors(N)  #Nの約数の集合
#整数Nの約数について条件にマッチングするかを1つ1つ調べる
for k in K:
    if k==1: continue
    n=N
    while n%k==0:
        n/=k
    else:
        if n==1 or n%k==1:
            ans.add(k)
print len(ans)-1

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

sys.setrecursionlimit(10 ** 6)

input_line = input()
inputs = input_line.split(' ')
N, = [int(s) for s in inputs]

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

num = len(make_divisors(N-1))-1

divisors = make_divisors(N)[1:]
for d in divisors:
    t = N
    while t%d==0:
        t = t // d
    if t%d==1:
        num += 1

print(num)

Submission status: Accepted

Solution code:
N=int(input())

def cf(n):
  a=[]
  f=1
  while f*f<=n:
    if n%f==0:
      a.append(f)
      if n//f!=f:
        a.append(n//f)
    f+=1
  return a

def main():
  c=len(cf(N-1))-1
  for f in cf(N):
    t=N
    if f!=1:
      while t%f==0:
        t//=f
      if t%f==1:
        c+=1
  print(c)

main()

Submission status: Accepted

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


n = int(input())

ans = 0

for k in enumDivisor(n):
    if k == 1:
        continue
    tmp = n
    while tmp % k == 0:
        tmp //= k
    tmp %= k
    if tmp == 1:
        ans += 1

ans += len(enumDivisor(n - 1)) - 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
if n == 2:
  print(1)
  quit()
elif n == 3:
  print(2)
  quit()
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
ans = 1
for l in factorization(n-1):
  ans *= (l[1]+1)
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  return divisors
lst = make_divisors(n)

for i in lst:
  if i == 1 or i == n:
    continue
  m = n
  while m % i == 0:
    m = m // i
  if m % i == 1:
    ans += 1
  
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

def cf(n):
  a=[]
  for f in range(1,int(n**(1/2)+1)):
    if n%f==0:
      a.append(f)
      if n//f!=f:
        a.append(n//f)
  return a

def pf(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 sorted(a)

def main():
  c,p,t=1,N+1,1
  for f in pf(N-1):
    if p==f:
      t+=1
    else:
      c*=t
      t=2
    p=f
  c=c*t-1

  for f in cf(N):
    t=N
    if f!=1:
      while t%f==0:
        t//=f
      if t%f==1:
        c+=1
  print(c)

main()

Submission status: Accepted

Solution code:
import sys
from math import sqrt
from collections import Counter, defaultdict, deque

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


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


def main():
    n = I()

    divs1 = devisor(n)
    divs2 = devisor(n - 1)
    c = len(divs2) - 1
    for val in divs1:
        if val != 1:
            tmp = n
            while tmp % val == 0:
                tmp = tmp // val
            if tmp % val == 1:
                c += 1
    print(c)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
mod0 = set()
mod1 = set()

for i in range(1, int(n**0.5)+1):
    if n%i==0:
        mod0.add(i)
        mod0.add(n//i)
    if (n-1)%i==0:
        mod1.add(i)
        mod1.add((n-1)//i)
mod0.remove(1)
mod1.remove(1)
ans = 0
for i in mod0:
    nn = n
    while nn%i==0:
        nn//=i
    if nn%i==1:
        ans += 1
ans += len(mod1)
print(ans)

Submission status: Accepted

Solution code:
import collections
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-1の約数を数える
N = int(input())
factor = collections.Counter(prime_factorize(N-1))
K = 1
for i in list(factor.values()):
    K *= i+1
K -=1
for f in range(2, int(N**0.5)+1):
    n = N
    if n%f != 0:
        continue
    while n%f ==0:
        n//=f
    if n%f ==1 or n==1:
        K+=1
#最後は自分自身を加える。
K +=1
print(K)