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: Wrong Answer

Solution code:
import math
N=int(input())
if N==2:
  print(1)
  exit(0)
if N==3:
  print(2)
  exit(0)
ans=0
for i in range(2,int(math.sqrt(N)+1)):
  n=N
  while n%i==0:
    n//=i
  if n%i==1:
    ans+=1
    if not N//i<=i:
      ans+=1
print(ans+1)

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
if N==2:
  print(1)
  exit(0)
if N==3:
  print(2)
  exit(0)
ans=0
for i in range(2,int(math.sqrt(N)+1)):
  n=N
  while n%i==0:
    n//=i
  if n%i==1:
    ans+=1
print(ans*2+1)

Submission status: Wrong Answer

Solution code:
from copy import copy

n = int(input())

cnt = 0
for k in range(2,int(n**0.5)+1):
  m = copy(n)
  while m > 1:
    if m%k == 0:
      m /= k
    else:
      m -= k
  if m == 1:
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from copy import copy

n = int(input())

cnt = 0
for k in range(2,n//2+1):
  m = copy(n)
  while m > 1:
    if m%k == 0:
      m /= k
    else:
      m -= k
  if m == 1:
    cnt += 1
print(cnt+2)

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = 1
divisors = []
d = 2
while d*d < N:
    if N % d == 0:
        divisors.append(d)
        divisors.append(N//d)
    d += 1
if d*d == N:
    divisors.append(d)

for d in divisors:
    dummyN = N
    while dummyN % d == 0:
        dummyN //= d
    if dummyN % d == 1:
        ans += 1

N -= 1
divisors = []
d = 2
while d*d < N:
    if N % d == 0:
        divisors.append(d)
        divisors.append(N//d)
    d += 1
if d*d == N:
    divisors.append(d)

ans += len(divisors)+1
print(ans)

Submission status: Wrong Answer

Solution code:
"""
一回以上わるとき、KはNの約数なので、Nの約数を全通り試して1に持っていけるかどうかを検証する。
Nを一回も割らずに1まで持っていけるようなKは、N-1の約数の数だけ存在する。
それぞれカウントすればよい
"""
N = int(input())
ans = 0

divisers = [N]
d = 2
while d*d < N:
    if N % d == 0:
        divisers.append(d)
        divisers.append(N//d)
    d += 1
if d**2 == N:
    divisers.append(d)

for d in divisers:
    dummyN = N
    while dummyN%d == 0:
        dummyN //= d
    if dummyN % d == 1:
        ans += 1

N -= 1
divisers = [N]
d = 2
while d*d < N:
    if N % d == 0:
        divisers.append(d)
        divisers.append(N//d)
    d += 1
if d**2 == N:
    divisers.append(d)

ans += len(divisers)

print(ans)

Submission status: Wrong Answer

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

def get_divisors(x):
  lim = math.ceil(math.sqrt(x))
  divisors = set()
  for i in range(1,lim+1):
    if x % i == 0:
      divisors.add(i)
      divisors.add(N//i)    
  return divisors
    
ans_1 = 0
#約数について
divisors = get_divisors(N)
for d in divisors:
  if d == 1: continue
  N_try = N
  while N_try % d == 0:
    N_try //= d
  if N_try % d == 1:
    ans_1 += 1
    
#約数でない数について
divisors = get_divisors(N-1)
ans_2 = len(divisors)-1
    
#print(ans_1, ans_2)
print(ans_1+ans_2)

Submission status: Wrong Answer

Solution code:
"""
Nが1になるようなKは、
・K^x＝NになるようなKか
・K*x = N-1 になるようなKである。
上記の両方を満たすKは存在しないので、それぞれについて条件を満たすKを数えて、合計すればよい。

まず、K^x = N になるようなKに関しては、Nを素因数分解して求めることができる。
各素因数のカウントの公約数の数だけKが存在する。（素因数が一つの場合は、その素因数のカウントの約数の数）

次に、K*x = N-1 になるようなKに関しては、N-1の約数の数だけKが存在するので、
これもまた、N-1を素因数分解して約数の数を調べればよい。
"""
from collections import Counter

def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

N = int(input())
ans = 0
#K^x = N になるようなKの数を調べる。
#Nを素因数分解する。
tmp = []
dummyN = N
ceil = int(dummyN**0.5)
for d in range(2,ceil+1):
    while dummyN % d == 0:
        tmp.append(d)
        dummyN //= d
if dummyN != 1:
    tmp.append(dummyN)
    dummyN //= dummyN

divideN = Counter(tmp)
values = list(divideN.values())
g = values[0]
for i in range(1,len(values)):
    g = gcd(g,values[i])
tmp = []
ceil = int(g**0.5)
for d in range(2,ceil+1):
    while g % d == 0:
        tmp.append(d)
        g //= d
if g != 1:
    tmp.append(g)
divideG = Counter(tmp)
commonDCnt = 1
for v in divideG.values():
    commonDCnt *= (v+1)
ans += commonDCnt


#K*x = N-1 になるようなKの数を調べる。
#Nを素因数分解する。
tmp = []
dummyN = N-1
ceil = int(dummyN**0.5)
for d in range(2,ceil+1):
    while dummyN % d == 0:
        tmp.append(d)
        dummyN //= d
if dummyN != 1:
    tmp.append(dummyN)
    dummyN //= dummyN

divideN = Counter(tmp)
commonDCnt = 1
for v in divideN.values():
    commonDCnt *= (v+1)
ans += commonDCnt

print(ans)

Submission status: Wrong Answer

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

def divisor(num):
    max_num = int(sqrt(num))
    divisor_list = []
    for i in range(1, max_num + 1):
        if num % i == 0:
            divisor_list.append(i)
            divisor_list.append(num//i)
    return divisor_list

K0 = divisor(N)
K1 = divisor(N-1)

ans = len(K1) - 1
for k in K0:
    tmp = N
    if k == 1:
        continue
    while tmp % k == 0 and tmp >= k:
        tmp //= k
    if tmp % k == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

def divisor(num):
    max_num = int(sqrt(num))
    divisor_list = []
    for i in range(1, max_num + 1):
        if num % i == 0:
            divisor_list.append(i)
            divisor_list.append(num//i)
    return divisor_list

K0 = divisor(N)
K1 = divisor(N-1)

ans = len(K1) - 1
for k in K0:
    tmp = N
    if k == 1:
        continue
    while tmp % k == 0:
        tmp //= k
    if tmp % k == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    ans = 2
    for k in range(2,int(n**0.5)+1):
        if n % k == 1:
            ans += 2
            ans -=k**2+1==n
        elif n % k == 0:
            g = n//k
            while g % k == 0:
                g = g//k
            ans += g % k == 1
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

def solve(N):
    Ans = [N, N-1]
    for base in range(2, N):
        if base * base > N:
            break
        n = N
        while n % base == 0:
            n //= base
        if n % base == 1:
            Ans.append(base)
        if (N-1) % base == 0:
            Ans.append(base)
            Ans.append((N-1)//base)
    if int(N**0.5)**2 == N:
        Ans.append(int(N**0.5))
    print(len(set(Ans)))

numba_compile([
    [solve, "void(i8)"],
])

N = int(input())
solve(N)

Submission status: Wrong Answer

Solution code:
N = int(input())

d = []
for k in range(1, int(N**0.5)+1):
  if N%k==0:
    d.append(k)
    d.append(N//k)

ans = 0

for k in d:
  if k == 1: continue
  n = N
  while n%k==0: n//=k
  n %= k
  if n==1:
    ans += 1

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

print(ans-1)

Submission status: Wrong Answer

Solution code:
n=int(input())
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
num=factorization(n-1)
num3=factorization(n)
num2=1
for i in range(len(num)):
    num2*=num[i][1]+1
num2-=1
print(num2+min(2,len(num3)))

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def ccc(v, k):
	while v > k:
		if v % k == 0:
			v = v // k
		else:
			v = v % k
	return v
		

def main():
	s = int(input())
	#b , c = tin()
	#s = input()
	if s == 2:
		return 1
	elif s == 3:
		return 2
	
	ret = 1  #s-1, 1は範囲外なので。
	for i in range(2, s-1):
		if i*i > s+1:
			break
		if (s-1) % i == 0:
			ret += 1 if i*i == s-1 else 2
			
	ret += 1 #s
	for i in range(2, s):
		if i*i > s+1:
			break
			
		if s % i == 0:
			if ccc(s, i) == 1:
				ret += 1
			oi = s // i
			if oi != i and ccc(s, oi) == 1:
				ret += 1
			
	print(ret)
			
			
	
	
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def ccc(v, k):
	while v > k:
		if v % k == 0:
			v = v //k
		else:
			v = v % k
	return v
		

def main():
	s = int(input())
	#b , c = tin()
	#s = input()
	if s == 2:
		return 1
	elif s == 3:
		return 2
	
	ret = 2
	for i in range(2, s-1):
		if i*i > s:
			break
		if s % i == 1:
			ret += 1 if i*i ==s-1 else 2
	
		if s % i == 0:
			if ccc(s, i) == 1:
				ret += 1
			oi = s // i
			if oi != i and ccc(s, oi) == 1:
				ret += 1
	print(ret)
			
			
	
	
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import copy

# 約数列挙
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 2
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1] + [n]

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


n = int(input())
div1 = make_divisors(n-1)
cnt = len(div1)

div2 = make_divisors(n)


for i in div2:
    x = copy.deepcopy(n)
    while x >= i:
        if x % i == 0:
            x //= i
        else:
            break
    if x == 1 or x % i == 1:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())

num = n - 1
cnt = 1
lst = [n]
for i in range(2, int(n ** 0.5) + 1):
    if num % i == 0:
        cnt += 2
        if num == i ** 2:
            cnt -= 1
    if n % i == 0:
        lst.append(i)
        if n != i ** 2:
            lst.append(n // i)

for num in lst:
    n2 = n
    while n2 % num == 0:
        n2 //= num
    if n2 % num == 1:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

S = set([N-1])
lst = [N]
i = 2
while i*i <= N-1:
  if (N-1) % i == 0:
    S.add(i)
    S.add((N-1)//i)
  i += 1  
  
i = 2
while i*i < N:
  if N % i == 0:
    lst.append(i)
    lst.append(N//i)
  i += 1
    
if i*i == N:
  lst.append(i)
  
lst.sort()

for l in lst:
  if l in S:
    continue
  _N = N
  while _N % l == 0:
    _N //= l
  if _N % l == 1:
    S.add(l)
    
print(len(S))

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

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

def prime_factorize(n):
    divisors = []
    # 27(2 * 2 * 7)の7を出すためにtemp使う
    temp = n
    for i in range(2, int(math.sqrt(n)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                # 素因数を見つけるたびにtempを割っていく
                temp //= i
            divisors.append([i, cnt])
    if temp != 1:
        divisors.append([temp, 1])
    if divisors == []:
        divisors.append([n, 1])

    return divisors

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            # √nで無い数についてもう一個プラス
            if i != n // i:
                divisors.append(n // i)
    return sorted(divisors)

N = getN()
print(N)

# 手順としては
# ①　kで出来るだけ割る
# ②　kで引いていく　N = mk + d(d = 1, 2, 3...)とすると,　引いて残る数はm(k - 1) + d
# つまりkで割り切れず、引いても引いても永遠に①に戻ることはない

# N = k ** i * (mk + 1)となるkの数を求める
# i == 0の時
# N - 1の約数の数 - 1(1)
ans = set()
for i in make_divisors(N - 1):
    if i != 1:
        ans.add(i)

# 割れるだけ割る関数
def dividor(x, k):
    if k == 1:
        return 0
    n = x
    while True:
        if n % k == 0:
            n //= k
        else:
            break
    return n

# i >= 1の時
for prim in make_divisors(N):
    if prim == 1:
        continue
    # Nを割れるだけ割る
    alta = dividor(N, prim)
    if alta == 1:
        ans.add(prim)
        continue
    if alta >= prim and alta % prim == 1:
        ans.add(prim)

# Nが素数でない場合はN自身が追加されない
ans.add(N)
print(len(ans))

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

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

def prime_factorize(n):
    divisors = []
    # 27(2 * 2 * 7)の7を出すためにtemp使う
    temp = n
    for i in range(2, int(math.sqrt(n)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                # 素因数を見つけるたびにtempを割っていく
                temp //= i
            divisors.append([i, cnt])
    if temp != 1:
        divisors.append([temp, 1])
    if divisors == []:
        divisors.append([n, 1])

    return divisors

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            # √nで無い数についてもう一個プラス
            if i != n // i:
                divisors.append(n // i)
    return sorted(divisors)

N = getN()

# 手順としては
# ①　kで出来るだけ割る
# ②　kで引いていく　N = mk + d(d = 1, 2, 3...)とすると,　引いて残る数はm(k - 1) + d
# つまりkで割り切れず、引いても引いても永遠に①に戻ることはない

# N = k ** i * (mk + 1)となるkの数を求める
# i == 0の時
# N - 1の約数の数 - 1(1)
ans = set()
for i in make_divisors(N - 1):
    if i != 1:
        ans.add(i)

# 割れるだけ割る関数
def dividor(x, k):
    if k == 1:
        return 0
    n = x
    while True:
        if n % k == 0:
            n //= k
        else:
            break
    return n

# i >= 1の時
for prim in prime_factorize(N):
    for i in range(1, prim[1] + 1):
        # kの候補は素因数を掛け合わせてできるNの約数
        opt = prim[0] ** i
        alta = dividor(N, opt)
        # もし割るだけ割ると1になったなら
        if alta == 1:
            ans.add(opt)
            continue
        # もしalta = (mk + 1)の形にできるなら
        if alta >= opt and alta % opt == 1:
            ans.add(opt)

# Nが素数でない場合はN自身が追加されない
ans.add(N)
print(len(ans))

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

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

def prime_factorize(n):
    divisors = []
    # 27(2 * 2 * 7)の7を出すためにtemp使う
    temp = n
    for i in range(2, int(math.sqrt(n)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                # 素因数を見つけるたびにtempを割っていく
                temp //= i
            divisors.append([i, cnt])
    if temp != 1:
        divisors.append([temp, 1])
    if divisors == []:
        divisors.append([n, 1])

    return divisors

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            # √nで無い数についてもう一個プラス
            if i != n // i:
                divisors.append(n // i)
    return sorted(divisors)

N = getN()

# 手順としては
# ①　kで出来るだけ割る
# ②　kで引いていく　N = mk + d(d = 1, 2, 3...)とすると,　引いて残る数はm(k - 1) + d
# つまりkで割り切れず、引いても引いても永遠に①に戻ることはない

# N = k ** i * (mk + 1)となるkの数を求める
# i == 0の時
# N - 1の約数の数 - 1(1)
ans = set()
for i in make_divisors(N - 1):
    if i != 1:
        ans.add(i)

# i >= 1の時
for prim in prime_factorize(N):
    # まず素因数全てで割ります
    # 全てで割らないと(mk + 1)の約数にkが残ります
    alta = N
    alta //= prim[0] ** prim[1]
    for i in range(1, prim[1] + 1):
        # kの候補は素因数を掛け合わせてできるNの約数
        opt = prim[0] ** i
        # もしalta = (mk + 1)の形にできるなら
        if alta % opt == 1:
            ans.add(opt)

# Nが素数でない場合はN自身が追加されない
ans.add(N)
print(len(ans))

Submission status: Wrong Answer

Solution code:
def div(n):
    r = int(n**(1/2))
    for i in range(2, r + 1):
        if n % i == 0:
            yield i
            if i != r:
                yield n // i
    yield n


n = int(input())
count = len(list(div(n-1)))
for i in div(n):
    x = n
    while x % i == 0:
        x //= i
    if x % i == 1:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import math


def div(n):
    r = math.floor(math.sqrt(n))
    for i in range(2, r + 1):
        if n % i == 0:
            yield i
            if i != r:
                yield n // i
    yield n


n = int(input())
count = len(list(div(n-1)))
for i in div(n):
    x = n
    while x % i == 0:
        x //= i
    if x % i == 1:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

sys.setrecursionlimit(1000000)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def divisors(N):
    divs = [1, N]
    i = 2
    while i ** 2 <= N:
        if N % i == 0:
            divs.append(i)
            divs.append(N//i)
        i += 1
    return divs

def is_ok(N, K):
    if K <= 1:
        return False
    while N % K == 0:
        N //= K
    return N % K == 1

def main():
    N = I()
    ans = 0

    for divisor in divisors(N-1):
        if is_ok(N, divisor):
            ans += 1

    for divisor in divisors(N):
        if is_ok(N, divisor):
            ans += 1

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

sys.setrecursionlimit(1000000)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = I()

    n1 = 1 if N > 2 else 0

    a = 2
    while (N - 1) > a * a:
        if (N - 1) % a == 0:
            n1 += 2
        a += 1

    b = 2
    divisors = [N]

    while N > b * b:
        if N % b == 0:
            divisors.append(b)
            divisors.append(N // b)
        b += 1

    n2 = 0
    for divisor in divisors:
        n = N
        while n % divisor == 0:
            n //= divisor
        if n % divisor == 1:
            n2 += 1

    print(n1 + n2)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

sys.setrecursionlimit(1000000)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = I()

    n1 = 1 if N > 2 else 0

    a = 2
    while (N - 1) > a * a:
        if (N - 1) % a == 0:
            n1 += 2
        a += 1

    b = 2
    divisors = [N]

    while N > b * b:
        if N % b == 0:
            divisors.append(b)
        b += 1

    n2 = 0
    for divisor in divisors:
        n = N
        while n % divisor == 0:
            n //= divisor
        if n % divisor == 1:
            n2 += 1

    print(n1 + n2)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [n]
for i in range(2,int(n**0.5+1)):
    if n%i==0:
        a.append(i)
        if i!=n//i:
            a.append(n//i)
cnt =0
for v in a:
    s = n
    while v<=s and s%v==0:
        s = s//v
    if s%v==1: cnt += 1
b = [n-1]
m = n-1
for i in range(2,int(m**0.5+1)):
    if m%i==0:
        b.append(i)
        if i!=m//i:
            b.append(m//i)
print(cnt + len(b))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd

def is_prime_miller_rabin(n):  # ミラー-ラビン素数判定法
    if n < 2:
        return False
    elif n in {2, 3, 5, 7, 11}:
        return True
    elif n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 or n % 11 == 0:
        return False

    if n < 4_759_123_141:
        witnesses = [2, 7, 61]
    elif n < 341_550_071_728_321:
        witnesses = [2, 3, 5, 7, 11, 13, 17]
    else:
        witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]

    d = n - 1
    d = d // (d & -d)

    for a in witnesses:
        y = pow(a, d, n)
        if y == 1:
            continue
        t = d
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1:
                return False
            t <<= 1
    return True

def find_factor_rho(n):  # ポラード・ロー素因数分解法
    if n < 2:
        return None
    m = 1<<n.bit_length() // 8 + 1
    for c in range(1, 99):
        def f(x):
            return (x * x + c) % n

        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if is_prime_miller_rabin(g):
                return g
            elif is_prime_miller_rabin(n // g):
                return n // g
    return None

def prime_factorize_dict(n):
    prime_dict = defaultdict(int)
    i = 2
    while i * i <= n:
        while n % i == 0:
            n //= i
            prime_dict[i] += 1
        i += 1 + i % 2
        if i != 101 or n < 1<<20:
            continue
        while n > 1:
            if is_prime_miller_rabin(n):
                prime_dict[n] = n = 1
                break
            j = find_factor_rho(n)
            while n % j == 0:
                n //= j
                prime_dict[j] += 1
    if n > 1:
        prime_dict[n] += 1
    return prime_dict

# ---------------------- #

n = int(input())
primes = prime_factorize_dict(n - 1)
ans = 1
for value in primes.values():
    ans *= value + 1
print(ans + 1)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
ans = 0
M = int(N**0.5) + 1
for k in range(2, M):
    n = N
    while n:
        if n % k == 0:
            n //= k
        elif n % k == 1:
            ans += n != N
            break
        else:
            break


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


ans2 = 1
for _, i in factorization(N - 1):
    ans2 *= (1 + i)
ans += ans2
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    if N <= 3:
        print(N - 1)
        return
    # (1) 2 <= k <= sqrt(N) で題意を満たすkの個数
    ans_1 = 0
    k = 2
    while k ** 2 <= N:
        n = N
        while n % k == 0:
            n //= k
        n %= k
        if n == 1:
            ans_1 += 1
        k += 1
    # (2) sqrt(N) < k <= N で題意を満たすkの個数
    # sqrt(N)より大きいN-1の約数の個数 + 1 (k = N)
    ans_2 = 1
    n = 1
    while n ** 2 < N:
        if (N - 1) % n == 0:
            # (N - 1) // n が sqrt(N) より大きい約数になる
            ans_2 += 1
        n += 1
    # 答え
    print(ans_1 + ans_2)


if __name__ == '__main__':
    main()