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())
A = []
c = 0

for i in range(2,int(N**0.5)+1):
    if N % i == 0:
        A.append(i)
        A.append(N//i)

for i in range(2,int((N-1)**0.5)+1):
    if (N - 1) % i == 0:
        A.append(i)
        A.append((N-1)//i)
        
A = list(set(A))
if N == 2:
    print(1)
else:
    for i in A:
        start = N
        while(True):
            if start % i != 0:
                break
            start = start//i
        if start % i == 1:
            c += 1
    print(c+2)

Submission status: Accepted

Solution code:
import math


def judge(n, k):
    m = n % k
    while m == 0:
        n //= k
        m = n % k
    return m


def div_list(n):
    l = set()
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            l.add(i)
            j = n // i
            if i != j:
                l.add(j)
    return l


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

    cnt = len(div_list(N-1)) - 1
    cnt += sum(1 for d in div_list(N) if d != 1 and judge(N, d) == 1)

    print(cnt)


main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
def judge(k, M):
    while M%k==0:
        M //= k
    return M%k == 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)
    # divisors.sort()
    return divisors

l = make_divisors(N)+make_divisors(N-1)
ans = 0
for x in l:
    if x == 1:
        continue
    if judge(x, N):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
c = 0

for i in range(2,int(N**0.5)+1):
    if N % i == 0:
        A.append(i)
        A.append(N//i)

for i in range(2,int((N-1)**0.5)+1):
    if (N - 1) % i == 0:
        A.append(i)

        A.append((N-1)//i)
A = list(set(A))
if N == 2:
    print(1)
else:
    for i in A:
        start = N
        while(True):
            if start % i != 0:
                break
            start = start//i
        if start % i == 1:
            c += 1
    print(c+2)

Submission status: Accepted

Solution code:
import math
n = int(input())
 
m = n-1
ans1 = 0
for i in range(1, math.ceil(math.sqrt(m))):
  if m%i == 0:
    ans1 += 2
if math.sqrt(m).is_integer():
  ans1 += 1
ans1 -= 1

ans2 = 0
for i in range(2, math.ceil(math.sqrt(n))):
  if n%i == 0:
    k = n
    while k % i == 0:
      k = k // i
    if k % i == 1:
      ans2 += 1
    k = n
    j = n/i
    while k % j == 0:
      k = k // j
    if k % j == 1:
      ans2 += 1
      
if math.sqrt(n).is_integer():
  ans2 += 1
ans2 += 1
#print(ans1, ans2)
print(ans1+ans2)

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

def test(n,x):
    while n%x==0:
        n//=x
    n%=x
    return n==1

l=make_divisors(N)
la=make_divisors(N-1)
l.extend(la)
l=set(l)

c=0
for i in l:
    if i==1 or i==N:
        continue
    if test(N,i):
        c+=1

print(c+1)

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-

#約数列挙（ググってでてきたやつ）
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_given = int(input())

#見つけたKのリスト
list_found_K = []


#パターン1 
divisors_N_minus_1 = make_divisors(N_given-1)
#みつけたKを追加
for divs in divisors_N_minus_1:
	if divs != 1:
		list_found_K.append(divs)

#パターン2
#K候補（Nの約数）
divisors_N = make_divisors(N_given)
divisors_N.remove(1)

#全てのN候補で試行
for candidate_K in divisors_N:
	N_wk = N_given
	#Kで割り尽くす
	while N_wk % candidate_K == 0:
		N_wk //=candidate_K

	#パターン1風　1引いてK候補で割れたらKに正式採用
	if (N_wk-1) % candidate_K == 0:
		list_found_K.append(candidate_K)

print(len(list_found_K))

Submission status: Accepted

Solution code:

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

    divisors.sort()
    divisors.append(n)
    return divisors

def check(N,K):
    try:
        if N == K:
            return True
        if N % K ==1:
            return True
        if N<K:
            return False
        
        if N % K ==0:
            return check(N//K,K)
        else:
            return False
    except:
        return False

def resolve():
    N = int(input())
    ys= set(make_divisors(N))
    ys2= set([i for i in make_divisors(N-1) if check(N,i)])

    x =set([i for i in ys if check(N,i)])

    print(len(x | ys2))


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import Counter

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

def 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

pf = make_divisors(N)
ans = 0
for i in pf:
    if i == 1:
        continue
    n = N
    while n >= i:
        if n % i == 0:
            n //= i
        else:
            n %= i
    if n == 1:
        ans += 1

pf = prime_factorize(N-1)
p = list(Counter(pf).values())
z = 1
for i in p:
    z *= (i+1)
z -= 1
print(ans+z)

Submission status: Accepted

Solution code:
n = int(input())
def make(r):
    rr = [1]
    for i, v in r:
        newrr = rr[:]
        for j in rr:
            for k in range(v):
                newrr.append(j * i ** (k + 1))
        rr = newrr
    return rr
        
def factors(n):
    k = n
    i = 2
    r = []
    while i * i <= k:
        v = 0
        while k % i == 0:
            v += 1
            k //= i
        if v > 0:
            r.append((i, v))
        i += 1
    if k > 1:
        r.append((k, 1))
    return make(r)

def isOK(n, k):
    return n % k == 1

r = 0
for i in factors(n):
    n1 = n
    while n1 % i == 0 and i != 1:
        n1 //= i
    if isOK(n1, i):
        r += 1
#print(factors(n), r)
r += len(factors(n - 1)) - 1
#print(factors(n - 1), r)
print(r)

Submission status: Accepted

Solution code:
# 素因数分解 O(√N)
def prime_decomposition(n):
    i = 2
    prime2exponent = {}  # key:prime --> value:its exponent
    while i*i <= n:
        while n % i == 0:
            n //= i
            if i in prime2exponent:
                prime2exponent[i] += 1
            else:
                prime2exponent[i] = 1
        i += 1
    if n > 1:
        if n in prime2exponent:
            prime2exponent[n] += 1
        else:
            prime2exponent[n] = 1
    return prime2exponent


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

    return divisors


N = int(input())

ans = 0
p2e = prime_decomposition(N-1)
temp = 1
for v in p2e.values():
    temp *= (v+1)
temp -= 1
ans += temp
#print(temp)
#rint(p2e)

divisors = make_divisors(N)
#print(divisors)
for div in divisors:
    cur = N
    if div == 1:
        continue
    while cur % div == 0:
        cur //= div
        #print(cur,div)
    if cur % div == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def divisors(n):
    S,T=[],[]
    for i in range(1,int(n**.5)+1):
        if(n%i==0):
            S.append(i)
            T.append(n//i)
    T.reverse()
    return S+T if(S[-1]!=T[0]) else S+T[1:]

def resolve():
    n = int(input())
    res = set(divisors(n-1))
    res.remove(1)
    res.add(n)

    for s in divisors(n):
        if s == n:
            continue
        tmp = s
        t = n // s
        if s < t: # s >= t
            continue
        while s % t == 0:
            s //= t
        s %= t
        if s == 1:
            res.add(tmp)

    print(len(res))
resolve()

Submission status: Accepted

Solution code:
import math
def make_divisors(n):
    D=[]
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            D.append(i)
            if i!=n//i:
                D.append(n//i)
    D=reversed(sorted(D))
    return D

n=int(input())
Ans=[n]
T=make_divisors(n-1) #nスタートのもの
for t in T:
    if t!=1:
        Ans.append(t)

S=make_divisors(n) #nの約数
for s in S:
    now=n
    if s!=n and s!=1:
        while now%s==0:
            now=now//s
        if now%s==1:
            Ans.append(s)
        
Ans.sort()
ans=0
cnt=0
for a in Ans:
    if cnt!=a:
        cnt=a
        ans+=1
print(ans)

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-

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

ks=make_divisors(N-1)
ks.remove(1)
#print(ks)
ans=ks

divs=make_divisors(N)
divs.remove(1)
for i in divs:
    divN=N
    while divN%i==0:
        divN=divN/i
    
    if (divN-1)%i==0:
        ans.append(i)

#print(ans)
print(len(ans))

Submission status: Accepted

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


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


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

Submission status: Accepted

Solution code:
import math
def prime(x):
  L = []
  last = math.floor(x ** 0.5) 
  for i in range(1, last + 1):
    if x % i == 0:
      L.append(i)
      if x // i != i:
        L.append(x // i)
  return L

N = int(input())

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

L = prime(N - 1)

ans = len(L) - 1

D = prime(N)

for i in D:
  if i == 1: continue
  t = N
  while (t / i == t // i):
    t //= i

  t -= 1
  if t / i == t // i:
    ans += 1

print(ans)

Submission status: Accepted

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

    def divisor_list(n):
        """n の正の約数のリスト"""
        ret = set()
        for k in range(1, int(n**0.5) + 1):
            if n % k == 0:
                ret.update({k, n // k})
        return sorted(ret)

    ans = (len(divisor_list(N - 1)) - 1)  # K >= 2 なので、-1 する
    for k in divisor_list(N):
        if k == 1:
            continue
        n = N
        while n % k == 0:
            n //= k
        ans += 1 if n % k == 1 else 0
    return ans

print(f_division_or_substraction())

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**9)

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

ds = set(make_divisors(N)) | set(make_divisors(N-1))

def check(n,k):
    if n<k:
        return n==1
    elif n%k==0:
        return check(n//k,k)
    else:
        return check(n%k,k)

ds.remove(1)
cnt = 0
for d in ds:
    # print(d)
    if check(N,d):
        cnt+=1
print(cnt)

Submission status: Accepted

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


cnt=0
for i in range(2,int(math.sqrt(n))+1):
    
    if (n-1)%i==0:
       
        
        cnt=cnt+2
    if (n)%i==0:
        s=n
        while s%i==0:
            s=s//i
        if s%i==1:
            
            cnt=cnt+1
if int(math.sqrt(n-1)) == math.sqrt(n-1):
    
    cnt=cnt-1

if n==2:
    print(1)
else:
    print(cnt+2)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

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(int(n))
  return table

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 = onem()
co = 0

nnn = make_divisors(n)

mp = make_divisors(n-1)


for i in nnn:
    nn = n
    if i == 1:
        continue
    while True:
        if nn == 1:
            co += 1
            break
        elif nn <= 0:
            break
        if nn % i:
            nn = nn % i if nn//i else 0
        else:
            nn //= i
for i in mp:
    if i != 1:
        co += 1
print(co)

Submission status: Accepted

Solution code:
import math
N = int(input())
s = math.floor(math.sqrt(N))
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
ans = make_divisors(N-1)
for i in range(2, s+1):
    temp = N % i
    if temp == 0:
        temp2 = N // i
        temp = temp2 % i
        while temp == 0:
            temp2 = temp2 // i
            temp = temp2 % i
        if temp == 1 and i not in ans:
            ans.append(i)
    elif temp == 1 and i not in ans:
        ans.append(i)
print(len(ans))

Submission status: Accepted

Solution code:
def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return (_N-1)%p == 0

def calc_divisors(n):
    m = int(n**0.5)
    left = []
    right = []
    for i in range(1, m+1):
        if n%i == 0:
            left.append(i)
            right.append(n//i)
    if left[-1] == right[-1]:
        right.pop()
    return left + right[::-1]

N = int(input())
P0 = calc_divisors(N)[1:] # [:1]で1を除外
P1 = calc_divisors(N-1)[1:] # 同上
ans = len(P1)
for p in P0:
  ans += check(p)

print(ans)

Submission status: Accepted

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

N = int(input())

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

s = set([N - 1, N])


for i in range(2, int(sqrt(N)) + 1):
    tmp = N
    if (tmp - 1) % i == 0:
        s.add(i)
        s.add((tmp - 1) // i)
    elif tmp % i == 0:
        while tmp % i == 0:
            tmp //= i

        if tmp % i == 1:
            s.add(i)

        tmp = N
        while tmp % (N // i) == 0:
            tmp //= (N // i)

        if tmp % (N // i) == 1:
            s.add(N // i)

# print(s)
print(len(s))

Submission status: Accepted

Solution code:
N = int(input())

divisor = set([N, N - 1])
x = N
for i in range(2, int(x ** 0.5) + 1):
    z = x
    while z % i == 0:
        z //= i
    if z % i == 1:
        divisor.add(i)
        
    if i == x // i:
        continue
        
    z = x
    while z % (x // i) == 0:
        z //= (x // i)
    if z % (x // i) == 1:
        divisor.add((x // i))
        
x = N - 1
for i in range(2, int(x ** 0.5) + 1):
    if x % i == 0:
        divisor.add(i)
        divisor.add(x // i)

print(len(divisor) if N > 2 else 1)

Submission status: Accepted

Solution code:
n=int(input())
def prime_factorize(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    f=3
    while f**2<=n:
        if n%f==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return(a)

import collections
A=collections.Counter(prime_factorize(n-1))
ans=1
cnt=0
for a,b in A.items():
    ans*=(b+1)

import math
li=[]
for i in range(2,math.floor(n**0.5)+1):
    if n%i==0:
        li.append(i)
        if i!=n//i:
            li.append(n//i)
li.append(n)
for i in li:
    x = n
    while x % i == 0:
        x //= i
    if x % i == 1:
        cnt += 1
print(ans - 1 + cnt)

Submission status: Accepted

Solution code:
N = int(input())

def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return (_N-1)%p == 0

n = int(N**0.5) + 1
P0 = set([N])
P1 = set([N-1])
for i in range(2, n+1):
  if (N-1)%i == 0:
    P1.add(i)
    P1.add((N-1)//i)
  if N%i == 0:
    P0.add(i)
    P0.add(N//i)

P0.discard(1)
P1.discard(1)
ans = len(P1)
for p in P0:
  ans += check(p)

print(ans)

Submission status: Accepted

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

n=int(input())
divs1=divisors(n)
divs2=divisors(n-1)
cnt=len(divs2)-1
for val in divs1:
  if val==1:
    continue
  tmp=n
  while tmp%val==0:
    tmp=tmp//val
  if tmp%val==1:
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
            if N//i != i:
                ans.append(N//i)
    return ans

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

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

for K in factor(N)[1:]:
    if check(K,N):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
c=0
for i in range(2,int(n**0.5)+1):
    d=n
    while d%i==0:
        d//=i
    if n%i==0 and (d-1)%i==0:
        c+=1
for i in range(2,int((n-1)**0.5)+1):
    if (n-1)%i==0:
        if n-1==i**2:
            c+=1
        else:
            c+=2
if n<3:
    print(1)
else:
    print(c+2)

Submission status: Accepted

Solution code:
import math
import random
import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline
MAX_INT = 2**62-1


def main():
    def check(num, k):
        mod = num % k
        if mod == 1:
            return True
        if mod:
            return False
        exp = k
        while num % exp == 0:
            num //= exp
            exp *= exp
        return check(num, k)

    N = int(input())
    ans = 2
    for i in range(2, round(N**0.5)+1):
        ans += ((N-1) % i == 0) * 2
        if N % i == 0:
            ans += check(N, i)

    print(ans - (round((N-1)**0.5)**2 == N-1))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
cnt = 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.pop(0)
    return divisors
N1_yakusu = make_divisors(N-1)
N_yakusu = make_divisors(N)
cnt += len(N1_yakusu)
for K in N_yakusu:
    new_N = N
    while(new_N%K==0):
        new_N = new_N//K
    if(new_N%K == 1):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
#(i)N%K!=0の時、N-Kを繰り返すことになるためN-K%K=N%Kより
#N%K=1にならないといけない
#よってこのようなKはN-1が最大であり、他は全てN-1の約数であり、(そのほかにない)
#(証)
#N%K<=>N-1%K=0より直ちに従う(ただし、K=1の時N%1=0なので注意)
#よって、N-1を素因数分解して、チャチャチャっとやって…終わり！

#(ii)N%K==0の時、約数をO(sqrt(N))で全探査し、
#高々2*(sqrt(N))の約数KについてO(log(N))オーダーで(N/K^i)%K=1かを調べる

import math
N=int(input())
l=[]
ser=[]
#(i)の部分
#素因数分解
pf={}
ans1=1
m=N-1
buf=0
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
#print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
#print(l)	#これでlistになったろう
ans1=1
for i in range(len(keys)):
    ans1=ans1*(l[i][1]+1)
ans1=ans1-1
#print(ans1)

#(ii)の部分
ans2=0
for i in range(int(math.sqrt(N))):
    a=i+1
    b=N/a
    #print(a)
    if b.is_integer()==True:
        if a!=b:
            ser.append(a)
            ser.append(int(b))
        else:
            ser.append(a)
#print(ser)
for i in range(len(ser)):
    buf=N
    if ser[i]!=1:
        while (buf/ser[i]).is_integer()==True:
            #print(buf / ser[i])
            buf=buf//ser[i]
        if buf%ser[i]==1:
            ans2=ans2+1
#print(ser,ans2)
print(ans1+ans2)

Submission status: Accepted

Solution code:
N = int(input())
ans=0
x = N-1
for i in range(2,int(x**(1/2))+1):
  if x%i==0:
    ans+=2
  
if int(x**(1/2))**2==x:
  ans-=1


for i in range(2,int(N**(1/2))+1):
  a = N
  if a%i==0:
    while a%i==0:
      a//=i
    if a%i==1:
      ans+=1
      
    b = N//i
    if b==i:
      continue
    a = N
    while a%b==0:
      a//=b
    if a%i==1:
      ans+=1
    
print(ans+2)

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())
count = 0
nlis = make_divisors(n)
n1lis = make_divisors(n-1)
for i in nlis:
  if i == 1:
    continue
  num = n
  while num % i == 0:
    num //= i
  num %= i
  if num == 1:
    count += 1
    
count += len(n1lis) - 1
print(count)

Submission status: Accepted

Solution code:
N = int(input())

res = 0

if N == 2:
    res += 1
else:
    res += 2

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

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

print(res)

Submission status: Accepted

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

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

cnt = 0
divisors = make_divisors(N)
divisors_n1 = make_divisors(N-1)
divisors.extend(divisors_n1)
for K in divisors:
    tmp_N = N_tmp
    if K <= 1: continue
    while tmp_N % K == 0:
        tmp_N = tmp_N // K
    tmp_N = tmp_N % K
    if tmp_N == 1:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

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

a = 0

for i in D(N):
  M = N
  if i == 1:
    continue
  else:
    while M % i == 0:
      M = M//i
    if M % i == 1:
      a += 1

print(len(D(N-1))-1+a)

Submission status: Accepted

Solution code:
n = int(input())

k = 2
count = 1
while k * k <= n:
    m = n
    while m % k == 0:
        m = m / k
    if m % k == 1:
        count += 1
    k += 1

l = 1
while l * l < n - 1:
    if (n - 1) % l == 0:
        count += 1
    l += 1

if n == 2:
    print(1)
else:
    print(count)

Submission status: Accepted

Solution code:
import math
import collections

N = int(input())
res = 1


n = 10 ** 6 + 5000
fl = [1] * n
fl[0] = 0
fl[1] = 0
lprime = []
for i in range(n):
    if fl[i] == 1:
        lprime.append(i)
        ti = i * 2
        while ti < n:
            fl[ti] = 0
            ti += i


def prime_factorize(n):
    global lprime
    a = []
    for p in lprime:
        if p * p > n:
            break
        while n % p == 0:
            a.append(p)
            n //= p
    if n != 1:
        a.append(n)
    return a


def yakusuu(N):
    t = math.floor(math.sqrt(N))
    res = []
    for i in range(2, t + 1):
        if N % i == 0:
            res.append(i)
    return res


tres = prime_factorize(N - 1)
ctres = collections.Counter(tres)
for s in ctres.values():
    res *= s + 1
tres = yakusuu(N)
for c in tres:
    t = N
    while t % c == 0:
        t //= c
    if t == 1 or (t - 1) % c == 0:
        res += 1
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math
n = int(input())
if n == 2:
    print(1)
    exit()
# n-1の約数を全列挙か、n の約数を全部探索して、n//k*p = 1+k*qになるかを確かめる
def divisor(n):
    res = [n]
    for i in range(2,1+math.floor(math.sqrt(n))):
        if n % i == 0:
            res.append(i)
            if i != n//i:
                res.append(n//i)
    return res
ans = len(divisor(n-1))
# n の約数で全列挙
res = []
lis = divisor(n)
for i in lis:
    # n を i で割れるだけわる
    m = n
    while m % i == 0:
        m = m // i 
    if m % i == 1:
        ans += 1
        res.append(i)
        #print(m,i)
print(ans)

Submission status: Accepted

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

n = int(input())

ans = set()

#約数の列挙
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)

for i in a:
    if i == 1:
        continue
    n_ = n
    while n_ % i == 0:
        n_ //= i
    if (n_ - 1) % i == 0:
        ans.add(i)

d = make_divisors(n - 1)

for i in d:
    if i != 1:
        ans.add(i)

ans.add(n)

print(len(ans))

Submission status: Accepted

Solution code:
n = int(input())

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

ans = len(divisor(n-1))-1
for i in divisor(n):
    if i == 1: continue
    n_ = n
    while n_ % i == 0:
         n_ //= i
    if n_ % i == 1:
        ans += 1
        
print(ans)

Submission status: Accepted

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

    divisors.sort()
    return divisors

tn1 = make_divisors(N-1)
cnt = len(tn1) - 1

tn = make_divisors(N)
for i in range(1, len(tn)):
  t = 1
  k = N
  while(k % tn[i] == 0):
    k = N // (tn[i] ** t)
    t += 1
  if(k%tn[i] == 1):
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
n_set = set()
_n_ls = set()
for i in range(1, 10**6+2):
    if n % i == 0:
        n_set.add(i)
        n_set.add(n // i)
    if (n-1) % i == 0:
        _n_ls.add(i)
        _n_ls.add((n-1) // i)

def check(n, k):
    if n < k:
        return n == 1
    else:
        if n % k == 0:
            n //= k
        else:
            n %= k
        return check(n, k)

cnt = len(_n_ls)
if 1 in _n_ls:
    cnt -= 1
for i in list(n_set):
    if i == 1:
        continue
    if check(n, i):
        cnt += 1
print(cnt)

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

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

for i in set(make_divisors(N)) - {1}:
    M = N
    while M >= i:
        if M % i == 0:
            M //= i
        else:
            break
    if M % i ==  1:
        ans += 1

print(ans)

Submission status: Accepted

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

def check_mod(n, k):
    if k == 1:
        return False
    while n != 0:
        mod = n % k
        if mod == 0:
            n = n/k
        elif mod == 1:
            return True
        else:
            return False

def main():
    n = int(input())
    #あまりが1のやつ
    res = len(make_divisors(n-1))

    for dv in make_divisors(n):
        if check_mod(n, dv):
            res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
n = (m*k+1)*(k^l) となるm,lがあるか？

kは「nの約数 or n%k==1<=>kが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:
                divisors.append(n//i)
    # divisors.sort()
    return divisors
 
def is_f(k,n):
    while n%k==0:
        n /= k
    return n%k==1


n = int(input())

cnt = 0
num = tuple(make_divisors(n)[1:] + make_divisors(n-1)[1:])

for k in num:
    if is_f(k,n):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import math
n = int(input())
if n == 2:
	print(1)
else:
	rn = int(math.sqrt(n) // 1)
	li = []
	for i in range(2, rn+1):
		if n % i == 0:
			li.append(i)
	#print(li)
	ans = 0
	for i in range(len(li)):
		m = n
		while m % li[i] == 0:
			m //= li[i]
		if m % li[i] == 1:
			ans += 1
			#print(m, li[i])
	#print(ans)
	rm = int(math.sqrt(n-1)//1)
	cnt = 0
	irregu = 0
	for i in range(2, rm+1):
		if (n-1) % i == 0:
			#print('divisor', i)
			cnt += 1
		if (n-1) == i**2:
			irregu += 1
	#print(cnt)
	ans += (2*cnt+2-irregu)
	print(ans)