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

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

ans = 0

def factorization(n):
  lis = []
  if n % 2 == 0:
    c = 0
    while n%2 == 0:
      n //= 2
      c += 1
    lis.append([2, c])
  k = 3
  while k*k <= n:
    if n%k == 0:
      c = 0 
      while n%k == 0:
        n //= k
        c += 1
      lis.append([k, c])
    else:
      k += 2
  if n > 1:
    lis.append([n, 1])
  return lis

list1 = factorization(N-1)
ans1 = 1
for k in range(len(list1)):
  ans1 *= list1[k][1]+1
ans += ans1-1

def operation(K):
  n = N
  while n%K == 0:
    n //= K
  if n%K == 1:
    return True
  else:
    return False

list2 = factorization(N)
factorlist = [1]
for l in range(len(list2)):
  list3 = []
  for j in range(list2[l][1]):
    for k in range(len(factorlist)):
      list3.append(factorlist[k]*list2[l][0]**(j+1))
  factorlist += list3
factorlist = factorlist[1:-1]
ans += 1
for item in factorlist:
  if operation(item):
    ans +=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
originalN = 0 +N
if N == 2:
  print(1)
  exit()
ans = 0
"""
primenum = [2]
count = [0 for _ in range(int(N**0.5)+2)]
for k in range(3, len(count), 2):
  if count[k] == 0:
    primenum.append(k)
    for j in range(k, len(count), k):
      count[j] = 1
    
def factorization(n):
  lis = []
  k = 0
  while primenum[k] <= n:
    if n%primenum[k] == 0:
      c = 0 
      while n%primenum[k] == 0:
        n //= primenum[k]
        c += 1
      lis.append([primenum[k], c])
    else:
      k += 1
      if k > len(primenum)-1:
        break
  if n > 1:
    lis.append([n, 1])
  return lis
"""
def factorization(n):
  lis = []
  if n % 2 == 0:
    c = 0
    while n%2 == 0:
      n //= 2
      c += 1
    lis.append([2, c])
  k = 3
  while k*k <= n:
    if n%k == 0:
      c = 0 
      while n%k == 0:
        n //= k
        c += 1
      lis.append([k, c])
    else:
      k += 2
  if n > 1:
    lis.append([n, 1])
  return lis

list1 = factorization(N-1)
#print(factorization(N-1))
ans1 = 1
for k in range(len(list1)):
  ans1*= list1[k][1]+1
ans1 -= 1
ans += ans1

#print(ans1)

def operation(K):
  N = originalN
  while N%K == 0:
    N //= K
  if N%K == 1:
    return True
  else:
    return False

list2 = factorization(N)
#print(list2)
factorlist = [1]

for l in range(len(list2)):
  list3 = []
  for j in range(list2[l][1]):
    for k in range(len(factorlist)):
      list3.append(factorlist[k]*list2[l][0]**(j+1))
  factorlist += list3

factorlist = factorlist[1:-1]
#print(factorlist)
ans2 = 1
for item in factorlist:
  if operation(item):
    #print(item)
    ans2 +=1


ans += ans2
#print(ans2)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
originalN = 0 +N
if N == 2:
  print(1)
  exit()
ans = 0
primenum = [2]
count = [0 for _ in range(int(N**0.5)+2)]
for k in range(3, len(count), 2):
  if count[k] == 0:
    primenum.append(k)
    for j in range(k, len(count), k):
      count[j] = 1
    
def factorization(n):
  lis = []
  k = 0
  while primenum[k] <= n:
    if n%primenum[k] == 0:
      c = 0 
      while n%primenum[k] == 0:
        n //= primenum[k]
        c += 1
      lis.append([primenum[k], c])
    else:
      k += 1
      if k > len(primenum)-1:
        break
  if n > 1:
    lis.append([n, 1])
  return lis

list1 = factorization(N-1)
#print(factorization(N-1))
ans1 = 1
for k in range(len(list1)):
  ans1*= list1[k][1]+1
ans1 -= 1
ans += ans1

#print(ans1)

def operation(K):
  N = originalN
  while N%K == 0:
    N //= K
  if N%K == 1:
    return True
  else:
    return False

list2 = factorization(N)
#print(list2)
factorlist = [1]

for l in range(len(list2)):
  list3 = []
  for j in range(list2[l][1]):
    for k in range(len(factorlist)):
      list3.append(factorlist[k]*list2[l][0]**(j+1))
  factorlist += list3

factorlist = factorlist[1:-1]
#print(factorlist)
ans2 = 1
for item in factorlist:
  if operation(item):
    #print(item)
    ans2 +=1


ans += ans2
#print(ans2)

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    lower.extend(reversed(upper))
    return lower


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

    D = divisors(N)
    D1 = divisors(N - 1)
    ans = len(D1) - 1

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    lower.extend(reversed(upper))
    return lower


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

    D = divisors(N)
    D1 = divisors(N - 1)
    ans = len(D1) - 1

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    lower.extend(reversed(upper))
    return lower


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

    D = divisors(N)
    D1 = divisors(N - 1)
    ans = len(D1) - 1

    for d in D[1:]:
        n = N
        while n % d == 0:
            n //= d
            if (n - 1) % d == 0:
                ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd

def is_prime_miller_rabin(n):  # ミラー-ラビン素数判定法
    if n < 2:
        return False
    elif n in {2, 3, 5, 7, 11}:
        return True
    elif n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 or n % 11 == 0:
        return False

    if n < 4_759_123_141:
        witnesses = [2, 7, 61]
    elif n < 341_550_071_728_321:
        witnesses = [2, 3, 5, 7, 11, 13, 17]
    else:
        witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]

    d = n - 1
    d = d // (d & -d)

    for a in witnesses:
        y = pow(a, d, n)
        if y == 1:
            continue
        t = d
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1:
                return False
            t <<= 1
    return True

def find_factor_rho(n):  # ポラード・ロー素因数分解法
    if n < 2:
        return None
    m = 1<<n.bit_length() // 8 + 1
    for c in range(1, 99):
        def f(x):
            return (x * x + c) % n

        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if is_prime_miller_rabin(g):
                return g
            elif is_prime_miller_rabin(n // g):
                return n // g
    return None

def prime_factorize_dict(n):
    prime_dict = defaultdict(int)
    i = 2
    while i * i <= n:
        while n % i == 0:
            n //= i
            prime_dict[i] += 1
        i += 1 + i % 2
        if i != 101 or n < 1<<20:
            continue
        while n > 1:
            if is_prime_miller_rabin(n):
                prime_dict[n] = n = 1
                break
            j = find_factor_rho(n)
            while n % j == 0:
                n //= j
                prime_dict[j] += 1
    if n > 1:
        prime_dict[n] += 1
    return prime_dict

# ---------------------- #

n = int(input())
ans = 1
for value in prime_factorize_dict(n - 1).values():
    ans *= value + 1
ans -= 1  # 1を除くn-1の約数の数

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

for divisor in get_divisors(n)[1:]:
    tmp = n
    while tmp % divisor == 0:
        tmp //= divisor
    if tmp % divisor == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
if N == 2:
    print(1)
    exit()
ans = 0
M = int(N**0.5) + 1
for k in range(2, M):
    n = N
    while n:
        if n % k == 0:
            n //= k
        elif n % k == 1:
            ans += n != N
            break
        else:
            break


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


ans2 = 1
for _, i in factorization(N - 1):
    ans2 *= (1 + i)
ans += ans2
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    if N <= 3:
        print(N - 1)
        return
    # (1) 2 <= k <= sqrt(N) で題意を満たすkの個数
    ans_1 = 0
    k = 2
    while k ** 2 <= N:
        n = N
        while n % k == 0:
            n //= k
        n %= k
        if n == 1:
            ans_1 += 1
        k += 1
    # (2) sqrt(N) < k <= N で題意を満たすkの個数
    # sqrt(N)より大きいN-1の約数の個数 + 1 (k = N)
    ans_2 = 1
    n = 1
    while n ** 2 < N:
        if (N - 1) % n == 0 and ((N - 1) // n) ** 2 > N:
            ans_2 += 1
        n += 1
    # 答え
    print(ans_1 + ans_2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import sqrt, ceil
n = int(input())
def ans(n):
  if n == 2:
    return 1
  # divisors of n-1
  count = sum(2*int((n-1)%i==0) for i in range(2, ceil(sqrt(n-1))))
  # check the square root of n-1
  if ceil(sqrt(n-1)) == int(sqrt(n-1)):
    count += 1
  # n-1 is always a divisor of n-1
  count += 1
  # divisors of n
  for i in range(2, ceil(sqrt(n))):
    if n%i==0:
      x = n
      while x%i == 0:
        x = x//i
      count += int((x-1)%i==0)
      other_divisor = n//i
      x = n
      while x%other_divisor == 0:
        x = x//other_divisor
      count += int((x-1)%other_divisor==0)
  # check the square root of n
  if ceil(sqrt(n)) == int(sqrt(n)):
    i = int(sqrt(n))
    x = n
    while x%i == 0:
      x = x//i
    count += int((x-1)%i==0)
  # n is always a divisor of n that reduces to 1 by division once
  count += 1
  return(count)
print(ans(n))

Submission status: Accepted

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


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


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]


ns = make_divisors(n)

ans = 0
for i in ns:
    if i == 1:
        continue
    p = n
    while p % i == 0:
        p //= i
    if p % i == 1:
        ans += 1


ns = make_divisors(n - 1)
ans += len(ns) - 1
print(ans)

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

F = make_divisors(N)
count = 0
for f in F:
  n = N
  while 1:
    if n % f != 0:
      n = n % f
    else:
      n = n // f
    if n < f:
      break
  if n == 1: count += 1
print(count + len(make_divisors(N-1)))

Submission status: Accepted

Solution code:
n = int(input())
div = []
div2 = []
ans = 0
for i in range(1,10**6+1):
    if n%i == 0:
        div+=[i,n//i]
    if (n-1)%i == 0:
        div2+=[i,(n-1)//i]
div = set(div)
div2 = set(div2)
# print(div)
a = [1]
for i in div:
    if i > 1:    
        t = n
        while t:
            if t%i == 0:
                t = t//i
            else:
                if t%i == 1:
                    ans += 1
                    a += [i]
                break
# for i in div2:
#     if i > 1:    
#         t = n-1
#         while t:
#             if t == 1:
#                 ans += 1
#                 a += [i]
#             t //= i
#         # if n%(i-1) == 1:
#         #     ans += 1
#         #     a += [i-1]
# print(ans)
# print(a)
# print(div)
# print(div2)
for i in div2:
    a+=[i]
a = set(a)
# print(a)
print(len(a)-1)

Submission status: Accepted

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

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

answer_set=set()
for i in range(2,int(N**0.5)+1):
  N2=N
  while N2%i==0:
    N2//=i
  if N2%i==1:
    answer_set.add(i)
#print(answer_set)

for i in range(1,int(N**0.5)+1):
  if (N-1)%i==0:
    answer_set.add((N-1)//i)    
#print(answer_set)

answer_set.add(N)
print(len(answer_set))

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
m=int(pow(n,0.5))
s=set()
t=set()
for i in range(1,m+1):
    if n%i==0:
        s.add(i)
        s.add(n//i)
    if (n-1)%i==0:
       t.add(i)
       t.add((n-1)//i) 
ans=len(t)-1
for i in s:
    if i==1:
      continue
    c=n
    while True:
        if c%i==0:
            c=c//i
        else:
            if c%i==1:
                ans+=1
            break
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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())
ans = len(make_divisors(N-1))-1
lis = make_divisors(N)
for n in lis:
    G = N
    if n==1:
        continue
    while G%n==0:
        G //= n
    if G%n==1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())

def divisore(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_l=divisore(n-1)[1:]

d=divisore(n)
for i in d[1:]:
  nn=n
  while nn%i==0:
    nn//=i
  if nn%i==1:
    ans_l.append(i)

print(len(ans_l))

Submission status: Accepted

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

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==[]: #1の場合はここ
        arr.append([n, 1])
 
    return arr

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)
ans = 0 #自分自身の一個を足しておく
SET = set([N])
#print(A)
for i in range(1,len(A)):
  M = N*1
  while M%A[i]==0:
    M = M//A[i]
  if M%A[i] == 1:
    ans += 1
    SET.add(A[i])
#ans = len(SET)
#print(SET)
#print(ans)
N -= 1
B = factorization(N)
yakusu = 1
#print(B)
for i in range(len(B)):
  yakusu *= (B[i][1]+1)
#print(yakusu)
ans += yakusu-1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ans=set()
ans.add(n)
i=2
x = 1
while x * x <= n-1 :
  if (n-1) % x == 0:          
    ans.add(x)
    ans.add((n-1)//x)
  x += 1
while i*i<=n:
  t=n
  while t%i==0:
    t/=i
  if t%i==1:
    ans.add(i)
  i+=1
print(len(ans)-1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N = int(input())

#nの約数列挙
def divisor(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されていない

ans = len(divisor(N-1))-1
b = divisor(N)
for bi in b:
    if bi == 1:
        continue
    a = N
    while a >= bi:
        if a%bi == 0:
            a = a//bi
        else:
            a = a%bi
    if a == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

divs = set()
n = 1
while n*n <= N:
    if N%n==0:
        divs.add(n)
        divs.add(N//n)
    n += 1

divs2 = set()
n = 1
while n*n <= (N-1):
    if (N-1)%n==0:
        divs2.add(n)
        divs2.add((N-1)//n)
    n += 1

ans = len(divs2) - 1
for d in divs:
    if d==1: continue
    n = N
    while n >= 1:
        if n==1:
            ans += 1
            break
        if n%d == 0:
            n //= d
        else:
            if n%d == 1:
                ans += 1
            break

print(ans)

Submission status: Accepted

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

A=f(N)
M=0
for i in range(len(A)):
  if A[i]==1:
    continue
  M=N
  while M%A[i]==0:
    M//=A[i]
  if M%A[i]==1:
    P+=1
P+=len(f(N-1))-1
print(P)

Submission status: Accepted

Solution code:
import sys
from math import gcd

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

"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
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


factors = factorization(N)
ans = 0

# K^i
tmp = factors[0][1]
for k, i in factors:
    tmp = gcd(tmp, i)
ptn = 1
if tmp != 1:
    for k, i in factorization(tmp):
        ptn *= i+1
ans += ptn

# ak+1
ptn = 1
for k, i in factorization(N-1):
    ptn *= i+1
ptn -= 1  # k=1のときを除外
ans += ptn

# (ak+1)*k^i
ptn = 0
for f, n in factors:
    for i in range(1, n+1):
        k = f**i
        tmp = N
        while True:
            if tmp%k!=0:
                break
            tmp = tmp/k
        ptn += ((tmp-1)%k==0 and tmp!=1)
ans += ptn

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from math import gcd

N=int(input())

def factorize(x):
    i=2
    ret=[]

    while i*i<=x:
        while x%i==0:
            ret.append(i)
            x//=i
        
        i+=1
    
    if x>1:
        ret.append(x)
    
    return Counter(ret)

ans=1

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

ans-=1

cnt=1
for v in factorize(gcd(N,N-1)).values():
    cnt*=v+1
cnt-=1

ans-=cnt

k=2
while k*k<=N:
    if N%k==0:
        n=N//k
        while n%k==0:
            n//=k
        
        if n%k==1:
            ans+=1
    k+=1
ans+=1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


# MOD = int(1e09) + 7
MOD = 998244353
INF = int(1e15)


def divisor(N):
    res = []
    i = 2
    while i * i <= N:
        if N % i == 0:
            res.append(i)
            if i != N // i:
                res.append(N // i)
        i += 1
    if N != 1:
        res.append(N)
    return res


def solve():
    N = Scanner.int()
    d0 = divisor(N - 1)
    ans = len(d0)
    d1 = divisor(N)
    for d in d1:
        X = N
        while X % d == 0:
            X //= d
        if X % d == 1:
            ans += 1
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def divisor(i):
    s = []
    for j in range(1, int(i ** (1 / 2)) + 1):
        if i % j == 0:
            s.append(i // j)
            s.append(j)
    return sorted(set(s))

n = int(input())
ans = 0
d = divisor(n)
d.pop(0)
for i in d:
    x = n
    while True:
        if not x % i == 0:
            break
        x //= i
    if x % i == 1:
        ans += 1
d = divisor(n - 1)
ans += len(d)
ans -= 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# import bisect
# from collections import Counter, deque, OrderedDict, defaultdict
from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    n = int(input())

    import math

    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f

    def make_prime_list_2(num):
        if num < 2:
            return []

        # 0のものは素数じゃないとする
        prime_list = [i for i in range(num + 1)]
        prime_list[1] = 0  # 1は素数ではない
        num_sqrt = math.sqrt(num)

        for prime in prime_list:
            if prime == 0:
                continue
            if prime > num_sqrt:
                break

            for non_prime in range(2 * prime, num, prime):
                prime_list[non_prime] = 0

        return [prime for prime in prime_list if prime != 0]

    def prime_factorization_2(num):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""

        if num <= 1:
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)

            dict_counter = {}  # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452

            for prime in prime_list:
                while num % prime == 0:
                    if prime in dict_counter:
                        dict_counter[prime] += 1
                    else:
                        dict_counter[prime] = 1
                    num //= prime
            if num != 1:
                if num in dict_counter:
                    dict_counter[num] += 1
                else:
                    dict_counter[num] = 1

            return dict_counter

    def divisor_count(num):
        """numの約数の個数を求める"""
        if num < 0:
            return None
        elif num == 1:
            return 1
        else:
            divisor_num = 1
            dict_fact = prime_factorization_2(num)
            for value in dict_fact.values():
                divisor_num *= (value + 1)
            return divisor_num

    ans = divisor_count(n-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:  # 平方数の場合n**0.5を1つだけにしてる
                    divisors.append(n//i)

        # divisors.sort() # ソートしたけりゃして
        return divisors

    l = make_divisors(n)

    def main():
        cnt = 0
        for i in l:
            if i==1: continue
            v = copy(n)
            while v % i == 0:
                v /= i
            v%=i
            if v==1: cnt += 1
        return cnt

    print(ans+main()-1)


resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict

roots = defaultdict(list)
for k in range(2, 10 ** 6 + 1):
    ki = k * k
    while ki <= 10 ** 12:
        roots[ki].append(k)
        ki *= k


def factors(n):
    fhead = []
    ftail = []
    for x in range(1, int(n ** 0.5) + 1):
        if n % x == 0:
            fhead.append(x)
            if x * x != n:
                ftail.append(n // x)
    return fhead + ftail[::-1]


def solve(N):
    works = set()
    # Answer seems to be anything of the form: N = (K ** i) * (j * K + 1)

    # Try every divisor of N as K ** i
    for d in factors(N):
        # If i == 1, then K == d
        k = d
        if (N // d) % k == 1:
            assert k <= N
            works.add(k)
        if d == 1:
            # If i == 0, then K ** 0 == 1, so K = (N - 1) // j, so anything that is a factor of N - 1 works
            works.update(factors(N - 1))
        elif d in roots:
            # For i >= 2, see if it's in the list of precomputed roots
            for k in roots[d]:
                if k > N:
                    break
                if (N // d) % k == 1:
                    works.add(k)
    works.discard(1)
    return len(works)


(N,) = [int(x) for x in input().split()]
print(solve(N))


if False:

    def brute(N, K):
        while N >= K:
            if N % K == 0:
                N = N // K
            else:
                N = N - K
        return N

    for N in range(2, 10000):
        count = 0
        for K in range(2, N + 1):
            temp = brute(N, K)
            if temp == 1:
                print(N, K, temp)
                count += 1
        print("##########", N, count, solve(N))
        assert count == solve(N)

Submission status: Accepted

Solution code:

def resolve():
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                # divisors.append((i, n // i)) # [(1,max), (2, max-1)]
                divisors += [i,n // i]  # [1,2,3,5]
        divisors.sort()
        return divisors

    N = int(input())
    ans = 0

    # K で割り切れない時
    div1 = set(make_divisors(N-1))
    ans += len(div1) - 1

    # K で割り切れる時
    div2 = set(make_divisors(N))
    for k in div2:
        if k == 1:
            continue
        n = N
        while n % k == 0:
            n //= k
        if n % k == 1:
            ans += 1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N = int(input())
def cd(n):
  ls = []
  for i in range(1,int(n**(1/2))+1):
    if n % i == 0:
      ls += [i, n//i]
  return ls

ans = len(set(cd(N-1))) - 1
for j in set(cd(N)):
  a = N
  if not j == 1:
    while a % j == 0:
      a //= j    
    if a % j == 1:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ns=int(n**0.5)
nms=int((n-1)**0.5)
p=[n]
for i in range(2,ns+1):
  if n%i==0:
    p.append(i)
    if i!=n//i:
      p.append(n//i)

def chd(x,k):
  while x%k==0:
    x=x//k
  return int((x%k)==1)

count=0
for i in p:
  count+=chd(n,i)
for i in range(2,nms+1):
  if (n-1)%i==0:
    count+=1
    if i!=(n-1)//i:
      count+=1
print(count+1-(n==2))

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())
divsN = make_divisors(N)
divsN2 = make_divisors(N-1)
divsN.pop(0)

ans = len(divsN2)-1

for div in divsN:
    n = N
    while True:
        if n%div != 0 or n==1:
            break
        n //= div
    if n%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())
divsN = make_divisors(N)
divsN2 = make_divisors(N-1)
divsN.pop(0)

ans = len(divsN2)-1

for div in divsN:
    n = N+1-1
    while True:
        if n%div != 0 or n==1:
            break
        n //= div
    if n%div == 1:
        ans += 1

print(ans)