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:
input = raw_input

n = int(input())

def fctr1(n): 
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append([i,c])
            c=0
    if n!=1:
        f.append([n,1])
    return f

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: # choufuku
                divisors.append(n//i)
    # divisors.sort()
    return divisors


def f(n, k):
    tmp = [n]
    while True:
        q = n % k
        if q == 0:
            n /= k
            tmp.append(n)
        elif q == 1:
            tmp.append(q)
            #print(tmp)
            return True
        else:
            return False

#out = 0
#for k in range(2, n): 
#    flag = f(n, k)
#    if flag:
#        print("ans", n, k)
#        out += 1
#out += 1 # k = n

elms = fctr1(n-1) 
out1 = 1
for a, b in elms:
    out1 *= (b+1)
out1 -= 1

yaku2 = make_divisors(n)
out2 = 0
yaku2.remove(n)
yaku2.remove(1)
for ya1 in yaku2:
    ya2 = n // ya1
    while ya1 % ya2 == 0:
        ya1 //= ya2
    if ya1 % ya2 == 1:
        out2 += 1
out2 += 1 # n

#print(out1, out2)
out = out1 + out2

print(out)

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())
nl = make_divisors(n)
nl_m = make_divisors(n-1)
l = sorted(list(set(nl + nl_m)))

ans = 0
for i in range(1, len(l)-1):
    p = n
    k = l[i]
    while p%k == 0:
        p = p // k
    if p%k == 1:
        ans += 1
print(ans+1)

Submission status: Accepted

Solution code:
from collections import defaultdict


def divide(n):  # unsort
    ans = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            ans.append(i)
            if n // i == i:
                continue
            ans.append(n // i)
    return ans


def calc(n, k):
    if k == 1:
        return False
    if n % k == 0:
        n //= k
        if n == 1:
            return True
        return calc(n, k)
    if n % k == 1:
        return True
    else:
        return False


n = int(input())
ans = 0
kouho = []
kouho += divide(n)
kouho += divide(n - 1)
kouho = set(kouho)
cnt = 0
for num in kouho:
    if calc(n, num):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

n=int(input())
soin=factorization(n)
minus=factorization(n-1)

ans=0
tmp=1
for i in range(len(minus)):
    if minus[i][0]!=1:
        tmp*=minus[i][1]+1
tmp-=1
ans+=tmp

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

Submission status: Accepted

Solution code:
from math import sqrt

n = int(input())

ans = 0

for i in range(2,int(sqrt(n))+1):
    if n%i==0:
        x = i
        y = n//i
        while y%x==0:
            y//=x
        if (y-1)%x==0:
            ans += 1
    elif (n-1)%i==0:
        if i**2==n-1:
            ans += 1
        else:
            ans += 2

if n>2:
    ans += 2
else:
    ans += 1

print(ans)

Submission status: Accepted

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

KMIN = 2
KMAX = 10 ** 12 + 1  # Exclusive

def main():
    n = int(input())
    k = []
    k += dividor_of(n - 1)
    for d in dividor_of(n):
        if d < 2:
            continue
        x = n
        while x % d == 0:
            x //= d
        if x % d == 1:
            k.append(d)
    k = sorted(x for x in k if x >= 2)
    print(len(set(k)))

def dividor_of(m):
    res = set()
    for i in range(1, 10 ** 6 + 1):
        if m % i == 0:
            res.add(i)
            res.add(m // i)
        if i ** 2 >= m:
            return sorted(list(res))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
for i in range(2,min(n-1,int(n**.5)+1)):
# for i in range(2,n*+1):
  if n % i == 0:
    tmp = n

    while tmp % i == 0:
      tmp //= i
    if tmp % i == 1:ans += 1

    if n //i == i or n //i == n or n // i == n-1:continue

    tmp = n; i = n // i
    while tmp % i == 0:
      tmp //= i
    if tmp % i == 1:ans += 1

  elif (n-1) % i == 0:
    if (n-1)//i != i and  (n-1) //i != n and (n-1) // i != n-1:ans += 2
    else: ans += 1

if n != 2:ans += 2
else: ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = input()

if n == 2:
    print 1
    exit()

m = n - 1
sqm = int(m ** 0.5) + 1

ans = set([m])
for i in xrange(2, sqm):
    if m % i == 0:
        ans.add(i)
        if i * i != m: ans.add(m // i)

divs = [n]
sqn = int(n ** 0.5) + 1
for i in xrange(2, sqn):
    if n % i == 0:
        divs.append(i)
        if i * i != n: divs.append(n // i)

for d in divs:
    N = n
    while N % d == 0: N //= d

    if N % d == 1: ans.add(d)

print len(ans)

Submission status: Accepted

Solution code:
from math import sqrt


def f(x):
    ret = []
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            ret.append(i)
            ret.append(x // i)

    return ret


n = int(input())

ans = 1
for k in range(2, int(sqrt(n)) + 1):
    r = n
    while r % k == 0:
        r //= k

    if r % k == 1:
        ans += 1

li = f(n - 1)
for e in li:
    if e > int(sqrt(n)):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

s = n - 1

li = [n]

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

for i in range(2, int(n**0.5) + 2):
    if n%i == 0:
        tmp = i
        result = n
        while True:
            if result < 1:
                break
            
            if result == 1:
                li.append(i)
                break
            
            if result%tmp == 0:
                result //= tmp
            else:
                result = result%tmp
                if result == 1:
                    li.append(i)
                    break
                else:
                    break
        
li = list(set(li))

print(len(li) - 1)

Submission status: Accepted

Solution code:
def printDivisors(n) : 
    i = 1
    fact = []
    while i <= n**(0.5): 
        if (n % i == 0) : 
            if (n / i == i) : 
                fact.append(i) 
            else : 
                fact.append(i) 
                fact.append(n//i) 
        i = i + 1
    return fact

n = int(input())
factN = printDivisors(n)[1:]
factN1  = printDivisors(n-1)[1:]
ans = len(factN1)
for fact in factN:
    num = n
    while num>=fact:
        if num%fact == 0:
            num = num//fact
        else:
            num %= fact
            break
    if num == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
n = n-1
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)

    # divisors.sort()
    return divisors

li = make_divisors(n)
n = n+1
for i in range(2,n+1):
    if i**2 > n:
        break
    tmp = n
    #print(i)
    while tmp % i == 0:
        #print(tmp)
        #exit()
        tmp = tmp / i
    if tmp % i == 1:
        ans += 1
        li.append(i)
#print(li)
print(len(set(li)))

exit()

for i in range(2,n+1):
    """
    if i**2 > n:
        break
    """
    tmp = n
    #print(i)
    if tmp % i == 0:
        #print(tmp)
        #exit()
        #tmp = tmp / i
        ans += 1
        print(i)
    """
    if tmp == 1:
        ans += 1
        print(i)
    """
        
print(ans)

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:
N = int(input())

import math

ans = set([])

targ = N
divider = []
for d in range(1, int(math.sqrt(targ)) + 1):
    if targ % d == 0:
        if d * d < targ:
            divider.append(d)
            divider.append(targ // d)
        else:
            divider.append(d)

for K in divider:
    if K == 1: continue
    N_tmp = N
    while N_tmp % K == 0:
        N_tmp //= K
    #
    if N_tmp % K == 1:
        # print("#", K)
        ans.add(K)
            
targ = N - 1
divider2 = []
for d in range(1, int(math.sqrt(targ)) + 1):
    if targ % d == 0:
        if d * d < targ:
            divider2.append(d)
            divider2.append(targ // d)
        else:
            divider2.append(d)

for K in divider2:
    if K == 1: continue
    # print("#", K)
    ans.add(K)

print(len(ans))

Submission status: Accepted

Solution code:
n = int(input())
set_ans = {n}
for x in range(2, int(n ** 0.5) + 1):
    if n % x == 0:
        tmp = n
        while tmp % x == 0:
            tmp //= x
        if tmp % x == 1:
            set_ans.add(x)
for x in range(1, int((n-1) ** 0.5) + 1):
    if (n - 1) % x == 0:
        if x > 1:
            set_ans.add(x)
        if (n - 1) // x != x:
            set_ans.add((n - 1) // x)
print(len(set_ans))

Submission status: Accepted

Solution code:
from collections import defaultdict


def prime_factorize(n):
    i = 2
    res = defaultdict(lambda: 0)
    while i * i <= n:
        while n % i == 0:
            res[i] += 1
            n = n // i
        i += 1
    if n != 1:
        res[n] = 1
    res = dict(res)
    return res


def divisor(n):
    i = 1
    res = set()
    while i * i <= n:
        if n % i == 0:
            res.add(i)
            res.add(n // i)
        i += 1
    return res


def solve(n):
    pf1 = prime_factorize(n - 1)
    ans = 1
    for v in pf1.values():
        ans *= v + 1
    ans -= 1
    # print(ans)

    pf2 = divisor(n)
    pf2.remove(1)
    for y in pf2:
        m = n
        while m % y == 0:
            m //= y
        m %= y
        if m == 1:
            ans += 1
    return ans


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

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
s=len(make_divisors(N-1))
p=make_divisors(N)
for i in range(1,len(p)):
  q=N
  while True:
    if q%p[i]==0:
      q/=p[i]
    else:
      break
  if (q-1)%p[i]==0:
    s+=1
print(s-1)

Submission status: Accepted

Solution code:
N = int(input())


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


factors = factorization(N - 1)
tmp = 1
for prime, power in factors:
    tmp *= power + 1

ans = tmp - 1


divisors = make_divisors(N)
divisors.remove(1)
for d in divisors:
    n = N
    while n % d == 0:
        n //= d
    if n % d == 1:
        ans += 1

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

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

import math

def prime_division2(x):
    q = int(math.sqrt(x))
    h = {}
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            h[i] = ex
    if x>q:
        h[x] = 1
    return h

def prime_division(x):
    q = int(math.sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

def nxt(es,es0):
    for i in range(len(es)):
        if es[i]<es0[i]:
            es[i] += 1
            return
        es[i] = 0

def ok(n,k):
    while n>=k:
        if n%k==0:
            n = n//k
        else:
            n = n%k
    return 1 if n==1 else 0

n = inn()
sm = 0
for m in [n-1,n]:
    ps = prime_division(m)
    es = [0]*len(ps)
    es0 = [pe[1] for pe in ps]
    while es != es0:
        nxt(es,es0)
        t = 1
        for i in range(len(ps)):
            t *= ps[i][0]**es[i]
        sm += ok(n,t)
print(sm)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

N = int(input())

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

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

for i in range(2, int(N**0.5)+1):
    if N%i==0:
        if chk(i):
            ans.add(i)
        j = N//i
        if chk(j):
            ans.add(j)
    elif (N-1)%i==0:
        if chk(i):
            ans.add(i)
        j = (N-1)//i
        if chk(j):
            ans.add(j)

# print(ans)
if N == 2:
    print(1)
else:
    print(len(ans))

Submission status: Accepted

Solution code:
def make_divisors(n):
    divisors = [n]
    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()
    return divisors


def main():
    N = int(input())
    if N == 2:
        print(1)
        exit()
    n = make_divisors(N)
    m = make_divisors(N - 1)
    cnt = len(m)
    for i in n:
        tmp = N
        while tmp % i == 0:
            tmp //= i
        if tmp % i == 1:
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

def c1(n):
    n -= 1
    for i in range(1, (int)(math.sqrt(n)) + 1) : 
        if((n) % i == 0):
            sol.add(i)
            sol.add(n/i)

def c2(n):
    for i in range(1, (int)(math.sqrt(n)) + 1) : 
        if((n) % i == 0): 
            if sd(n,i) % i == 1:
                sol.add(i)
            if sd(n, n/i) % (n/i) == 1:
                sol.add(n/i)

n = int(input())
sol = {1}
c1(n)
c2(n)
print(len(sol)-1)

Submission status: Accepted

Solution code:
import math

n = int(input())
# s = input()
# n,k = map(int,input().split())
# da = list(map(int,input().split()))
# a = [int(input()) for i in range(n)]
# da = [list(map(int,input().split())) for i in range(m)]
st = set()

for i in range(1,int(math.sqrt(n))+1):
    if n%i == 0:
        st.add(i)
        st.add(n//i)
st.remove(1)
ans = 0
l = n-1
stt = set()
for i in range(1,int(math.sqrt(n))+1):
    if l%i == 0:
        stt.add(i)
        stt.add(l//i)
stt.remove(1)
ans += len(stt)

for i in st:
    m = n
    while m%i == 0:
        m //= i
    if m%i == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ans = 2
for i in range(2,int((n-1) ** 0.5) + 2):
    if (n-1) % i == 0:
        #print(i)
        ans += 1
        if i ** 2 < n-1:
            ans += 1
        else:
            if i ** 2 > n-1:
                ans -= 1
            break
#print(ans)

for i in range(2,int(n ** 0.5) + 2):
    if n % i == 0:
        nt = n
        while (nt % i == 0):
            nt = nt // i
        if nt % i == 1:
            ans += 1
        if i ** 2 < n:
            nt = n
            it = n - i
            while (nt % it == 0):
                nt = nt // it
            if nt % i == 1:
                ans += 1
                
if n == 2:
    ans = 1
print(ans)

Submission status: Accepted

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

def AAA(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


B = len(AAA(N-1))-1


C = AAA(N)
for i in range(len(C)):
    nN = N
    if C[i] != 1:
        while nN % C[i] == 0:
            nN = nN / C[i]
        if nN % C[i] == 1:
            ans = ans + 1
            
print(B+ans)

Submission status: Accepted

Solution code:
from math import ceil, sqrt


def main():
    n = int(input())
    if n == 2:
        print(1)
        return
    c = 2 + (int(sqrt(n))**2 == n) + (int(sqrt(n - 1))**2 == (n - 1))
    # print(c)
    for k in range(2, ceil(sqrt(n - 1))):
        m = n % k
        if m > 1:
            # print(k, 0)
            continue
        elif m == 1:
            # print(k, 2)
            c += 2
        else:
            p = n // k
            while p % k == 0:
                p //= k
            if p % k == 1:
                # print(k, 1)
                c += 1
            # else:
                # print(k, 0)
    print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
def factorization(n):
  a = n
  p = 2
  D = {}
  while a != 1:
    cnt = 0
    while a % p == 0:
      cnt += 1
      a //= p
    if cnt != 0:
      D[p] = cnt
    p += 1
    if p * p > n and a != 1:
      D[a] = 1
      break
  return D
DF = factorization(N-1)
DFF = factorization(N)
X = [[i, DFF[i]] for i in DFF]
cnt = 1
S = 1
for i in DF:
  S *= DF[i] + 1
if N != 2:
  cnt += S - 1
Y = 1
for i in X:
  Y *= i[1] + 1
n = len(X)
for k in range(1, Y):
  L = [0 for m in range(n)]
  tmp = k
  for m in range(n):
    L[m] = tmp % (X[m][1] + 1)
    tmp //= (X[m][1] + 1)
  Z = 1
  for m in range(n):
    Z *= X[m][0] ** L[m]
  M = N
  while M % Z == 0:
    M //= Z
  if M % Z == 1:
    cnt += 1
print(cnt-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())

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 get_divisors(num):
    f_divs, l_divs = [], []
    for i in range(1, int(num**0.5)+1):
        if not num % i:
            f_divs.append(i)
            if i != num // i:
                l_divs.append(num // i)
    return f_divs + l_divs[::-1]

f = factorization(n)
num, cnt = zip(*f)
ans = len(get_divisors(n-1))-1

def dfs(idx, x):
    nx = x
    if idx >= len(num):
        if x == 1: return
        k = n
        while k % x == 0: k //= x
        if (k-1) % x == 0:
            global ans
            ans += 1
        return

    for i in range(cnt[idx]+1):
        dfs(idx+1, nx)
        nx *= num[idx]

dfs(0, 1)
print(ans)

Submission status: Accepted

Solution code:
def make_divisors(n):
    divisors = [n]
    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()
    return divisors


def main():
    N = int(input())
    if N == 2:
        print(1)
        exit()
    n = make_divisors(N)
    m = make_divisors(N - 1)
    answer = m[:]
    cnt = len(answer)
    for i in n:
        tmp = N
        while tmp % i == 0:
            tmp //= i
        if tmp % i == 1:
            cnt += 1
            answer.append(i)
    answer.sort()
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

n = int(input())

if n == 2:
    print(1)
    exit()
"""elif n == 3:
    print(2)
    exit()
elif n==4:
    print(3)
    exit()
elif n==5:
    print(3)
    exit()
elif n==9:
    print(5)
    exit()
"""
a = prime_factorize(n-1)
b = [[a[0],1]]

for i in range(1,len(a)):
    if a[i]==b[-1][0]:
        b[-1][1]+=1
    else:
        b.append([a[i],1])

ans = 1
for i in range(len(b)):
    ans *= b[i][1]+1
ans-=1

g = []
for i in range(2,int(math.sqrt(n))+1):
    if n%i==0:
        x = n//i
        y = i
        x,y = min(x,y),max(x,y)
        if 1 in [x,y]:
            continue
        while y%x==0:
            y//=x
        if (y-1)%x==0:
            ans += 1
            g.append(i)

if n not in g:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
"""
NTC here
"""
import sys
inp = sys.stdin.readline
def input(): return inp().strip()
# flush= sys.stdout.flush
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(2**26)
 
def iin(): return int(input())
 
 
def lin(): return list(map(int, input().split()))
 
 
# range = xrange
# input = raw_input
 
def main():
    T = 1
    while T:
        T-=1
        n = iin()
        ans = set()
        ans.add(n)
        def check1(x):
            n1 = x-1
            i = 1
            while i*i<=n1:
                if n1%i==0:
                    ans.add(i)
                    ans.add(n1//i)
                i+=1
        def check2(x):
            n1 = n
            while n1%x==0:
                n1//=x
            n1 = n1%x
            if n1==1 :
                ans.add(x) 
        check1(n)
        i = 2
        while i*i<=n:
            if n%i==0:
                check2(i)
                if i!=n//i:
                    check2(n//i)
            i+=1
        ans = [i for i in ans if i>1]
        print(len(ans))
        # print(ans)






 
 
 
 
main()
 
# threading.Thread(target=main).start()

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

y=make_divisors(n)
z=make_divisors(n-1)

y.sort()


for i in range(1,len(y)):
    v=n

    while v>=y[i]:
        if v%y[i]==0:
            v=v//y[i]
        else:
            v%=y[i]

    if v==1:
        ans+=1

print(ans+len(z)-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

X = {}
N = int(input())


for i in make_divisors(N-1):
    X[i] = 1

for i in make_divisors(N):
    hoge = N
    if i == 1:
        continue
    while hoge % i == 0:
        hoge //= i
    if hoge % i == 1:
        X[i] = 1
    else:
        X[i] = 0

"""
for k,i in X.items():
    if i >= 1:
        print(k)
"""
print(sum(X.values())-1)

Submission status: Accepted

Solution code:
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

def sousa(n, k):
    while n >= k:
        if n % k == 0:
            n = n // k
        else:
            n = n % k
    return n

N = int(input())
cnt = 0

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

divisors = make_divisors(N)
for i in divisors:
    if i == 1: continue
    if sousa(N, i) == 1:
        cnt += 1

lst = factorization(N-1)
tuika = 1
for i in range(len(lst)):
    tuika *= lst[i][1]+1
# cnt += len(make_divisors(N-1))-1
cnt += tuika-1
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

div = set()
for i in range(1, N + 1) :
  if i * i > N : 
    break
    
  if N % i == 0 :
    div.add(i)
    if i != N // i :
      div.add(N // i)

N = N - 1
for i in range(1, N + 1) :
  if i * i > N : 
    break
    
  if N % i == 0 :
    div.add(i)
    if i != N // i :
      div.add(N // i)

def check(x) :
  n = N + 1
  while n >= x :
    if n % x == 0 :
      n //= x
    else :
      n %= x
      
  return n == 1

ret = 0
for x in list(div) :
  if x == 1 : continue
  if check(x) :
    ret += 1
      
print(ret)

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

def div(target, n):
    while target % n == 0:
        target = target // n
    return target

n = int(input())


ans = len(make_divisors(n-1)) - 1
for c in make_divisors(n):
    if c == 1:
        continue
    if div(n, c) % c == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
def getlist2():
    return [int(x) * 100000 for x in input().split()]
import math
import bisect
import heapq
from decimal import Decimal
# from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15

def factorization2(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

# factorization(24)

## [[2, 3], [3, 1]]
##  24 = 2^3 * 3^1

def factorization(n):
    ret = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            ret.append(n // i)
    ret.append(n)
    return ret

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

    if n == 1:
        return True
    else:
        return False
def simulation_answer(n):
    ans = 0
    for i in range(2, n+1):
        if simulation(n, i):
            # print(i)
            ans += 1
    return ans

def submit_answer(n):
    # fcminus = factorization(n - 1)
    ans1 = factorization(n-1)
    # for a, b in fcminus:
    #     ans1 *= (b + 1)

    fc = factorization(n)
    ans2 = 0
    for fact in fc:
        tmp = n
        while (tmp % fact == 0):
            tmp /= fact
        if tmp % fact == 1:
            ans1.append(fact)
        # for power in range(1, b+1):
        #     wari = a**power
        #     while(tmp % wari == 0):
        #         tmp /= wari
        #     # if (n // (a ** power)) == (a ** power) + 1:
        #     if tmp % wari == 1:
        #         ans2 += 1
        #         print(a ** power)

    # print(ans2)
    # for i in range(2, n + 1):
    #     if simulation(n, i):
    #         print(i)
    # return (ans1 + ans2)
    # print(list(set(ans1)))
    return(len(list(set(ans1))))

def main():
    # n = getN()
    # print(factorization(n))
    # print(simulation_answer(n))
    # print(submit_answer(n))
    # for i in range(2, 100000):
    #     if simulation_answer(i) == submit_answer(i):
    #         status = "OK"
    #     else:
    #         status = "NG"
    #
    #         print("{}:  {}".format(i, status))
    #         print("simu: ", simulation_answer(i))
    #         print("sub: ", submit_answer(i))
    n = getN()
    if n == 2:
        print(1)
        return
    else:
        print(submit_answer(n))
        return

if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Accepted

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

def calc(n,k):
    while(n%k==0):
        n = n//k
    n  %= k
    return 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

divisors = make_divisors(n)
divisors += make_divisors(n-1)
divisors = set(divisors)
for i in divisors:
    if(i != 1):
        if( calc(n,i)==1 ):
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())


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)