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 yakusu(n):
    if n == 1:
        return []
    results = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            results.append(i)
            results.append(n // i)
    return list(set(results)) + [n]

N = int(input())
count = 0
for i in yakusu(N):
    NN = N
    while NN >= i:
        if NN % i == 0:
            NN //= i
        else:
            NN %= i
    if NN == 1:
        count += 1
for i in yakusu(N-1):
    NN = N
    while NN >= i:
        if NN % i == 0:
            NN //= i
        else:
            NN %= i
    if NN == 1:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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


divs = make_divisors(N)
cnt = 0

for d in divs:
    if d == 1:
        continue
    rest = N // d
    while rest % d == 0:
        rest //= d
    if (rest - 1) % d == 0:
        cnt += 1

divs2 = make_divisors(N-1)
cnt += len(divs2) - 1

print(cnt)

Submission status: Accepted

Solution code:
import sys

# import bisect
from collections import Counter, deque, defaultdict

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    k = set()

    def divisors(n):
        # 素因数分解

        divisors = []

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

        return divisors

    divisors1 = divisors(n)
    divisors1.sort()

    for d in divisors1[1:]:
        x = n
        while x % d == 0:
            x = x // d
        if x % d == 1:
            k.add(d)

    divisors2 = divisors(n-1)
    divisors2 = set(divisors2)
    k = k.union(divisors2)
    k.discard(1)
    print(len(k))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import sqrt
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

# def solve1(n):
#     ans = []
#     for k in range(2, n+1):
#         tmp = n
#         while tmp % k == 0:
#             tmp = tmp // k
#             if tmp < k:
#                 break
#         tmp = tmp % k
#         if tmp == 1:
#             ans.append(k)
#     return ans, len(ans)

def solve2(n):
    div1 = make_divisors(n-1)
    div2 = make_divisors(n)
    div = list(set(filter(lambda x: x > 1, div1 + div2)))
    ans = []
    for k in div:
        tmp = n
        while tmp % k == 0:
            tmp = tmp // k
            if tmp < k or tmp == 1:
                break
        tmp = tmp % k
        if tmp == 1:
            ans.append(k)
    return len(ans)

print(solve2(n))

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
def pf(x):
  ret={}
  for i in range(2,int(x**0.5)+1):
    while x%i==0:
      ret[i]=ret.get(i,0)+1
      x//=i
  if x>1:
    ret[x]=1
  return ret

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

  divisors.sort()
  return divisors

D1=make_divisors(n)
D2=pf(n-1)
ans=0
cur=1
for i in D2.keys():
  cur*=D2[i]+1
ans+=cur

for i in D1:
  if i!=1:
    nn=n
    chk=False
    while nn%i==0:
      nn//=i
      chk=True
    if chk and nn%i==1:
      ans+=1
print(ans-1)

Submission status: Accepted

Solution code:
n = int(input())


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

    # divisors.sort()
    return divisors


if n == 2:
    print('1')
elif n == 3:
    print('2')
else:
    div = set(make_divisors(n-1))
    div.add(2)
    div.add(n)
    div.remove(1)
    for i in range(2, 41):
        root = round(n ** (1/i))
        if root ** i == n:
            div.add(root)

    for j in make_divisors(n)[1:-1]:
        k = n // j
        while k % j == 0:
            k = k // j
        if k % j == 1:
            div.add(j)
    print(len(div))

Submission status: Accepted

Solution code:
a=int(input())
def div(n):
    div=set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.add(i)
            div.add(n//i)
            if i != n // i:
                div.add(i)
    return div
s=list((div(a)|div(a-1))|div(a+1))
def x(n,k):
  if k==1:
    return False
  else:
    while n>1 and n>k-1:
      if n%k==0:
        n=n//k
      else:
        n=n%k
    if n==1:
      return True
    else:
      return False
ans=0
for i in s:
  if x(a,i):
    ans+=1
    #print(i)
  else:pass
print(ans)

Submission status: Accepted

Solution code:
import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+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())
    r = len(make_divisors(n-1)) - 1
    d = make_divisors(n)
    for i in d:
        if i == 1:
            continue
        if i == 2:
            r += 1
            continue
        t = n
        while t % i == 0:
            t = t // i
        t = t % i
        if t == 1:
            r += 1
    return r
print(main())

Submission status: Accepted

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

n=int(input())

yakusu=[[],[]]
for i in range(2):
    kazu=n-i
    for j in range(1,kazu+1):
        if(j*j>kazu):
            break
        if(kazu%j==0):
            if(j!=1):
                yakusu[i].append(j)
            if(j*j!=kazu):
                yakusu[i].append(kazu//j)
    yakusu[i].sort()

#for i in range(2):
#    print(yakusu[i])


ans=[]

for i in range(2):
    for y in yakusu[i]:
        if(check(n,y)):
            ans.append(y)

ans.sort()
#print(ans)
print(len(ans))

Submission status: Accepted

Solution code:
def main():
    from collections import Counter as ct

    def soinsuu(a):
        yy, j = [], 2
        y = yy.append
        while(a > 1):
            for i in range(j, int(a**0.5)+1):
                if a % i == 0:
                    y(i)
                    a, j = a//i, i
                    break
            else:
                y(a)
                break
        return ct(yy)

    def soinsuu2(a):
        s = {1}
        for i, j in a.items():
            s2 = set()
            for k in range(1, j+1):
                for l in s:
                    s2.add(l*pow(i, k))
            s |= s2
        s.remove(1)
        return s

    n = int(input())

    ans = 0
    s = soinsuu(n)
    s2 = soinsuu2(s)
    for i in s2:
        m = n
        while m % i == 0:
            m //= i
        m -= 1
        if m % i == 0:
            ans += 1

    n -= 1
    ans2 = 1
    for i in soinsuu(n).values():
        ans2 *= i+1
    ans2 -= 1
    print(ans+ans2)


main()

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 = len(make_divisors(N-1)) - 1
divisors = make_divisors(N)
for i in range(1, len(divisors)):
    tmp = N
    d = divisors[i]
    while tmp%d == 0:
        tmp //= d
    if tmp % d == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def m(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=len(m(n-1))-1
A=m(n)
for i in range(1,len(A)):
  s=n
  while s%A[i]==0:
    s=s//A[i]
  if s%A[i]==1:
    ans=ans+1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
def factors(x):
   t=[]
   for i in range(2, int(x**0.5)+1):
       if x % i == 0:
           t.append(i)
           if x//i!=i:
               t.append(x//i)     
   return t
ans=2+len(factors(N-1))
fac=factors(N)
for i in fac:
    n=N
    while n%i==0:
        n=n//i
    n=n%i
    if n==1:
        ans+=1
if N==2:
    print(1)
else:  
    print(ans)

Submission status: Accepted

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

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations
from itertools import accumulate
from math import ceil, sqrt, pi

N = int(input())

def divisors(n) -> list:
    res = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n // i)
    #res = sorted(res)
    return res

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

cnt = defaultdict(int)
for d in div1:
    cnt[d] += 1
for d in div2:
    cnt[d] += 1

arr = list(cnt.keys())
arr.sort()
#print(arr)

answer = 0

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

for a in arr:
    if 2 <= a <= N:
        if check(N, a):
            answer += 1
print(answer)

Submission status: Accepted

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

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

n = int(input())

div_list = divisor(n)
ans = 0

for div in div_list:
    x = calc(n,div)
    if x==1: ans +=1

ans += len(divisor(n-1)) - 1
print(ans)

Submission status: Accepted

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


n = int(input())

res = -1

for i in range(1,int(n**0.5)+1):
    if (n-1)%i == 0:
        if i*i == n-1:
            res += 1
        else:
            res += 2
def divisor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass


pri = divisor(n)
pri.append(n)


for e in pri:
    tmp = n
    while tmp%e == 0:
        tmp = tmp//e
    if tmp%e == 1:
        res += 1

print(res)

Submission status: Accepted

Solution code:
import math


def solve(n):
    if n == 2:
        return 1
    res = 0

    # divisor of n - 1
    m = int(math.sqrt(n - 1))
    for i in range(2, m + 1):
        if (n - 1) % i == 0:
            res += 2
    if m * m == n - 1:
        res -= 1
    res += 1

    # divisor of n
    # n itself
    res += 1
    divisors = []
    m = int(math.sqrt(n))
    for i in range(2, m):
        if n % i == 0:
            divisors.append(i)
            divisors.append(n // i)
    if n % m == 0 and m * m == n:
        divisors.append(m)
    elif n % m == 0:
        divisors.append(m)
        divisors.append(n // m)
    # print(divisors)
    for p in divisors:
        q = n // p
        while q % p == 0:
            q = q // p
        if q % p == 1:
            res += 1
    # print(res)
    return res


def solve_greed(n):
    for p in range(2, n + 1):
        m = n
        while m % p == 0:
            m = m // p
        if m % p == 1:
            print(p)


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(6) == 3
    assert solve(3141) == 13
    assert solve(314159265358) == 9


if __name__ == "__main__":
    test()
    main()

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

if __name__ == "__main__":
    N = int(input())
    A = make_divisors(N)
    cnt = 0
    for a in A[1:]:
        n = N
        while n%a == 0:
            n = n//a
        if n%a == 1:
            cnt += 1
    print(cnt+len(make_divisors(N-1))-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

## [[2, 3], [3, 1]]
##  24 = 2^3 * 3^1
n=int(input())
a=make_divisors(n)
cnt=0
use=set()
for k in a[1:]:
    t=n
    while t%k==0:
        t//=k
    if t%k==1:
        use.add(k)
b=make_divisors(n-1)
for i in b[1:]:
    use.add(i)
print(len(use))

Submission status: Accepted

Solution code:
N = int(input())
#divisor
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_ok(k):
    if(k==1):
        return False
    _N = N
    while(_N>1):
        if(_N%k==0):
            _N//=k
        else:
            _N%=k
            break
    if(_N!=1):
        return False
    else:
        return True

cand = set(make_divisors(N)) | set(make_divisors(N-1))
cnt = 0
for i in list(cand):
    if(is_ok(i)):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
#nの約数列挙
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    ass.sort()
    return ass

n = int(input())
d = divisor(n-1)
#print(d)
ans = len(d)-1
d2 = divisor(n)
#print(d2)
for k in d2:
    if k == 1:
        continue
    s = n
    while s%k == 0:
        if s%k == 0:
            s = s//k
    s = s%k
    if s == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())


@lru_cache(maxsize=None)
def func(n, k):
    if n < k:
        return n
    if n % k == 0:
        return func(n // k, k)
    else:
        # return func(n - k, k)
        return n % k


def test(N):
    cnt = 0
    for k in range(2, N + 1):
        c = func(N, k)
        if c == 1:
            cnt += 1
        print(k, c)
    print(cnt)


def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :rtype: list of int
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret


# test(N)

# k == N - 1 の約数のとき 1 になる
ans = len(get_divisors(N - 1))
for k in get_divisors(N):
    if (N - 1) % k == 0:
        continue
    p = N // k
    if p >= k:
        ans += func(N // k, k) == 1
print(ans)

Submission status: Accepted

Solution code:
def factors(N): #約数を全て求める。ただし、順不同
    from collections import deque
    ret = deque()
    middle = int( N**(1/2))
    for i in range(1, middle):
        if N%i == 0:
            ret.append(i)
            ret.append(N//i)
            
    if N%middle == 0:
        ret.append(middle)
        if middle != N//middle:
            ret.append(N//middle)
    return ret

#import sys
#input = sys.stdin.readline
def main():
    N = int( input())
    ans = 0
    F = factors(N)
    for k in F:
        if k == 1:
            continue
        x = N
        while x%k == 0:
            x //= k
        x %= k
        if x == 1:
            ans += 1
    G = factors(N-1)
    for k in G:
        if k == 1:
            continue
        x = N
        while x%k == 0:
            x //= k
        x %= k
        if x == 1:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    n = int(N**0.5) + 1

    def check(i, N):
        while N%i==0:
            N //= i
            if N%i==1:
                return 1
        return 0

    def yakusuu(N):
        n = int(N**.5)+1
        res1 = []
        res2 = []
        for i in range(1, n):
            if N%i==0:
                res1.append(i)
                if N!=i**2:
                    res2.append(N//i)
        res2.reverse()
        return res1+res2
        
    res = 0

    for i in range(2, n):
        if (N%i)!=1:
            res += check(i, N)
    res += len(yakusuu(N-1))

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def f(x,k,ans):
    if x < k:
        if x == 1:
            ans.append(k)
        return
    if x%k == 0:
        while x%k == 0:
            x //= k
        f(x,k,ans)
    else:
        f(x%k,k,ans)
    return
def divide(x):
    div=[]
    for check in range(1,int(x**0.5)+1):
        if(x%check==0):
            div.append(check)
            div.append(x//check)
    for check in range(1,int((x+1)**0.5)+1):
        if((x+1)%check==0):
            div.append(check)
            div.append((x+1)//check)
    div = list(set(div))
    div.sort()
    return div
def main():
    ans = []
    n = inp()
    Divide = divide(n-1)
    for e in Divide:
        if e == 1:
            continue
        f(n,e,ans)
    print(len(ans))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
N=[n]
import collections
def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a
t=prime_factorize(n-1) # n-1の素因数
c = collections.Counter(t)
w=1
for i in c.values():
  w *= 1+i
w-=1
#print(w)
# wはn-1の約数の個数（1以外）

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

for i in t:
  n=N[0]
  while n%i==0:
    n//=i
  if n%i==1:
    w+=1
print(w)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def factor(n):
    res=[]
    for d in range(1,n+1):
        if d*d>n:break
        if n%d==0:
            res.append(d)
            res.append(n//d)
        if res[-1]==res[-2]:res.pop()
    return res[1:]

def main():
    n=II()
    ff=factor(n)
    ans=len(factor(n-1))
    for k in ff:
        for b in range(1,40):
            pw=pow(k,b)
            if n%pw==0 and (n//pw-1)%k==0:
                ans+=1
                #print(k,(n//pw-1)%k,b)
    print(ans)

main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    if n==2:
        ans=1
    else:
        ans=2
    for i in range(2,int(n**.5)+1):
        if n%i==0:
            k1=i
            k2=n//i
            N=n
            while N%k1==0:
                N//=k1
            if N%k1==1:
                ans+=1
            if k2!=k1:
                N=n
                while N%k2==0:
                    N//=k2
                if N%k2==1:
                    ans+=1
    n-=1
    for i in range(2,int(n**.5)+1):
        if n%i==0:
            if i==n//i:
            	ans+=1
            else:
                ans+=2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
yakusuu = set()
ans = set()
for i in range(1, int((n-1)**(1/2))+1):
    if (n-1) % i == 0:
        yakusuu.add(i)
        yakusuu.add((n-1)//i)

for i in range(1, int(n**(1/2))+1):
    if n % i == 0:
        yakusuu.add(i)
        yakusuu.add(n//i)
yakusuu.remove(1)



for i in yakusuu:
    k = n
    if gcd(i, k) == 1:
        if k % i == 1:
            ans.add(i)
        continue

    k = n
    while k >= i:
        if k % i == 0:
            k //= i
        else:
            if k % i == 1:
                k = 1
            else:
                k = 0
    if k == 1:
        ans.add(i)

print(len(ans))

Submission status: Accepted

Solution code:
import math

N=int(input())
ans=0
L=[]
M=[]
if N==2:
	print(1)
	exit()
for i in range(2,int(math.sqrt(N))+1):
	if N%i==0:
		L.append(i)
		L.append(N//i)
for i in range(2,int(math.sqrt(N))+1):
	if (N-1)%i==0:
		L.append(i)
		L.append(N//i)

X=set(L)
Y=sorted(X)
for i in range(len(Y)):
	if N%Y[i]==1:
		ans+=1
	elif N%Y[i]==0:
		A=N//Y[i]
		while(1):
			if A%Y[i]==1:
				ans+=1
				break
			elif A%Y[i]==0:
				B=A//Y[i]
				if B==1:
					ans+=1
					break
				else:
					A=B
					continue
			else:
				break
print(ans+2)

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.append(n)
    return divisors
#return only >=2

n=int(input())
div=make_divisors(n)
tmp_div=div
ctr=0
#N=K^i(jK+1)
#i>0
for k in div:
  tmp_div=div
  k_i=k #k^i
  while n%(k_i*k)==0:
    k_i*=k
  if (n//k_i)%k==1:
    ctr+=1

#i==0
div=make_divisors(n-1)
for k in div:
  if n%k==1:
    ctr+=1
print(ctr)

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

def mn(n):
    c = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i != 1:
                c += 1
            if i != n // i:
                c += 1
    return c
N = int(input())
r = mn(N-1)
rs = set()
for k in make_divisors(N):
    if k == 1:
        continue
    M = N
    while M%k == 0: 
        M //= k
    if (M-1) % k == 0:
        rs.add(k)
        r += 1

print(r)

Submission status: Accepted

Solution code:
n=int(input())
ans=0
def count_cases(n):
    n-=1
    cur=1
    cnt=0
    while cur*cur<=n:
        if n%cur==0:
            if n//cur!=cur:
                if (n+1)%(n//cur)==1:
                    cnt+=1
#                    print(n//cur)
                if (n+1)%cur==1:
                    cnt+=1
#                    print(cur)
            else:
                if (n+1)%cur==1:
                    cnt+=1
#                    print(cur)
        cur+=1
    return cnt
#count non divisible cases 
ans+=count_cases(n)
#print(ans,end=' ans\n')
#exit()
#count divisible type cases
cur=2
while cur*cur<=n:
    #check if cur,cur**2,cur**3,cur**4 are a valid one
    if n%cur==0:
        num=n
        div=cur
        while num%div==0:
            num//=div
        if num%div==1:
 #           print(div)
            ans+=1
        div=n//cur
        if cur!=(n//cur):
            num=n
            while num%div==0:
                num//=div
 #              print(div)
            if num%div==1:
                ans+=1
    cur+=1
print(1+ans)#extra 1 due to k=n case

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
d=make_divisors(n)[1:]
l=make_divisors(n-1)[1:]

ans=0
for i in d:
    m=n
    while m%i==0:
        m//=i
    if m%i==1:
        ans+=1
print(ans+len(l))

Submission status: Accepted

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

ans=0
def f(x):
    out=set()
    for i in range(1, int(x**(1/2))+1):
        if x%i==0:
            out.add(i)
            out.add(x//i)
    out=list(out)
    out.sort()
    return out[1:]

tmp=f(N)
for K in tmp:
    x=N
    while x>=K:
        if x%K==0:
            x=x//K
        else:
            x=x%K
            
    if x==1:
        ans+=1
        
tmp=f(N-1)
ans+=len(tmp)
print(ans)

Submission status: Accepted

Solution code:
import math
n=int(input())
ans=0
s=set()
s.add(1)
s.add(n)
s.add(n-1)
for i in range(2,math.ceil(math.sqrt(n))+1):
  nn=n
  key=0
  while nn % i ==0:
    nn=nn//i
    key=1
  if nn % i ==1:
    s.add(i)
    if key==0:
      s.add((nn-1)//i)
s.remove(1)
print(len(s))

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

Submission status: Accepted

Solution code:
n = int(input())
lst = set()

for i in range(2, int(n ** (1 / 2)) + 1):
  k = i
  while k <= n * i:
    k *= i
    if n % k == k // i:
      lst.add(i)
      break

for i in range(2, int(n ** (1 / 2)) + 1):
  if n % i == 1:
    lst.add(i)
    lst.add((n - 1) // i)

if n > 2:
  lst.add(n - 1)
lst.add(n)
print(len(lst))

Submission status: Accepted

Solution code:
N = int(input())

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

a.sort()

count=0
for i in a:
    if i!=1:
        M = N
        while M%i==0:
            M//=i
        if M%i == 1:
            count+=1

b = []
for i in range(1,int((N-1)**0.5)+1):
    if i**2 == N-1:
        b.append(i)
    elif (N-1)%i==0:
        b.append(i)
        b.append((N-1)//i)


for i in b:
    if N%i==1:
        count+=1


print(count)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
count=0
for i in range(2,10**6+1):
    num=1
    while num<=n:
        if n%num==0:
            if (n//num-1)%i==0:
                count+=1
        num=num*i
if n>10**6:
    count+=1
for i in range(1,10**6+1):
    if (n-1)%i==0:
        if (n-1)//i>10**6:
            count+=1
print(count)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
inputt = lambda: range(int(input()))
inputn = lambda n = 1: range(n)
inputi = lambda: map(int, input().split())
inputl = lambda: list(inputi())
from math import *
from heapq import *
from bisect import *
from operator import *
from functools import reduce, lru_cache
from collections import Counter, defaultdict
from builtins import *

def factor(n):
    i, l = 2, []
    while i * i <= n:
        if not n % i:
            l.append(i)
            n //= i
        else:
            i += 1
    l.append(n)
    return l

def T(n, k):
    while not n % k:
        n //= k
    return n % k == 1

N, = inputi()
R = reduce(mul, [v + 1 for v in Counter(factor(N - 1)).values()], 1) - 1
D = {1}
for n in factor(N):
    D |= {d * n for d in D}
for d in D:
    if d != 1 and T(N // d, d):
        R += 1
if N == 2:
    print(1)
else:
    print(R)

Submission status: Accepted

Solution code:
def divisor(n):
    x=[]
    y=[]
    for i in range(1,int(n**.5)+1):
        if n%i==0:
            x.append(i)
            y.append(n//i)
    if y[-1]==x[-1]:
        y=y[:-1]
    return x+y[::-1]
N=int(input())
a=0
d=divisor(N)
for K in d:
    if K==1:continue
    n=N
    while n>=K:
        if n%K==0:
            n//=K
        else:
            n%=K
    if n==1:
        a+=1
if N-1>1 and N-1 not in d:
    a+=len(divisor(N-1))-1
print(a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
i = 2
ps = []
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
ps = make_divisors(N)
ps2 = make_divisors(N - 1)
res = 0
for x in (ps + ps2):
  if x == 1: continue
  y = N + 0
  while y % x == 0: y //= x
  if y % x == 1: res += 1
print(res)