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:
def MI():return map(int,input().split())
def LI():return list(MI())

# n,k,c=MI()
# s=input()

"""nを素因数分解"""
"""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

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())
l=[]

yakusuu=(make_divisors(n-1))

for k in range(2,min(10**6,n)+1):
    NN=int(n)
    while NN>=k:
        if NN%k==0:
            NN=NN//k
        else:
            NN=NN%k
    if NN==1:
        l+=k,

ll=(l+yakusuu+[n])

print(len(set(ll)))

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())
l1 = make_divisors(n)
l2 = make_divisors(n-1)
l1_l2_sym_diff = list((set(l1) ^ set(l2)) & set(l2))
ans = len(l1_l2_sym_diff)
for i in range(1, len(l1)):
    n1 = n 
    while n1 % l1[i] == 0:
        n1 = n1//l1[i]
    if (n1-1) % l1[i] == 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


N = int(input())

if N == 2:
    print("1")
else:

    hoge = make_divisors(N - 1)
    hoge.append(N)
    X = make_divisors(N)

    for i in range(1,len(X)):
        a = X[i]
        while a <= N:    
            if N % a != 0:
                break
                
            if (N // a) % X[i] == 1:
                hoge.append(X[i])
                
            a *= X[i]

    print(len(set(hoge))-1)

Submission status: Accepted

Solution code:
import bisect
import sys
import itertools
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 

def f(N):
    c = 0
    for n in range(1, int(N ** 0.5) + 1):
        if N % n == 0:
            c += 1
            if n * n != N:
                c += 1
    return c - 1


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

    res = 0
    res += f(N - 1)

    for n in range(1, int(N ** 0.5) + 1):
        if N % n == 0:
            if n != 1:
                M = N
                while M % n == 0:
                    M //= n
                if M % n == 1:
                    res += 1
        
            if n * n != N:
                n = N // n
                M = N
                while M % n == 0:
                    M //= n
                if M % n == 1:
                    res += 1

    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

N = int(readline())

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

n1 = N - 1

n1_count = 1

i = 2
while i * i <= n1:
    if n1 % i == 0:
        if n1 // i != i:
            n1_count += 2
        else:
            n1_count += 1
    
    i += 1

n_count = 1
i = 2
while i * i <= N:
    if N % i == 0:
        a = i
        n = N
        while n % a == 0:
            n = n // a
        if (n - 1) % a == 0:
            n_count += 1
        
        if N // i != i:
            a = N // i
            n = N
            while n % a == 0:
                n = n // a
            if (n - 1) % a == 0:
                n_count += 1

    i += 1

print(n1_count + n_count)

Submission status: Accepted

Solution code:
n = int(input())
def make_divisors(n):
  for i in range(2, int(n**0.5)+1):
    if n % i == 0:
      x = n//i
      while x%i == 0:
        x = x//i
      if x%i == 1:
        ans += 1
  return
def count_divisors(n):
  c = 0
  for i in range(1, int(n**0.5)):
    if n % i == 0:
      c += 2
  if n%int(n**0.5) == 0:
    if n==n//int(n**0.5):
      c += 1
    else:
      c += 2
  return c
ans = 0
def count_divisors(n):
  c = 0
  for i in range(1, int(n**0.5)):
    if n % i == 0:
      c += 2
  if n%int(n**0.5) == 0:
    if int(n**0.5)==n//int(n**0.5):
      c += 1
    else:
      c += 2
  return c
ans += count_divisors(n-1)
def make_divisors(n):
  c = 0
  for i in range(2, int(n**0.5)+1):
    if n % i == 0:
      x = n//i
      while x%i == 0:
        x = x//i
      if x%i == 1:
        c += 1
  return c
ans += make_divisors(n)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())


def divisor(M):
    div = set()
    for i in range(1, int(N ** 0.5 + 0.5) + 1):
        if M % i == 0:
            div.add(i)
            div.add(M // i)
    return div


def simu(M, X):
    cnt = 0
    while M >= X:
        if M % X == 0:
            M //= X
        elif M % X == 1:
            return True
        else:
            M -= X
        cnt += 1
        if cnt > 1000:
            return False
    return M == 1


A = divisor(N)
B = divisor(N - 1)

# N%K==1となるやつ
ans = len(B) - 1

for a in (A - B):
    if simu(N, a):
        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


n = int(input())
count = len(make_divisors(n-1))
# print(count)
yaku = make_divisors(n)
for e in yaku[1:-1]:
    # print(e)
    if e*e > n:
        break
    num = n
    while num%e == 0:
        num //= e
        if num == 1:
            count += 1
            break
        if num < e:
            break
        if (num-1)%e == 0:
            count += 1
            break

print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    if n == 2:
        print(1)
        return
    if n == 3:
        print(2)
        return
    ans = 0
    for i in range(2, int(sqrt(n)) + 1):
        m = n
        if m % i == 0:
            while m % i == 0:
                m //= i
            if m % i == 1:
                ans += 1
    m = n - 1
    l = []
    for i in range(2, int(sqrt(m)) + 1):
        t = 0
        while m % i == 0:
            m //= i
            t += 1
        if t:
            l.append(t)
    if m != 1:
        l.append(1)
    tmp = 1
    for li in l:
        tmp *= (li + 1)
    print(ans+tmp)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())


def factorization(n):
    arr = dict()
    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[i] = cnt

    if temp != 1:
        arr[temp] = 1

    if not arr and n != 1:
        arr[n] = 1

    return arr


def make_divisors(n):
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            yield i
            if i != n // i:
                yield n // i


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

it = make_divisors(N)
next(it)

for k in it:
    tmp = N
    while not tmp % k:
        tmp //= k
    if tmp % k == 1:
        ans += 1
print(ans)

Submission status: Accepted

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

def check(n,k):
    while n > k:
        if n % k == 0:
            n //= k
        else:
            n -= k

    if n % k == 0:
        return True
    elif n - k == 1:
        return True
    else:
        return False


def main():
    N = int(input())
    if N == 2:
        print(1)
        exit()
    div = divisor(N-1)
    ans = [N] + div
    for i in range(1,int(N**0.5)+1):
        if i in div:
            continue
        tmp = int(N)
        if i == 1:
            continue
        if N % i == 0:
            while tmp % i == 0:
                tmp //= i
            if tmp % i == 1:
                ans.append(i)
        elif N % i == 1:
            ans.append(i)
        else:
            tmp -= i + 1
            if tmp % i == 0:
                ans.append(i)
    print(len(ans))




    


if __name__ == "__main__":
    main()

Submission status: Accepted

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

# nの約数を全て求める
def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

def hantei(i):
    global n
    n1 = copy.copy(n)
    while n1 % i == 0:
        n1 //= i
    if n1 % i == 1:
        return True
    else:
        return False

li = divisor(n)
li2 = divisor(n-1)
ans = 0

for i in li:
    if i != 1:
        if hantei(i):
            ans += 1

for i in li2:
    if n % i != 0:
        ans += 1

print(ans)

Submission status: Accepted

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

N = int(input())
d = make_div(N)
d = d[1:]
s = set()

for di in d:
    N2 = N
    
    while N2%di==0:
        N2 //= di
    
    if (N2-1)%di==0:
        s.add(di)

d = make_div(N-1)
d = d[1:]

for di in d:
    s.add(di)

print(len(s))

Submission status: Accepted

Solution code:

N = int(input())
if N<=10**6:
    res = 0
    for K in range(2, N + 1):
        n = N
        while n >= K:
            if n % K == 0:
                n = n // K
            else:
                n = n % K
        if n == 1:
            res += 1
    print(res)
    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)

    # divisors.sort()
    return divisors

def hantei(n):
    k = int(n**0.5)
    if k*(k+1) == n or (k-1)*k == n or (k+1)*(k+2) == n:
        return k
    else:
        return 0

res1 = make_divisors(N-1)
res2 = hantei(N)
if res2!=0:
    res1.append(res2)
res1.append(2)
res1.append(N)
res1.remove(1)


res3 = make_divisors(N)
res3.remove(1)
for val in res3:
    n = N
    while n >= val:
        if n % val == 0:
            n = n // val
        else:
            n = n%val
    if n == 1:
        res1.append(val)
        # print(K)
res = len(set(res1))
print(res)

Submission status: Accepted

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

a = set(divisor(n-1))

for k in divisor(n):
    if k < 2:
        continue
    if k in a:
        continue
    m = n
    while m%k == 0:
        m //= k
    s = m%k
    if s == 1:
        a.add(k)

print(len(a)-1)

Submission status: Accepted

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

    divisors.sort()
    return divisors
N =int(input())
k1 = make_divisors(N)
k2 = make_divisors(N-1)
ans = 0
n = N

for x in k1:
    
    if x == 1:continue
    if n%x == 1:ans+=1
    while n%x == 0:
        n//=x
        if n%x == 1:
            ans+=1
            
    n = N
for x in k2:
    if x == 1:continue
    if n%x == 1:ans+=1
    while n%x == 0:
        n//=x
        if n%x == 1:
            ans+=1
            
    n = N
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,boundary=1,search=[],replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,boundary=1,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
def show2d(g,h,w):
    for i in range(h):show(g[i*w:i*w+w])

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()


## return prime factors of N as dictionary {prime p:power of p}
## within 2 sec for N = 2*10**20+7
def primeFactor(N):
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret


## return the list of prime numbers in [2,N], using eratosthenes sieve
## within 2sec for N = 1.2*10**7
def PrimeNumSet(N):
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList:
        if seachList[0] <= Max:
            break
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

## retrun LCM of numbers in list b
## within 2sec for no of B = 10*5  and  Bi < 10**6
def LCM(b,mo=10**9+7):
    prs=PrimeNumSet(max(b))
    M=dict(zip(prs,[0]*len(prs)))
    for i in b:
        dc=primeFactor(i)
        for j,k in dc.items():
            M[j]=max(M[j],k)
    
    r=1
    for j,k in M.items():
        if k!=0:
            r*=pow(j,k,mo)
            r%=mo
    return r

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

def Primes(x):
    div=[1]
    for j,c in primeFactor(x).items():
        tmp=[]
        for x in div:
            for k in range(1,c+1):
                tmp+=[x*j**k]
        div+=tmp
    return div


def f(x,k):
    c=0
    while x>1 and c<100:
        #print((x,k))
        c+=1
        if x%k==0:
            x=x//k
        else:
            x-=k
    #print((x,k))
    return x

def check(n):
    rt=[]
    tmp=1
    for i in range(2,n+1):
        if f(n,i)==1:
            tmp+=1
            rt+=[i]
    return rt
    
def solve(n):
    rt=set(Primes(n-1))
    rt.add(2)
    rt.add(n)
#    print(Primes(n))
    for d in Primes(n):
#        print(d,'---')
        if d==1:continue
        x=n
#        c=0
        #while x%d==0 and c<100:
        while x%d==0:
#            c+=1
            x//=d
#            print(x,d)
        if x%d==1:
            rt.add(d)
    rt.remove(1)
    return rt

n=int(input())
print(len(solve(n)))

Submission status: Accepted

Solution code:
N = int(input())

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

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

ans = []
for n in range(1, int(N ** 0.5) + 1):
    if (N - 1) % n == 0:
        ans.append(n)
        ans.append((N - 1) // n)

for k in range(2, int(N ** 0.5) + 1):
    x = N
    while x % k == 0:
        x //= k

    if 1 in (x % k - k, x % k):
        ans.append(k)

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

    return divisors

def test(n,x):
    while True:
        if n>=x:
            if n%x==0:
                n/=x
            else:
                n%=x
        else:
            break

    if n==1:
        return True
    else:
        return False

l=make_divisors(N)
la=make_divisors(N-1)

lb=[]
for i in l:
    if i==1 or i==N:
        continue
    if test(N,i):
        lb.append(i)

la.extend(lb)

print(len(set(la)))

Submission status: Accepted

Solution code:
#
import sys
import math
import numpy as np
import itertools


# ひとつ入力
n = int(input())
q = []
p=0
def hantei(k):
    a = n
    b = 0
    while 1:
#        print(n,k,a)
        if a % k == 0:
            a = a//k
        else:
            a = a % k
        if a == 1:
#            print(k)
            return(1)
        if a < k :
            return(0)

x = []

# https://qiita.com/LorseKudos/items/9eb560494862c8b4eb56
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

x += make_divisors(n)
x += make_divisors(n-1)
x = set(x)
x.remove(1)

for i in x:
    if hantei(i) == 1:
        q.append(i)

#print(x)
#print(p)
#print(q)

print(len(q))

Submission status: Accepted

Solution code:
N=int(input())
if N==2:
    print(1)
    exit()
DN={N}
k=2
while(k*k<=N):
    if N%k==0:
        DN.add(k)
        DN.add(N//k)
    k+=1
DN1={N-1}
k=2
while(k*k<=(N-1)):
    if (N-1)%k==0:
        DN1.add(k)
        DN1.add((N-1)//k)
    k+=1
DN=sorted(list(DN))
DN1=sorted(list(DN1))
#print(DN)
#print(DN1)
ans=set()
for K in DN:
    tmp=N
    while(tmp>=K):
        if tmp%K==0:
            tmp//=K
        else:
            tmp%=K
    if tmp==1:
        ans.add(K)
for K in DN1:
    tmp=N
    while(tmp>=K):
        if tmp%K==0:
            tmp//=K
        else:
            tmp%=K
    if tmp==1:
        ans.add(K)


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(1000000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def sim(N, K, v=False):
    s = [N]
    while N >= K:
        if N % K == 0:
            N = N // K
        else:
            N = N % K
        s.append(N)
    if v:
        print(K, s)
    return N


def divisor(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            yield i
            if i != n // i:
                yield n // i


@mt
def slv(N):
    ans = set()
    for _ in divisor(N):
        if _ != 1 and sim(N, _) == 1:
            ans.add(_)
    for _ in divisor(N-1):
        if _ != 1 and sim(N, _) == 1:
            ans.add(_)

    return len(ans)


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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

      return 0

if __name__ == "__main__":
      solve()

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())
f=make_divisors(n)
f1=set(make_divisors(n-1))
f.remove(1)
f1.remove(1)

for i in f:
    if (n//i)%i==0:
        _n=n//i
        while _n%i==0:
            _n//=i
        if _n%i==1:
            f1.add(i)

    elif (n//i)%i==1:
        f1.add(i)

print(len(f1))

Submission status: Accepted

Solution code:
N = int(input())
import itertools
#N = 6
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

NN = factorization(N)

# N-1について
NN_1 = factorization(N-1)
#print(NN_1)
ans = 0
tmp = 1
for i in NN_1:
    tmp *= i[1]+1
ans += tmp - 1
#print(ans)

#
P = []
IKU = []
PP = []
for i in NN:
    P.append(i[0])
    j = i[1]
    tmp = []
    for k in range(j+1):
        tmp.append(k)
    PP.append(tmp)
    IKU.append(i[1])
L = len(P)
#print('aaa')
for i in itertools.product(*PP):
    tmp = 1
    for j in range(L):
        tmp *= P[j]**i[j]
    K = tmp
    tmp = 1

    if K != 1:
        #print('K',K)
        for j in range(1,41):
            tmp *= K
            if N<tmp:
                break
            #print(tmp)
            if (N-tmp)%(tmp*K)==0:
                ans += 1
                #print('YES',K)
                break
            
#print(NN_1)
#print(NN)
if N==2:
    print(1)
else:
    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

#nは必ず含まれる
ans = 1

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

l = make_divisors(n)

for num in l[1:]:
	if num**2 > n:
		break
	else:
		tmp = n
		while True:
			tmp = tmp // num
			if tmp % num != 0:
				break
		if tmp % num == 1:
			ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = input()

S = set()

# (a*K+1)*K**b==N

# b==0
# a*K+1==N
K = 1
while K*K<=N-1:
  if (N-1)%K==0:
    if K>1:
      S.add(K)
    if (N-1)/K>1:
      S.add((N-1)/K)
  K += 1

# b==1
# (a*K+1)*K==N
K = 1
while K*K<=N:
  if N%K==0:
    if K>1 and (N/K-1)%K==0:
      S.add(K)
    K2 = N/K
    if K2>1 and (N/K2-1)%K2==0:
      S.add(K2)
  K += 1

# b>=2
for b in range(2, 100):
  K = 2
  while True:
    if K**b>N:
      break
    if N%K**b==0 and (N/K**b-1)%K==0:
      S.add(K)
    K += 1

print len(S)

Submission status: Accepted

Solution code:
N = int(input())


def factorization(n):
    arr = dict()
    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[i] = cnt

    if temp != 1:
        arr[temp] = 1

    if not arr and n != 1:
        arr[n] = 1

    return arr

def make_divisors(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            yield i
            if i != n // i:
                yield n//i

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

it = make_divisors(N)
next(it)

for k in it:
    tmp = N
    while not tmp % k:
        tmp //= k
    if tmp % k == 1:
        ans += 1
print(ans - 1)

Submission status: Accepted

Solution code:
N=int(input())
if N==2:
    print(1)
    exit()
DN={N}
k=2
while(k*k<=N):
    if N%k==0:
        DN.add(k)
        DN.add(N//k)
    k+=1
DN1={N-1}
k=2
while(k*k<=(N-1)):
    if (N-1)%k==0:
        DN1.add(k)
        DN1.add((N-1)//k)
    k+=1
DN1=len(DN1)
#print(DN)
#print(DN1)
ans=0
for K in DN:
    tmp=N
    while(tmp>=K):
        if tmp%K==0:
            tmp//=K
        else:
            tmp%=K
    if tmp==1:
        ans+=1

#print(ans)
print(DN1+ans)

Submission status: Accepted

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

    # divisors.sort()
    return divisors

n = int(input())
i = 2
cnt = 1
check = 0

# for i in range(2, n + 1):
#     m = n
#     while m % i == 0:
#         m //= i
#     m %= i
#     if m == 1:
#         print(i)
#         cnt += 1
# print(cnt)
# print()
# print()

out = [n]
while i < n: #割ってひく
    m = n
    if i - m / i > 2:
        break
    while m % i == 0:
        check = 1
        m //= i

    if (m % i == 1 and check):
        out.append(i)
        cnt += 1
    i += 1

i = 2
while i * i <= n: #割ってひく
    m = n
    while m % i == 0:
        m //= i
    if m == 1:
        out.append(i)
    i += 1

out += make_divisors(n - 1)
print(len(set(out)) - 1)

Submission status: Accepted

Solution code:
N = int(input())

def divisors(n):
    ret = set()
    m = 1
    while m*m <= n:
        if n%m==0:
            ret.add(m)
            ret.add(n//m)
        m += 1
    return ret

a = divisors(N)
b = divisors(N-1)

ans = len(b)-1
for k in a:
    if k==1: continue
    n = N
    while n%k==0:
        n //= k
    if n%k == 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)
    divisors.sort()
    return divisors
n=int(input())
x=make_divisors(n)
l=len(x)
ans=0
for i in range(l):
    k=n
    if x[i]==1:
        continue
    while k%x[i]==0:
        k//=x[i]
    if k%x[i]==1 or k-k%x[i]==1:
        #print(x[i])
        ans+=1
#print(ans)
y=make_divisors(n-1)
#print(y)
l2=len(y)
ans2=0
for i in range(l2):
    k=n
    if y[i]==1:
        continue
    while k%y[i]==0:
        k//=y[i]
    if k%y[i]==1 or k-k%y[i]==1:
        #print(y[i])
        ans2+=1
print(ans+ans2)

Submission status: Accepted

Solution code:
#n = int(input())
#n,k = map(int,input().split())
#x = list(map(int,input().split()))

# print("Yes")
# print("No")

# print("YES")
# print("NO")



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

    divisors.sort()
    return divisors


N = int(input())
ans = 0

num1 = make_divisors(N)
for i in range(1,len(num1)):
    mm = N//num1[i]
    while(mm%num1[i]==0):
        mm = mm//num1[i]
    if mm%num1[i]==1:
        ans += 1
        # print(num1[i])

# print(num1)
num2 = make_divisors(N-1)
ans += len(num2)-1
# print(num2)

print(ans)

Submission status: Accepted

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

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

    return divisors

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

for i in make_divisors(N):
    if i == 1:
        continue

    now = N
    while now % i == 0:
        now //= i
    if now == 1:
        ans += 1
    if i in make_divisors(now-1):
        ans += 1

print(ans)