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:
from sys import stdin, setrecursionlimit


def check(n, k):
    tmp = n
    while tmp % k == 0:
        tmp = tmp // k
    return tmp % k == 1


def main():
    input = stdin.buffer.readline
    n = int(input())
    ans = 1
    if n > 2:
        ans += 1
    for i in range(2, int((n - 1) ** 0.5) + 1):
        if (n - 1) % i == 0:
            ans += 1
            if i != (n - 1) // i:
                ans += 1
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            if check(n, i):
                ans += 1
            if check(n, n // i) and i != n // i:
                ans += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

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

def check(N, k):
    if k<2:
        return False
    N //= k
    while N:
        if (N-1)%k==0:
            return True
        if N%k:
            return False
        N //= k

for k in range(1, int(N**0.5)+1):
    if (N-1)%k==0:
        ans.add(k)
        ans.add((N-1)//k)
    if N%k==0:
        if check(N, k):
            ans.add(k)
        if check(N, N//k):
            ans.add(N//k)

ans.remove(1)
print(len(ans))

Submission status: Accepted

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

def check(N, k):
    if k<2:
        return False
    N //= k
    while N:
        if (N-1)%k==0:
            return True
        if N%k:
            return False
        N //= k
    return False


for k in range(1, int(N**0.5)+1):
    if (N-1)%k==0:
        k1, k2 = k, (N-1)//k
        ans.add(k1)
        ans.add(k2)
    if N%k==0:
        k1, k2 = k, N//k
        if check(N, k1):
            ans.add(k1)
        if check(N, k2):
            ans.add(k2)

ans.remove(1)
print(len(ans))

Submission status: Accepted

Solution code:
n = int(input())

if n == 2:
  count = 1
else:
  count = 2
divisor = []

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

d = 2
while d * d < n:
  if n % d == 0:
    divisor.append(d)
    divisor.append(n // d)
  d += 1
if d * d == n:
  divisor.append(d)

for d in divisor:
  tmp = n
  while tmp % d == 0:
    tmp //= d
  if tmp % d == 1:
    count += 1

print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
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

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N = inputI()

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

def Base_10_to_n(X, n):
  if (int(X/n)):
     return Base_10_to_n(int(X/n), n)+" "+str(X%n)
  return " "+str(X%n)

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

  # divisors.sort()
  return divisors

d = make_divisors(N)+make_divisors(N-1)



ans = 0
for x in d:
  l = list(Base_10_to_n(N, x).split())
  for i in l[::-1]:
    if i == "0":
      continue
    else:
      if i == "1":
        ans += 1
        break
      else:
        break

print(ans+2)

Submission status: Accepted

Solution code:
import queue

N = int(input())

def common_divisors(n):
    i = 1
    res = []
    while i*i <= n:
        if n % i == 0:
            res.append(i)
            res.append(n//i)
        if i*i == n:
            res.pop()
        i += 1
    return res

ans = 0
ans += len(common_divisors(N-1))-1

for i in common_divisors(N):
    if i == 1:
        continue
    n = N
    while n % i == 0:
        n /= i
    if n % i == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
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())
N_div = make_divisors(N)[1:]
N1_div = make_divisors(N-1)[1:]

ans = len(N1_div)

for i in N_div:
    n = N
    while n % i == 0:
        n //= i
    if n % i == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def check(n, i):
    while n >= i and n % i == 0:
        n //= i
    return n % i == 1

def main():
    N = int(input())
    i = 2
    r = set()
    while i * i <= N:
        if N % i == 0:
            if check(N, i):
                r.add(i)
            if check(N, N // i):
                r.add(N // i)
        elif N % i == 1:
            r.add(i)
            if check(N, N // i):
                r.add(N // i)
        i += 1
    if N > 2:
        r.add(N - 1)
    r.add(N)
    return len(r)

print(main())

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
import sys
sys.setrecursionlimit(10**7)
def func(N,d):
    if d==1:
        return False
    while N>1:
        if N%d==0:
            N//=d
        else:
            if (N-1)%d==0:
                N=1
            else:
                N=0
    return True if N==1 else False

ans=len(set(make_divisors(n-1)))-1
l=set(make_divisors(n))
for li in l:
    if func(n,li):
        ans+=1
print(ans)
#print(ans)

Submission status: Accepted

Solution code:

def solve1(n):
    # n = k ^ a
    res = []
    for i in xrange(1, 100):
        u = int(pow(n, 1.0 / i) + 0.1)
        if u ** i == n:
            res.append(u)
    return set(res)

def solve2(n):
    # n = a * k + 1
    m = n - 1

    i = 1
    res = set()
    while i * i <= m:
        if m % i == 0:
            res.add(i)
            res.add(m / i)
        i += 1
    return res ^ set([1])

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

def brute_force(n):
    res = []
    for i in xrange(2, n + 1):
        m = n
        while m % i == 0:
            m /= i
        m %= i
        if m == 1:
            res.append(i)
    # print res
    return len(res)

def solve(n):
    s1 = solve1(n)
    s2 = solve2(n)
    s3 = solve3(n)
    # print sorted(s1 | s2 | s3)
    return len(s1 | s2 | s3)

assert solve(6) == 3
assert solve(3141) == 13
assert solve(314159265358) == 9

assert solve(10 ** 12)

import random
for i in xrange(2, 100):
    assert brute_force(i) == solve(i)

n = int(raw_input())
print solve(n)

Submission status: Accepted

Solution code:

N = int(input())

def prime_cnt(N):
    # 約数列挙(1,N)も含まれる
    prime, i = set([2]), 1
    while i * i <= N:
        if N % i == 0:
            prime.add(i)
            prime.add(N//i)
        i += 1
    prime.remove(1)
    return prime
import math
ans = 0
ans = prime_cnt(N-1)
p = prime_cnt(N)
for i in p:
    n = N
    while n % i == 0:
        n /= i
    if (n-1) % i == 0:
        ans.add(i)
#print(sorted(list(ans)))
print(len(ans))

Submission status: Accepted

Solution code:
def divisor(n):
  list1 = []
  for i in range(1, int(n ** (0.5)) + 1):
    if n % i == 0:
      list1.append(i)
      list1.append(int(n / i))
  list1 = list(set(list1))
  return len(list1) - 1

def function(n):
  ans = 0
  if n >= 2:
    ans += 1
  for i in range(2, int(n ** (0.5)) + 1):
    m = n
    if m % i == 0:
      while m % i == 0:
        m = int(m / i)
      if m % i == 1:
        ans += 1
  ans += divisor(n - 1)
  return ans
n = int(input())
print(function(n))

Submission status: Accepted

Solution code:
import numpy as np

def divisors(N):
    return sorted(sum((list({n, N // n}) for n in range(1, int(N ** 0.5) + 1) if not N % n), []))

def prime_factorize_dict(n):
    d = dict()
    while not n & 1:
        d[2] = d.get(2, 0) + 1
        n >>= 1
    f = 3
    while f * f <= n:
        if not n % f:
            d[f] = d.get(f, 0) + 1
            n //= f
        else:
            f += 2
    if n != 1:
        d[n] = d.get(n, 0) + 1
    return d

N = int(input())
count = 0
for n in divisors(N)[1:]:
    M = N
    while not M % n:
        M //= n
    count += M % n == 1
fact_Nm1 = np.array(list(prime_factorize_dict(N - 1).values()), dtype=np.int32)
print(count + np.prod(fact_Nm1 + 1) - 1)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

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

def main():
    N = I()
    cnt = 0
    if N == 2:
        print(1)
        return
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        while True:
            if cpN % n == 0:
                cpN = cpN // n
            else:
                break
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

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

def main():
    N = I()
    cnt = 0
    if N == 2:
        print(1)
        return
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        while True:
            if n == 1:
                break
            if cpN % n == 0:
                cpN = cpN // n
            else:
                break
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

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

def main():
    N = I()
    cnt = 0
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    if N == 2:
        print(1)
        return
    for n in yakusu:
        cpN = N
        while True:
            if n == 1:
                break
            if cpN % n == 0:
                cpN = cpN // n
            else:
                break
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

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

def main():
    N = I()
    cnt = 0
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        while True:
            if n == 1:
                break
            if cpN % n == 0:
                cpN = cpN // n
            else:
                break
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

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

def main():
    N = I()
    cnt = 0
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        loop = 0
        while True:
            loop += 1
            if loop > 100:
                break
            if cpN % n == 0:
                cpN = cpN // n
            else:
                break
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()

Submission status: Accepted

Solution code:
n=int(input())

cnt=0
import math

result=set([])

for i in range(1,int(math.sqrt(n-1))+1):
    if (n-1)%i==0:
        for item in [i,(n-1)//i]:
            if item!=1:result.add(item)

for i in range(1,int(math.sqrt(n))+1):
    if n%i==0:
        for item in [i,n//i]:
            if item!=1:
                N=n
                while N%item==0:N=N//item
                if N==1:result.add(item)
                elif N%item==1:result.add(item)

print(len(result))

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N=int(input())
    Nd=set()
    for n in range(1,int(N**0.5)+1):
        if N%n==0:
            Nd.add(n)
            Nd.add(N//n)
    N1d=set()
    for n in range(1,int((N-1)**0.5)+1):
        if (N-1)%n==0:
            N1d.add(n)
            N1d.add((N-1)//n)
    for d in Nd:
        if d==1: continue
        n=N
        while n%d==0: n//=d
        if n%d==1: N1d.add(d)
    print(len(N1d)-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
num = int(input())
n = num
num -= 1
result = 1
for i in range(2, int(pow(num, 0.5))+1):
    c = 0
    while num%i==0:
        num //= i
        c += 1
    if c>0:
        result *= c+1

if num > 1:
    result *= 2
result -= 1

r = set()
for i in range(2, int(pow(n, 0.5))+1):
    num = n
    if num%i==0:
        r.add(i)
        r.add(n//i)
r.add(n)
for i in r:
    num = n
    while num%i==0:
        num //= i
    if num%i == 1:
        result += 1

print(result)

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

a = make_divisors(N)
b = make_divisors(N-1)
cnt = 0
for i in a:
    if i == 1:
        continue
    k = N
    while k % i == 0:
        k //= i
    if k % i == 1:
        cnt += 1
ans = len(b) - 1 + cnt
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

def divisor(N):
    res = []

    for i in range(1, int(math.sqrt(N)) + 1):
        if N % i != 0:
            continue

        res.append(i)
        if i * i != N:
            res.append(N/i)
    
    return res

N = I()

ans = 0
for x in divisor(N):
    if x == 1:
        continue
    
    tmp = N
    while tmp % x == 0:
        tmp /= x
    tmp %= x

    if tmp == 1:
        ans += 1

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

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = [2]
        for j in range(4, m, 2):
            a[j] = False
        for i in range(3, m, 2):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False
        self.ds_memo = {}
        self.ds_memo[1] = set([1])

    def is_prime(self, n):
        return self.A[n]

    def division(self, n):
        d = collections.defaultdict(int)
        for c in self.T:
            while n % c == 0:
                d[c] += 1
                n //= c
            if n < 2:
                break
        if n > 1:
            d[n] += 1
        return d.items()

    # memo
    def divisions(self, n):
        if n in self.ds_memo:
            return self.ds_memo[n]

        for c in self.T:
            if n % c == 0:
                rs = set([c])
                for cc in self.divisions(n // c):
                    rs.add(cc)
                    rs.add(cc * c)
                self.ds_memo[n] = rs
                return rs

        rs = set([n])
        self.ds_memo[n] = rs
        return rs


def main():
    n = I()

    pr = Prime(10**12)
    d = list(pr.division(n))
    r = 0
    l = len(d)
    for i in range(1, 2**l):
        t = [d[j] for j in range(l) if 2**j & i]
        m = min(map(lambda x: x[1], t))
        ok = True
        for k,v in t:
            if v % m > 0:
                ok = False
                break
        if not ok:
            continue
        for j in range(1,m+1):
            if m % j > 0:
                continue
            mk = m // j
            u = 1
            for k,v in t:
                u *= k**((v//m)*mk)
            nn = n
            while nn % u == 0:
                nn //= u
            if nn % u == 1:
                r += 1
            # print("u",u,j,nn,r)

    d = pr.division(n-1)
    # print("d",d)
    k = 1
    for _,v in d:
        k *= v + 1
    r += k - 1

    return r

print(main())

Submission status: Accepted

Solution code:
def divisor(n):
    res = []
    
    i = 1
    while i*i <= n:
        if not n % i:
            res.append(i)
            if (i*i != n): res.append(n//i)     
        
        i += 1
        
    return res

N = int(input())
ans = 0

for d in divisor(N):
    if d == 1: continue
    n = N
    
    while not n % d:
        n //= d
        
    if n%d == 1: ans += 1
    
print(ans + len(divisor(N-1))-1)

Submission status: Accepted

Solution code:
N = int(input())

def f(N, i):
    if i == 1:
        return False
    while N%i == 0:
        N //= i
    if N%i == 1:
        return True
    else:
        return False
        
ans = 0
i = 1
while i <= N**0.5:
    if N%i > 0:
        i += 1
        continue
    if f(N, i):
        ans += 1
    if i%(N//i) == 1:
        ans += 1
    i += 1

i = 1
while i <= (N-1)**0.5:
    if (N-1)%i > 0:
        i += 1
        continue
    if N%i == 1 and N//i != i:
        ans += 1
    if N%((N-1)//i) == 1:
        ans += 1
    i += 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())
ans = 0
divs = make_divisors(N)
divs = [x for x in divs if x > 1]
for k in divs:
    x = N
    while x % k == 0:
        x //= k
    if x % k == 1:
        ans += 1

divs = make_divisors(N - 1)
divs = [x for x in divs if x > 1]
ans += len(divs)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())


def factor(n):
    res=set()
    for i in range(2,int(n**(1/2))+10):
        if n%i == 0:
            res.add(i)
            res.add(n//i)

    res.add(n)
    res.discard(1)
    return list(res)

ans = 0

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


for k in factor(n):
    n2=n
    if k==1:
        continue
    while n2%k==0:
        n2//=k
    if n2%k == 1:
        ans +=1
        

print(ans)

Submission status: Accepted

Solution code:
# 1は除外
# ・N-1の約数は全て対象
# ・Nの約数でsqrt(N)以下の数について、Nで割れなくなるまで割って、最後にあまりが1になればOK
# ・N自身は必ず対象
# これを足し合わせる

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
  
# N-1の約数の個数
ans = len(make_divisors(N-1)) - 1

def check(n,x):
  # xで割った余りがxの倍数でなくなるまでxで割る
  # xの倍数でなくなったときにxで割って1余ればOK
  while n % x == 0:
    n //= x
  return (n % x == 1)

# Nの約数で2以上sqrt(N)以下の数
for i in range(2,int(N ** 0.5) + 1):
  if N % i == 0:
    if check(N,i):
      ans += 1

# N自身も対象
ans += 1

print(ans)

Submission status: Accepted

Solution code:
# 1は除外
# ・N-1の約数は全て対象
# ・Nの約数で、sqrt(N)以下であればOK　ただしN自身は対象
# これを足し合わせる

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
  
# N-1の約数の個数
ans = len(make_divisors(N-1)) - 1

def check(n,x):
  # xで割った余りがxの倍数でなくなるまでxで割る
  # xの倍数でなくなったときにxで割って1余ればOK
  while n % x == 0:
    n //= x
  return (n % x == 1)

# Nの約数で2以上sqrt(N)以下の数
for i in range(2,int(N ** 0.5) + 1):
  if N % i == 0:
    if check(N,i):
      ans += 1

# N自身も対象
ans += 1

print(ans)