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:
#!/usr/bin/env python3

import sys
import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()

    # naive, O(nlgn)
    # cnt = 0
    # for k in range(2, n + 1):
    #     tmp = n
    #     if tmp % k == 1:
    #         cnt += 1
    #     elif tmp % k == 0:
    #         while tmp >= k and tmp % k == 0:
    #             tmp //= k
    #         if tmp % k == 1:
    #             cnt += 1
    # print(cnt)

    class Eratos:
        def __init__(self, num):
            assert(num >= 1)
            self.table_max = num
            # self.table[i] は i が素数かどうかを示す (bool)
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            for i in range(2, int(math.sqrt(num)) + 1):
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    # i**2 からスタートすることで定数倍高速化できる
                        self.table[j] = False
            # self.table_max 以下の素数を列挙したリスト
            self.prime_numbers = [2] if self.table_max >= 2 else []
            for i in range(3, self.table_max + 1, 2):
                if self.table[i]:
                    self.prime_numbers.append(i)
        
        def is_prime(self, num):
            """
            >>> e = Eratos(100)
            >>> [i for i in range(1, 101) if e.is_prime(i)]
            [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
            """
            assert(num >= 1)
            if num > self.table_max:
                raise ValueError('Eratos.is_prime(): exceed table_max({}). got {}'.format(self.table_max, num))
            return self.table[num]
        
        def prime_factorize(self, num):
            """
            >>> e = Eratos(10000)
            >>> e.prime_factorize(6552)
            {2: 3, 3: 2, 7: 1, 13: 1}
            """
            assert(num >= 1)
            if int(math.sqrt(num)) > self.table_max:
                raise ValueError('Eratos.prime_factorize(): exceed prime table size. got {}'.format(num))
            factorized_dict = dict()    # 素因数分解の結果を記録する辞書
            candidate_prime_numbers = [i for i in range(2, int(math.sqrt(num)) + 1) if self.is_prime(i)]
            # n について、√n 以下の素数で割り続けると最後には 1 or 素数となる
            # 背理法を考えれば自明 (残された数が √n より上の素数の積であると仮定。これは自明に n を超えるため矛盾)
            for p in candidate_prime_numbers:
                # これ以上調査は無意味
                if num == 1:
                    break
                while num % p == 0:
                    num //= p
                    try:
                        factorized_dict[p]
                    except KeyError:
                        factorized_dict[p] = 0
                    finally:
                        factorized_dict[p] += 1
            if num != 1:
                factorized_dict[num] = 1
            return factorized_dict
    

    eratos = Eratos(int(math.sqrt(n)))
    d_1 = eratos.prime_factorize(n - 1)
    # n = k + 1, 2k + 1, 3k + 1, ...    
    cnt = 0
    tmp = 1
    for _, v in d_1.items():
        tmp *= (v + 1)
    tmp -= 1
    cnt += tmp
    d_2 = eratos.prime_factorize(n)
    # 全約数 x (除: 1) について (n // x) ≡ 1 (mod x) なら cnt += 1とすればいいのでは
    # 約数の個数は高々 2√n 個なので間に合いそう？
    L = [range(v + 1) for _, v in d_2.items()]
    power_list = list(product(*L))
    prime_list = list(d_2.keys())
    for elm in power_list:
        # elm は具体的な各素数の指数を指定したリストである
        div = 1
        for i in range(len(prime_list)):
            div *= pow(prime_list[i], elm[i])
        # print(f"div: {div}")
        if div != 1:
            assert(n % div == 0)
            copy_n = n
            while copy_n % div == 0:
                copy_n //= div
            if copy_n % div == 1:
                cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout
import math
import bisect
import datetime
from collections import defaultdict
import random

def bl_solve(a):
    ans = []
    for k in range(2, a + 1):
        tmp = a
        while tmp > 0:
            if tmp % k == 0:
                tmp = tmp // k
            else:
                tmp -= k
            if tmp == 1:
                ans.append(k)
                break
    return ans

def bl_solve2(a):
    if a == 2:
        ans = 1
    else:
        ans = 2
    for k in range(2, int(math.sqrt(a))+1):
        tmp = a
        while tmp >= k:
            if tmp % k == 0:
                tmp = tmp // k
            else:
                tmp %= k
        if tmp == 1:
            ans+=1
        if (a - 1) % k == 0 and k != math.sqrt(n - 1):
            ans+=1
    return ans

def fj(a):
    arr = defaultdict(int)
    i = 2
    while i <= math.sqrt(a):
        while a % i == 0:
            a //= i
            arr[i] += 1
        i += 1
    if a != 1:
        arr[a] += 1
    ans = 1
    for key, value in arr.items():
        ans *= (value + 1)
    return ans-1

def solve(a):
    if a == 2:
        return 1
    ans = fj(a - 1)
    i = 2
    while True:
        tmp = round(a**(1 / i))
        if tmp ** i == a:
            ans += 1
        if tmp < 2:
            break
        i+=1
    return ans + 1
    

n = int(stdin.readline().strip())

ans = bl_solve2(n)
stdout.writelines(str(ans)+'\n')

# for n in range(2, 10000):
#     ans = bl_solve(n)
#     ans2 = bl_solve2(n)
#     if ans2 == len(ans):
#         print('True')
#     else:
#         print('False')
#         print(ans2,len(ans),ans)
#         input()
    # print(n, len(ans), ans)

Submission status: Accepted

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

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

def main():
    mod=10**9+7
    
    N=I()
    #約数列挙
    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
    
    ans=set(make_divisors(N-1))
    ans=ans - set([1])
    ans.add(2)
    
    L=make_divisors(N)
    
    for i in range(1,len(L)):
        temp=L[i]
        N2=N
        while N2>=temp:
            if N2%temp==0:
                N2=N2//temp
            else:
                N2=N2%temp
        if N2==1:
            ans.add(temp)
            
        
            
    
    print(len(ans))

        

main()

Submission status: Accepted

Solution code:
init=int(input())

ans=[]
for K in range(2,int(init**0.5)+1):
    N=init
    while N%K==0:
        N/=K
    if N-(N//K)*K==1:
        ans.append(K)
        
tgt=init-1
cand=[]
for i in range(1,int(init**0.5)+1):
    if tgt%i==0:
        cand.append(i)
        if i!=tgt//i:
            cand.append(tgt//i)
ans=list(set(ans+cand))
print(len(ans))

Submission status: Accepted

Solution code:
import copy
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())

box = make_divisors(n-1)
ans = len(box)-1
boxn = make_divisors(n)
for i in range(1,len(boxn)):
    k = boxn[i]
    nn = copy.deepcopy(n)
    while nn % k == 0 and nn >= k:
        nn = nn // k

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

def yakusu(x):
    xx = 2
    y = []
    while xx**2 < x:
        if x%xx == 0:
            y.append(xx)
            y.append(x//xx)
        xx += 1
    if xx**2 == x:
        y.append(xx)
    y.append(x)
    return y
    
if n == 2:
    ans = 0
else:
    ans = len(yakusu(n-1))

for i in yakusu(n):
    nn = n
    while True:
        if nn%i == 0:
            nn = nn//i
        else:
            break
    if nn%i == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	K = int(input())

	div = [] #約数のリスト
	#場合分け
	if ((K ** 0.5) // 1) ** 2 == K:
		n = int((K ** 0.5) // 1)
		for i in range(1, n):
			if K % i == 0:
				div.append(i)
		d = len(div)
		for i in range(d):
			div.append(K // div[i])
		div.append(int((K ** 0.5) // 1))

	else:
		n = int((K ** 0.5) // 1)
		for i in range(1, n + 1):
			if K % i == 0:
				div.append(i)
		d = len(div)
		for i in range(d):
			div.append(K // div[i])

	# print(div)
	ans = 0
	for i in div:
		if i == 1:
			continue
		N = K
		while True:
			if N % i == 0:
				N = int(N // i)
			else:
				if N % i == 1:
					ans += 1
				break

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

	else:
		n = int((K ** 0.5) // 1)
		for i in range(1, n + 1):
			if K % i == 0:
				ans += 2

	print(ans - 1)



if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import math
def calc_yakusu_num(n):
    num = 0

    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            if i == n // i:
                num += 1
            else:
                num += 2
    return num - 1
    
def calc_yakusu(n):
    yakusu = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            if i == n // i:
                yakusu.append(i)
            else:
                if i != 1:
                    yakusu.append(i)
                yakusu.append(n // i)
    return yakusu

if __name__ == "__main__":
    ans = 0
    n = int(input())

    ans += calc_yakusu_num(n - 1)
    
    y = calc_yakusu(n)
  

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

Submission status: Accepted

Solution code:
import math

n = int(input())
ans=2

def go(n,k):
	aux=1
	while(n%k==0):
		n/=k
	if n%k==1:
		return True
	return False

for i in range(2,n):
	if(i*i>n): 
		break
	if n%i==0:
		if(go(n,i)): 
			ans+=1
		if(i!=n/i and go(n,n/i)):
			ans+=1
n-=1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
ans=0

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

    # divisors.sort()
    return divisors

ndivs = make_divisors(n)

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

for i in range(1,len(ndivs)):
    tmp = n
    k = ndivs[i]
    while tmp%k==0:
        tmp //=k
    if tmp%k==1:ans+=1

print(ans)

Submission status: Accepted

Solution code:

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

    # divisors.sort()
    return divisors

N = int(input())
ans = len(make_divisors(N-1))-1

for i in make_divisors(N):
  if i == 1:
    continue
    
  Ni = int(N/i)
  
  while Ni % i == 0:
    Ni = int(Ni/i)
    
  if Ni % i == 1:
    ans+=1
    

print(ans)

Submission status: Accepted

Solution code:

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

  def get_divisors(num):
    divisors = []
    for i in range(1, int(num ** 0.5) + 1):
      if num % i == 0:
        divisors.extend([i, num // i])

    return set(divisors)

  ans = len(get_divisors(n - 1)) - 1

  for k in get_divisors(n):
    if k == 1: continue

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

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

  print(ans)

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

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

d = list(set(a + b))

ans = 0

for i in list(d):
    if i == 1:
        continue
    x = n
    while x % i == 0:
        x /= i
    
    if x % i == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

# n % k = 1 の数
m = n - 1
i = 2
ans = 1
while i * i <= m:
    if m % i == 0:
        num = 1
        while m % i == 0:
            num += 1
            m //= i
        ans *= num
    i = i + 1
if m != 1:
    ans *= 2
ans -= 1

# n % k = 0 の場合
# nを素因数分解する
m = n
import numpy as np
i = 2
factor = []
while i * i <= n:
    if n % i == 0:
        l = []
        num = 1
        l.append(num)
        while n % i == 0:
            num *= i
            l.append(num)
            n //= i
        factor.append(np.array(l))
    i = i + 1
if n > 1:
    factor.append(np.array([1, n]))

# 直積を求めることでnの全約数を得る
divisor = factor[-1]
for i in range(len(factor) - 1):
    divisor = np.outer(divisor, factor[i])
divisor = np.outer(np.array(1), divisor)

# 判定
for i in divisor[0]:
    if i == 1:
        continue
    n = m
    while n % i == 0:
        n //= i
    if n % i == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

# 例外処理
if n == 2:
    print(1)
    exit()
if n == 3:
    print(2)
    exit()

# n % k = 1 の数
m = n - 1
i = 2
ans = 1
while i * i <= m:
    if m % i == 0:
        num = 1
        while m % i == 0:
            num += 1
            m //= i
        ans *= num
    i = i + 1
if m != 1:
    ans *= 2
ans -= 1

# n % k = 0 の場合
# nを素因数分解する
m = n
import numpy as np
i = 2
factor = []
while i * i <= n:
    if n % i == 0:
        l = []
        num = 1
        l.append(num)
        while n % i == 0:
            num *= i
            l.append(num)
            n //= i
        factor.append(np.array(l))
    i = i + 1
if n > 1:
    factor.append(np.array([1, n]))

# 直積を求めることでnの全約数を得る
divisor = factor[-1]
for i in range(len(factor) - 1):
    divisor = np.outer(divisor, factor[i])
divisor = np.outer(np.array(1), divisor)

# 判定
for i in divisor[0]:
    if i == 1:
        continue
    n = m
    while n % i == 0:
        n //= i
    if n % i == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
from numpy import sqrt
cnt = 2
rt = int(sqrt(n))
for i in range(2,rt+1):
    if n % i == 0:
        m = n
        while m%i ==0:
            m = m//i
        if m%i == 1:
            cnt += 1
    elif (n-1) % i ==0:
        cnt += 2
if n == rt ** 2 + 1:
    cnt -= 1
print(cnt)

Submission status: Accepted

Solution code:
N=int(input())
D={}
for i in range(2,int(N**0.5)+1):
    n=N
    #print(i,n)
    while n%i==0 and n!=i:
        n//=i
    #print(i,n)
    if n==i or n%i==1:
        D[i]=1
        #print("ANS",i,n)
#print(D)
N1=N-1
for i in range(1,int(N1**0.5)+1):
    if N1%i==0:
        D[i]=1
        D[N1//i]=1
#print(D)
print(len(D))

Submission status: Accepted

Solution code:
n=int(input())

def m_div(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 check(num,k):
    if k==1:
        return False

    while num>=k:
        if num%k==0:
            num=num//k
        else:
            break
    num%=k
    return num==1

n1divs = m_div(n-1)
ndivs  = m_div(n)

ans=[]
for num in n1divs:
    if check(n,num):
        ans.append(num)
for num in ndivs:
    if check(n,num):
        ans.append(num)
print(len(set(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)):
            if(i>1):
                divisors.append(i)
            if i != n // i:
                if(n//i>1):
                    divisors.append(n//i)
    return divisors

def test(n,ans_list):
    ans_list.append(n)
    ans_list = ans_list + make_divisors(n-1)
    
    for ans in make_divisors(n):
        nn = n
        while(nn%ans == 0):
            nn = nn/ans
        nn = nn%ans
        if(nn == 1):
            ans_list.append(ans)
    return ans_list

n = int(input())

ans_list = []

answer = list(set(test(n,ans_list)))
#answer.sort()

print(len(answer))

Submission status: Accepted

Solution code:
def calc_factors(N):
    """
    約数をlistでreturn
    この問題はK>1なので、約数に1を含めてない
    """
    i=2
    factors={N}
    while i*i<=N:
        if N%i==0:
            factors.add(i)
            factors.add(N//i)
        i+=1
    return list(sorted(factors))


N = int(input())


if N==2:
    print(1)
    exit()
#割り算しない場合
ans = len(calc_factors(N-1))
#割り算する場合
for fac in calc_factors(N):
    tmp=N
    while tmp%fac==0:
        tmp//=fac
    if tmp%fac==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    count = 2
    sqrt = int(n ** (1/2))
    for i in range(2,sqrt + 1):
        if n % i == 1:
            count += 2
        elif n % i == 0:
            ins = n
            while ins % i == 0:
                ins = ins // i
            if ins % i == 1:
                count += 1
    if sqrt ** 2 == n - 1:
        count -= 1

    print(count)


if __name__ == "__main__":
    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


n = int(input())
ans = len(make_divisors(n - 1))
divisors = []
for i in make_divisors(n):
    j = n
    if i != 1:
        while j % i == 0:
            j //= i
        if (j - 1) % i == 0:
            divisors.append(i)
print(ans + len(divisors) - 1)

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
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 resolve():
    N = ir()
    ans = len(make_divisors(N-1))-1
    d = make_divisors(N)
    d.remove(1)
    for i in d:
        tmp = N
        while tmp != 1 and tmp >= i:
            if tmp%i > 0:
                tmp %= i
            else:
                tmp //= i
        if tmp == 1:
            ans += 1
    print(ans)
resolve()

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())
divs = make_divisors(N)
# print(sorted(divs))
divs2 = make_divisors(N-1)
ans = len(sorted(divs2))-1
for div in divs[1:]:
    tmp = N
    while tmp%div == 0:
        tmp //= div
    if tmp%div == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *

sys.setrecursionlimit(100000000)


def input(): return sys.stdin.readline().rstrip()


N = int(input())


def f(x):
    ans = set()
    i = 1
    while i * i <= x:
        if x % i == 0:
            ans.add(i)
        i += 1
    for i in ans.copy():
        ans.add(x // i)
    return ans

ans = set()
for K in f(N) | f(N - 1):
    if K == 1:
        continue
    n = N
    while n % K == 0:
        n //= K
    if n % K == 1:
        ans.add(K)

print(len(ans))

Submission status: Accepted

Solution code:
N = int(input())

def divider(n):
  dividers = []
  for i in range(1, int(n**0.5) + 1):
    if n % i == 0:
      dividers.append(i)
      if i != n // i:
        dividers.append(n // i)
  dividers.sort()
  dividers.remove(1)
  return dividers
#nの約数を抽出する関数を定義(1以外)

cnt = len(divider(N - 1))
for k in divider(N):
  n = N
  while n % k == 0:
    n /= k
  if n % k == 1:
    cnt += 1
print(cnt)

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



ansl = make_divisors(n-1)
ansl.remove(1)
for i in make_divisors(n):
    if i == 1:
        continue
    k = n
    while k:
        if k % i == 0:
            k //= i
        else:
            if k % i == 1:
                ansl.append(i)
            break

print(len(set(ansl)))

Submission status: Accepted

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

    # K > 1

    def divisor_set(x):
        ret = set()
        if x > 1:
            ret.add(x)

        d = 2
        while d * d <= x:
            if x % d == 0:
                ret.add(d)
                ret.add(x // d)
            d += 1
        return ret

    # N % K == 1
    # (N-1) % K == 0
    # K > 1

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

    # N % K == 0
    # N //= K ---> M
    # (M-1) % K == 0

    for k in divisor_set(N):
        x = N
        while x % k == 0:
            x //= k
        if x % k == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
from math import ceil

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

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

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

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    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)
        return ass  # sortされていない
    g = sorted(divisor(n))

    q = []
    for i in range(1, len(g)):
        m=n
        while m >= g[i]:
            if m %g[i] == 0:
                m = m//g[i]
            else:
                m = m%g[i]
        if m == 1:
            q.append(g[i])
    print(len(set(divisor(n-1)+q))-1)

resolve()

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)

ans = (len(b) - 1)
for i in a:
    x = n
    if i == 1:
        continue
    elif i == n:
        ans += 1
    else:
        while x % i == 0:
            x /= i
        if x % i == 1:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
def divisors(n):
    ret = set()
    for i in range(1, int(n**0.5)+2):
        if n % i == 0:
            ret.add(i)
            ret.add(n // i)
    ret.remove(1)
    return ret


def main():
    N = int(input())
    s = divisors(N)
    ans = divisors(N-1)

    for x in s:
        n = N
        if x == 1:
            continue
        while(n % x == 0):
            n = n // x
        if n % x == 1:
            ans.add(x)
    print(len(ans))


main()

Submission status: Accepted

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

    def gcd(x, y):
        if y == 0:
            return x
        while y != 0:
            x, y = y, x % y
        return x

    N = int(input())
    ans = 0
    divs = trial_division(N) | trial_division(N-1)
    for d in divs:
        if d == 1:
            continue
        num = N
        while num % d == 0 and d <= num:
            num //= d
        if num % d == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

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


div_N = divisor(N)
div_N_1 = divisor(N-1)

ans = 0

for k in div_N[1:]:
    n = N
    while n % k == 0:
        n //= k
    if n % k == 1:
        ans += 1

ans += len(div_N_1) - 1

print(ans)

Submission status: Accepted

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

    # divisors.sort()
  return divisors
#N-1の約数(1は除く)　Nそのもの
#2
d=make_divisors(N-1)
if not 2 in d:
  d.append(2)
#print(d)
d2=make_divisors(N)
#print(len(d))
for i in d2:
  if i!=N and i!=1 and i not in d:
    now=N
    while now%i==0:
      now/=i
    if now%i==1:
      d.append(i)
print(len(d))

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import product


from functools import reduce
import operator
nproduct = lambda it: reduce(operator.mul,it,1)

# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n

def all_divisors(n):
    factors,counts = map(tuple,zip(*Counter(prime_factors(n)).items()))

    for p in product(*(range(c+1) for c in counts)):
        yield nproduct(v**k for v,k in zip(factors,p))

def num_divisors(n):
    return nproduct(c+1 for c in Counter(prime_factors(n)).values())


N = int(input())

cnt = num_divisors(N-1)
for d in all_divisors(N):
    if d == 1:
        continue
    x = N
    while x % d == 0:
        x //= d
    if x % d == 1:
        cnt += 1

print(cnt-1)

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,int(n**.5) + 1):
  if n % i == 0:
    tmp = n
    while tmp % i==0:
      tmp //= i
    if (tmp-1) % i == 0:ans += 1

    if n//i != i:
      tmp = n;i = n//i
      while tmp % i==0:
        tmp //= i
      if (tmp-1) % i == 0:ans += 1

for i in range(2,int((n-1)**.5 )+ 1):
  if (n-1) % i == 0:
    if (n-1) // i == i: ans += 1
    else: ans += 2
# print(ans)
print(ans+1 + int(n != 2))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from copy import deepcopy


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(readline())
ans = len(make_divisors(n - 1))
for check in make_divisors(n):
    if check == 1:
        continue
    nn = deepcopy(n)
    while nn % check == 0:
        nn //= check
    if nn % check == 1:
        ans += 1
print(ans - 1)