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 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 sorted(divisors) 
n = int(input())
ans = len(divisors(n-1))-1;
for k in divisors(n)[1:]:
    boz = n
    while (n % k == 0):
        n = n//k
    if (n % k == 1):
	    ans += 1
    n = boz
print(ans)

Submission status: Accepted

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

N = int(input())

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

for k in divisors(N)[1:]:
    N_ = N
    while N_ % k == 0:
        N_ = N_//k
    if N_ % k == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
if n==2:
    count=1
else:
    count=2
for i in range(2,int(n**0.5)+1):
    if n%i==0:
        k=n//i
        while k>0:
            if k%i==0:
                k=k//i
            else:
                if k%i==1:
                    count+=1
                break
    elif (n-1)%i==0:
        count+=1
        if i!=(n-1)//i:
            count+=1
print(count)

Submission status: Accepted

Solution code:
# 約数を全部列挙する関数
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:  # 9の約数の場合、3*3で割る方も割られる方も同じ数のため、こういう組み合わせを除外。12の約数を求める場合3がもとまったら、4も約数。 int型で返すため, //で計算。
                divisors.append(n // i)
    return sorted(divisors)


N = int(input())

# NがKで一度も割れない場合, 最終的に1になるには、NmodK=1のため, N=aK+1と表される。そのため、K=N-1/aのため、Kは1を除く、N-1の全ての約数
count = len(divisors(N - 1)) - 1

for K in divisors(N)[1:]:
    N_ = N
    while N_ % K == 0:
        N_ = N_ // K
    N_ = N_ % K
    if N_ == 1:
        count += 1

print(count)

Submission status: Accepted

Solution code:
def find_divisors(n):
    divisors = set()
    
    div = 1
    while div ** 2 <= n:
        if n % div == 0:
            divisors.add(div)
            divisors.add(n // div)
        div += 1
    
    return divisors


def main():
    n = int(input())
    
    res = 0
    
    for k in find_divisors(n) - {1}:
        t = n
        while t % k == 0:
            t //= k
        if t % k == 1:
            res += 1
    
    res += len(find_divisors(n - 1)) - 1
    
    print(res)


main()

Submission status: Accepted

Solution code:
N = int(input())
 
def make_devision(n):
  lst = []
  for i in range(1, int(n**0.5) + 1):
    if n % i == 0:
      lst.append(i)
      if i != n // i:
        lst.append(n // i)
  return lst
 
def calc(n, k):
  if n % k == 0:
    return calc(n // k, k)
  elif n < k:
    return n
  else:
    return calc(n % k, k)
 
ans = make_devision(N-1)
 
for i in make_devision(N):
  if i == 1:
    continue
  if calc(N, i) == 1:
    ans.append(i)
    
print(len(ans)-1)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline
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)
    return divisors

def main():
    N=int(input())
    ret=0
    if N==2:
        ret=1
    else:
        div=make_divisors(N)
        div=div+make_divisors(N-1)
        div.append(N)
        div.append(N-1)
        for k in div:
            n=N
            while n%k==0:
                n=n//k
            ret += n%k==1
        if N==2:
            ret = 1
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

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

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

for i in range(2, int(n ** 0.5) + 1):
    if n % i == 0:
        k = i
        temp = n
        while temp % k == 0:
            temp //= k
        if temp % k == 1:
            ans.add(k)
        k = n // i
        temp = n
        while temp % k == 0:
            temp //= k
        if temp % k == 1:
            ans.add(k)

print(len(ans) + 2)

Submission status: Accepted

Solution code:
import sys
import math
N = int(input())
def solve(num):
    d = math.floor(num**(1/2))
    for i in range(1,d+1):
        if num % i == 0:
            yield [i,num//i]

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

cnt = 0
for a,b in solve(N-1):
    if a == b:
        cnt += 1
    else:
        cnt += 2

cnt -= 1

for s in solve(N):
    if s[0] == s[1]:
        s.pop()
    for a in s:
        if a == 1:
            continue

        tmp = N
        while True:
            tmp,m = divmod(tmp, a)
            if m == 0:
                continue
            elif m == 1:
                cnt += 1
            break

print(cnt)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

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

ans = make_devision(N-1)

for i in make_devision(N):
  if i == 1:
    continue
  if calc(N, i) == 1:
    ans.append(i)
    
print(len(ans)-1)

Submission status: Accepted

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

def f(n):
  return divisor(n)[1:]

def solve(n):
  ans=f(n-1)
  for k in f(n):
    N=n
    while N>=k:
      if N%k==0:N=N//k
      else:N=N%k
    if N==1:ans+=k,
  print(len(ans))
  return 0

solve(int(input()))

Submission status: Accepted

Solution code:
def MI():return map(int,input().split())
def LI():return list(MI())

def factorization(n):
  arr=[]
  temp=n
  for i in range(2,int(n**0.5)+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=[]
for k in make_divisors(n):
  NN=int(n)
  while NN>=k:
    if NN%k==0:
      NN=NN//k
    else:
      NN=NN%k
  if NN==1:l+=k,

ll=(l+make_divisors(n-1))

print(len(ll))

Submission status: Accepted

Solution code:
from math import sqrt

N = int(input())


def f(x):
    n = N
    while n % x == 0:
        n //= x
    return n % x == 1


ans = 1
for k in range(2, int(sqrt(N)) + 1):
    res = N % k
    if res == 0:
        k1, k2 = k, N // k
        ans += 1 if f(k1) else 0
        ans += 1 if k1 != k2 and f(k2) else 0
    elif res == 1:
        ans += 1 if k == (N - 1) // k else 2
if N >= 3:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:


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

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

    def isqrt(n):
        x = n
        y = (x + 1) // 2
        while y < x:
            x = y
            y = (x + n // x) // 2
        return x

    # N = K^a * (bK + 1)
    # if a == 0


    ans = 1 # i == N-1
    for i in range(2, isqrt(N-1)+1):
        if (N-1) % i == 0:
            ans += 1
            if i != (N-1) // i:
                ans += 1
    
    # if a >= 1:
    divs = [N]
    for i in range(2, isqrt(N)+1):
        if N % i == 0:
            divs.append(i)
            j = N // i
            if i != j:
                divs.append(j)
    
    for div in divs:
        M = N
        while M % div == 0:
            M //= div
        if M % div == 1:
            ans += 1
    
    if N == 2:
        ans = 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def divisor(n):
  ass=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      ass.append(i)
      if i!=n//i:ass.append(n//i)
  return ass
n=int(input())
ans=len(divisor(n-1))-1
for i in divisor(n):
  if i==1:continue
  m=n
  while m%i==0:m//=i
  if m%i==1:ans+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

def divisior(n):
    a = []
    i = 1
    while (i*i <= n):
        if n%i == 0:
            a.append(i)
            if (i*i != n): a.append(n//i)
        i += 1
    return a

ans = 0
a = divisior(n)

for x in a:
    if x == 1: continue
    tmp = n
    while (tmp%x == 0): tmp = tmp//x
    if (tmp%x == 1) : ans += 1

b = divisior(n-1)

ans = ans + len(b) -1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

def divisior(n):
    a = []
    i = 1
    while (i*i <= n):
        if n%i == 0:
            a.append(i)
            if (i*i != n): a.append(n//i)
        i += 1
    return a

ans = 0
a = divisior(n)

for x in a[1:]:
    tmp = n
    while (tmp%x == 0): tmp = tmp//x
    if (tmp%x == 1) : ans += 1

b = divisior(n-1)

ans = ans + len(b) -1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

def get_divisors(n):
    result = []
    for i in range(1, int(n**.5)+1):
        if n % i == 0:
            result.append(i)
            if n != i ** 2:
                result.append(n // i)
    result.sort()
    return result

c = 0
for number in get_divisors(n)[1:]:
    tmp = n
    while tmp % number == 0:
        tmp //= number
    if tmp % number == 1:
        c += 1

c += len(get_divisors(n-1)) - 1
print(c)

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())
d1 = make_divisors(N)
d2 = make_divisors(N - 1)

ans = len(d2) - 1
for n in d1:
    if n == 1:
        continue
    n2 = N
    while n2 % n == 0:
        n2 //= n
    if n2 % n == 1:
        if n not in d2:
            ans += 1

print(ans)

Submission status: Accepted

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

def yakusu(A):
  arr = []
  limit = int(math.sqrt(A))
  for i in range(2,limit+1):
    if A % i == 0:
      arr.append(i)
      if i != A // i:
        arr.append(A//i)
  arr.append(A)
  arr.sort()
  return(arr)

yakusu_N = yakusu(N)
yakusu_N1 = yakusu(N-1)


      
def ope(a,N):
  while True:
    if N % a == 0:
      N = N / a
      if N == 1:
        return 1
        break
    else:
      N = N % a
      if N != 1:
        return 0
        break
      else :
        return 1
        break



count = 0 
for i in yakusu_N:  
  if ope(i,N) == 1:
    count += 1
if N != 2:
  print(count + len(yakusu_N1))
else:
  print(1)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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


n = int(input())
a, b, ans = make_divisors(n), make_divisors(n-1), 0
for i in range(1, len(a)):
    tmp = n
    while tmp % a[i] == 0:
        tmp = tmp // a[i]
    if (tmp-1) % a[i] == 0:
        ans += 1
ans += len(b)
print(ans-1)

Submission status: Accepted

Solution code:
def divisor(n):
  ass=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      ass.append(i)
      if i!=n//i:ass.append(n//i)
  return ass
n=int(input())
ans=len(divisor(n-1))-1
for i in divisor(n):
  if i==1:continue
  m=n
  while m%i==0:m//=i
  if m%i==1:ans+=1
print(ans)

Submission status: Accepted

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

n = int(input())
l,m,ans = yakusu(n),yakusu(n-1),0
for i in range(1,len(l)):
    a = n
    while a % l[i] == 0:
        a = a // l[i]
    if (a-1) % l[i] == 0:
        ans += 1
ans += len(m)
print(ans-1)

Submission status: Accepted

Solution code:
def divisors(n):
  small = []
  large = []
  i = 1
  while i * i <= n:
    if not n % i:
      small.append(i)
      large.append(n // i)
    i += 1
  if small[-1] == large[-1]:
    large.pop()
  return small + large[::-1]

n = int(input())
res = set(divisors(n - 1))
res.remove(1)

for d in divisors(n):
  if d == 1:
    continue
  now = n
  # simulation
  while not now % d:
    now //= d
  if now % d == 1:
    res.add(d)

print(len(res))

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-1)
l2=make_divisors(n)[2:]
for i in l2:
  j=n/i
  while j%i==0:
    j/=i
  if j%i==1 and n/i not in l1:
    l1.append(n/i)
print(len(l1))

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict, deque
from math import ceil, factorial
from fractions import gcd
import sys
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10**9+7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


def get_divisor(n):
    divs = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divs.add(i)
            divs.add(n // i)
    return divs


n = ii()
ans = 0

# K が N の約数のとき
for x in get_divisor(n):
    if x == 1:
        continue
    tmp = n
    while tmp % x == 0:
        tmp //= x
    if tmp % x == 1:
        ans += 1

# K が N の約数でないとき
# 1 は除く
ans += len(get_divisor(n-1)) - 1

print(ans)

Submission status: Accepted

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

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

def solve_slow(N):
    def f():
        ans = 0
        for i in range(2, N+1):
            if div(N, i) % i == 1:
                yield i
    return set(f())

def solve(N: int):
    from itertools import takewhile
    def f():
        for i in takewhile(lambda x: x*x<=N-1, range(1, N)) :
            if (N - 1) % i == 0:
                yield i
                yield (N-1)//i
    def g():
        for i in takewhile(lambda x: x*x<=N, range(2, N)) :
            if N % i == 0:
                if div(N, i) % i == 1:
                    yield i
                if div(N, N // i) % (N // i) == 1:
                    yield N // i
        yield N
    return set(g()) | set(f()) - set([1])

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    print(len(solve(N)))

def test():
    for i in range(2, 1000):
        if solve(i) != solve_slow(i):
            print(i, solve(i), _solve(i),)

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

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())
ans = len(make_divisors(N-1))-1
a = make_divisors(N)[1:]
for x in a:
    n = N
    while n%x == 0:
        n //= x
    if n%x == 1:
        ans += 1
print (ans)

Submission status: Accepted

Solution code:
# 素因数分解

N=int(input())
cand=[]

def check(N0,K0):
    if N0%K0==0:
        return check(int(N0/K0),K0)
    elif N0%K0==1:
        return 1
    else:
        return 0

def check0(N0,K0):
    while N0%K0==0:
        N0=int(N0/K0)
    if N0%K0==1:
        return 1
    else:
        return 0

# N-1の約数の数
for i in range(2,int((N-1)**0.5)+1):#O(N**0.5)
    if (N-1)%i==0:
        cand.append(i)
        if i!=int((N-1)/i):
            cand.append(int((N-1)/i))
if N>2:
    cand.append(N-1)

# Nの約数
for i in range(2,int(N**0.5)+1):#O(N**0.5)
    if N%i==0:
        cand.append(i)
        if i!=int(N/i):
            cand.append(int(N/i))
cand.append(N)

#print(cand)
count=0
for i in range(len(cand)):
    if check(N,cand[i]):
        count+=1

print(count)

Submission status: Accepted

Solution code:
n = int(input())
a = [n]
if n != 2:
    a.append(n - 1)

def div_(N, k):
    while N % k == 0:
        N /= k
    if N % k == 1:
        a.append(k)

for k in range(2, int(n ** 0.5) + 1):
    if n % k == 0:
        div_(n,k)
        if k != n / k:
            div_(n, n // k)

    if (n - 1) % k == 0:
        a.append(k)
        if k != (n - 1) / k:
            a.append((n - 1) // k)

print(len(a))

Submission status: Accepted

Solution code:
n = int(input())
ans = 0
def factorize(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

def check(num, mod):
    if num % mod == 1:
        return 1
    elif num % mod == 0:
        num = num / mod
        return check(num, mod)
    else:
        return 0


nfct = factorize(n)
n_1fct = factorize(n - 1)
if n_1fct != [1]:
  ans += len(n_1fct)
for mod in nfct:
  ans += check(n,mod)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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):
    if N % k != 0:
        continue

    x = N
    while x % k == 0:
        x //= k

    if x % k == 1:
        ans.append(k)

print(len(set(ans)))

Submission status: Accepted

Solution code:
n = int(input())


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


def count(n):
    total = 0
    cands = set([n, n-1])
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cands.add(i)
            cands.add(n // i)
    for i in range(2, int(n ** 0.5) + 1):
        if (n-1) % i == 0:
            cands.add(i)
            cands.add((n - 1) // i)
    for k in cands:
        if k == 1:
            continue
        if check(n, k) == 1:
            total += 1
    return total


print(count(n))

Submission status: Accepted

Solution code:
n = int(input())
n_ = n-1
a = [n]
if n_ == 1:
    a_ = []
else:
    a_ = [n_]
    
for i in range(2,int(n**0.5//1+1)):
    if n%i == 0:
        a.append(i)
        if n/i != i:
            a.append(n/i)
    if n_%i == 0:
        a_.append(i)
        if n_/i != i:
            a_.append(n_/i)

ans = len(a_)
for i in a:
    num = n
    while num%i == 0:
        num /= i
    if num % i == 1:
        ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input()) 
times = 0

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
    
times = len(make_divisors(n - 1))
a = make_divisors(n)

for i in a:
    tmp = n // i
    if tmp == 1:
        times += 1 
        continue
    while tmp % i == 0:
        tmp = tmp // i
    if tmp % i == 1:
        times += 1 
    
print(times if n != 2 else 1)

Submission status: Accepted

Solution code:
n = int(input())

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 tester(n, k):
    if k == 1:
        return False

    temp = n
    while temp % k == 0:
        temp /= k

    if temp % k == 1:
        return True
    else:
        return False

answer = []
for i in (divisor(n - 1) + divisor(n)):
    if tester(n, i):
        answer.append(i)

print(len(answer))

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

cnt = len(make_divisors(n-1))-1
base = make_divisors(n)
for x in base[1:]:
    org = n
    while org % x == 0:
        org = org / x
    if org % x == 1:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
def make_divisors(n):
    div=[n]
    for i in range(2,-int(-n**0.5//1)):
        if n%i==0:
            div.append(i)
            div.append(n//i)
    if n%(n**0.5)==0:
        div.append(int(n**0.5))
    div.sort()
    return div

n=int(input())
if n>2:
    ans=make_divisors(n-1)
else:
    ans=[]
for i in make_divisors(n):
    a=n
    while a%i==0:
        a=a//i
    if a%i==1:
        ans.append(i)
print(len(ans))

Submission status: Accepted

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

#output
#ある整数nの素因数を列挙
import math
from collections import Counter
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

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 sub_div(n, k):
    if k == 1:
        return n
    while n >= k:
        if n % k == 0:
            n = n//k
        else:
            n = n % k
    return n

a = Counter(prime_factors(N))
b = Counter(prime_factors(N-1))
c = make_divisors(N)

answer = 1
for value in b.values():
    answer *= (value+1)

answer -= 1

for x in c:
    if sub_div(N, x) == 1:
        answer += 1

print(answer)

Submission status: Accepted

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

for k in range(2, int(n ** 0.5) + 1):
    if n % k != 0:
        continue
    if (n // k) % k == 1:
        ans += 1
for i in range(2, 41):
    for k in range(2, n + 1):
        x = k ** i
        if x > n:
            break
        if n % x != 0:
            continue
        if (n // x) % k == 1:
            ans += 1
n -= 1
for k in range(1, int(n ** 0.5) + 1):
    if n % k != 0:
        continue
    if k * k == n or k == 1:
        ans += 1
    else:
        ans += 2
if(n == 1):
    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())

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

tmp=make_divisors(n-1)
tmp.remove(1)
ans=set(tmp)
cnt=make_divisors(n)
cnt.remove(1)
for i in range(len(cnt)):
    k=cnt[i]
    gh=n
    while(gh%k==0):
        gh//=k
    if gh%k==1:
        ans.add(k)

print(len(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())
num = 0

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

k = make_divisors(n)
k.pop(0)

for item in k:
  tn = n
  while tn % item == 0:
      tn /= item
    
  if tn % item == 1:
    num += 1

print(num)

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

a = make_divisors(n-1)
b = make_divisors(n)

a.remove(1)
b.remove(1)

count = len(a)

for i in b:
    n_new = n // i
    while n_new % i == 0:
        n_new = n_new // i
    if n_new % i == 1:
        count += 1

print(count)

Submission status: Accepted

Solution code:
from collections import deque
def deque_divisor(n):
    d = deque()
    for i in range(int(n**(1/2)),0,-1):
        if i**2 == n:
            d.append(i)
            continue
        if n % i == 0:
            d.appendleft(i)
            d.append(n//i)
    return d

n = int(input())

candidate = (set(deque_divisor(n)) | set(deque_divisor(n-1)))
candidate.discard(1)

ans = 0

for i in candidate:
    k = n
    while k % i == 0:
        k //= i
    k %= i
    if k == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())

divisor_N1=set()
for i in range(1, math.floor(math.sqrt(N-1)) + 1):
    if (N - 1) % i == 0:
        divisor_N1.add(i)
        divisor_N1.add((N-1) // i)
#print(divisor_N1)

divisor_N=set()
for i in range(1, math.floor(math.sqrt(N) + 1)):
    if N % i == 0:
        divisor_N.add(i)
        divisor_N.add(N // i)
#print(divisor_N)
divisor_N.remove(1)
divisor_N1.remove(1)
#print(divisor_N)
#print(divisor_N1)

cnt = len(divisor_N1)
for num in divisor_N:
    temp = N
    while temp % num == 0:
        temp //= num
    if temp % num == 1:
        cnt += 1
        #print(num)
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = []
B = []
for i in range(2,int(N**0.5)+1):
    if N%i==0:
        A.append(i)
        A.append(N//i)
    if (N-1)%i==0:
        B.append(i)
        B.append((N-1)//i)
A.append(N)
if N>2:
    B.append(N-1)
A = sorted(A)
for a in A:
    m = 1
    while True:
        if a**m==N:
            B.append(a)
            break
        elif a**m>N:
            break
        m += 1
for a in A:
    m=0
    while a**m<N:
        if N%a**m==0:
            if (N//(a**m)-1)%a==0:
                B.append(a)
        m += 1
B = sorted(list(set(B)))
print(len(B))

Submission status: Accepted

Solution code:
def abc(n,i):
    if i==1:
        return 0
    while not n%i:
        n=n//i
    return not (n-1)%i
n=int(input())
e={}
for i in range(1,int(pow(n,0.5))+1):
    if not n%i:
        if abc(n,i):
            e[i]=0
        if abc(n,n//i):
            e[n//i]=0
n-=1

c=0
for i in range(1,int(pow(n,0.5))+1):
    if not n%i:
        c+=1
        if i!=n//i:
            c+=1
print(len(e)+c-1)

Submission status: Accepted

Solution code:
N = int(input())

divisor = [N]
ans = 0

#Nの約数の列挙
for i in range(2,N+1,1):
    if i*i < N:
        if N % i == 0:
            divisor.append(i)
            divisor.append(N//i)
    elif i*i == N:
        divisor.append(i)
    else:
        break

#N-1の約数の列挙
yakusuuu = [N-1]
for i in range(2,N,1):
    if i*i < (N-1):
        if (N - 1)% i == 0:
            yakusuuu.append(i)
            yakusuuu.append((N-1)//i)
    elif i*i == (N-1):
        yakusuuu.append(i)
    else:
        break

for i in yakusuuu:
    if N % i == 1:
        ans += 1

#print(divisor)
#print(yakusuuu)

M = N

for K in divisor:
    #print(K)
    while M % K == 0:
        M = M//K

    

    if M == 1:
        ans += 1
        
    else:
        M =  M % K
        if M == 1:
            ans += 1 
    
    M = N
        




print(ans)

Submission status: Accepted

Solution code:
def divisors(N):
    U = int(N ** 0.5) + 1
    L = [i for i in range(1, U) if N % i == 0]
    return L + [N // i for i in reversed(L) if N != i * i]

def solve(k):
    n = N
    while n % k == 0:
        n //= k
    return (n % k == 1)

N = int(input())

K = set(divisors(N) + divisors(N - 1)) - {1}
print(sum(solve(k) for k in K))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


def divisors(n, sort=False):
    """
    nの約数をO(√n)で列挙する
    """
    d = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            d.append(i)
            if i != n // i:
                d.append(n//i)
    if sort:
        d.sort()
    return d


N = I()

ans = 0
for d in divisors(N - 1):
    if d > 1:
        ans += 1
for d in divisors(N):
    if d == 1:
        continue
    num = N
    while num % d == 0:
        num = num // d
    if num % d == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ans = 0
    m = n - 1
    num = 1
    while num * num <= m:
        if m % num == 0:
            if num > 1:
                ans += 1
            if m // num != num:
                ans += 1
        num += 1
    num = 1
    while num * num <= n:
        if n % num == 0:
            tmp = n
            while num > 1 and tmp % num == 0:
                tmp = tmp // num
            if tmp == 1 or tmp % num == 1:
                ans += 1
            rest = n // num
            if rest != num:
                tmp = n
                while tmp % rest == 0:
                    tmp = tmp // rest
                if tmp == 1 or tmp % num == 1:
                    ans += 1
        num += 1
    print(ans)


if __name__ == "__main__":
    main()