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:
#関数f:入力xの1以外の約数をリストで出力
def f(x):
  out=set() #約数を保存するセット
  for i in range(1, int(-(-pow(x, 1/2)//1))):
    #1-x**(1/2)未満の整数iについて、xを割り切れるか判定
    if x%i==0:
      #xをiで割り切れるのであれば、iとx/iを保存
      out.add(i)
      out.add(x//i)
      
  #x**(1/2)でxを割り切れる(つまりxが平方数)なら、出力にx**(1/2)を追加
  if x%(x**(1/2))==0:
    out.add(x**(1/2))
    
  #セットから昇順のリストに変換します
  out=list(out)
  out.sort()
  
  #昇順にした結果1が先頭に来ているため、インデックス1以降を出力
  return out[1:]

#入力受け取り
N=int(input())
ans=0 #最後に出力する変数

for K in f(N): #Nの1以外の約数について、操作の結果1になるかをそれぞれ調べる
    x=N #Nを直接書き換えると後に影響するため、ここではxとする
    #xをKで割り切れる間は、Kで割り続ける
    while x%K==0:
      x/=K
      
    #xをKで割り切れなくなったら、xからKを引けるだけ引く(=割って余りをとる)
    x%=K
    
    #操作後x=1となったならば、出力に1を足す
    if x==1:
        ans+=1
        
#(N-1)の1を除いた約数はすべて条件を満たすため、出力にf(N-1)の要素数を足す
ans+=len(f(N-1))

#出力
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ans=0
nmcc=0
i=1
d=[]
while i*i<=n:
  if n%i==0:
    d.append(i)
    if i*i!=n:
      d.append(n//i)
  i+=1
for i in d:
  if i==1:
    continue
  tmp=n
  while tmp%i==0:
    tmp//=i
  tmp%=i
  if tmp==1:
    ans+=1

i=1
while i*i<=(n-1):
  if (n-1)%i==0:
    nmcc+=1
    if i*i!=n-1:
      nmcc+=1
  i+=1
nmcc-=1
print(ans+nmcc)

Submission status: Accepted

Solution code:
from math import sqrt
from math import ceil
from math import floor

def divisors(n):
	count=0
	lis=[]
	for i in range(1,ceil(sqrt(n))+1):
		if n%i==0:
			if n//i==i:
				count+=1
				lis.append(i)
			else:
				lis.append(i)
				lis.append(n//i)
				count+=2
	lis=set(lis)
	lis.remove(1)
	return lis

def main():
	n=int(input())
	ol=n-1
	ans=0
	case1div=divisors(ol)
	case2div=divisors(n)
	for i in case2div:
		newn=n
		if newn%i==0:
			while newn%i==0:
				newn//=i
		if newn%i==1:
			ans+=1
	ans+=len(case1div)
	print(ans)
main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return divisors # sortしたリストで欲しい時はsorted(divisors)

ret = 0
a = make_divisors(n)
for k in a:
    if k == 1:
        continue
    m = n
    while m % k == 0:
        m //= k
    if m % k == 1:
        ret += 1

s = make_divisors(n - 1)
s.discard(1)
print(ret + len(s))

Submission status: Accepted

Solution code:
N=int(input())
n=N
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)

    return divisors
l=make_divisors(N-1)
r=make_divisors(N)
ans=len(l)-1
for i in range(len(r)):
    N=n
    K=r[i]
    if K==1:
        continue
    while(N%K==0):
        N=N//K
    if N%K==1:
        #print(K)
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
"""from collections import *
from heapq import *
from itertools import *
from fractions import gcd

from decimal import *
import copy
from bisect import *
import time"""
import sys
sys.setrecursionlimit(10**7)
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
if 2<=N<=4:
    if N==2:
        print(1)
    if N==3:
        print(2)
    if N==4:
        print(2)
    exit()
count=2
visited=set()
for K in range(2,round(N**.5)+1):
    n=N
    while n%K==0:
        n//=K
    count+=n%K==1
    visited.add(K)

lst=[]
X=round(N**.5)+1
for i in range(2,round(N**.5)+1):
    if (N-1)%i==0:
        if not i in visited:
            lst.append(i)
        C=(N-1)//i
        if not C in visited:
            lst.append(C)



for K in lst:
    n=N
    while n%K==0:
        n//=K
    count+=n%K==1
    visited.add(K)
print(count)
"""
for K in C:
    n=N
    while n>=K:
        if n%K==0:
            n//=K
        else:
            n-=K
    if n==1:
        print(K,"KK")
"""

Submission status: Accepted

Solution code:
n=int(input())
a=n>2
for i in range(2,int(n**.5)+1):
 m=n
 while m%i<1:m//=i
 a+=(m%i<2)+(~-n%i<(i<~-n//i))
print(a+1)

Submission status: Accepted

Solution code:
N=int(input())
def F(n):
    A=[]
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            A.append(i)
            if i != n // i:
                A.append(n//i)
    return A
D=F(N-1)
E=F(N)
E=sorted(E)
G=[]
for i in E[1:]:
  a=N
  while a%i==0:
    a//=i
  if a%i==1:
    G.append(i)
print(len(G)+len(D)-1)

Submission status: Accepted

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

m = int(math.sqrt(N-1))
Myaku = []
for i in range(1,m+1):
    if (N-1)%i == 0:
        if i != 1:
            Myaku.append(i)
        if (N-1)//i != i:
            Myaku.append((N-1)//i)
            
ans = len(Myaku)

n = int(math.sqrt(N))
Nyaku = []
for i in range(1,n+1):
    if N%i == 0:
        if i != 1:
            Nyaku.append(i)
        if N//i != i:
            Nyaku.append(N//i)
            
for ny in Nyaku:
    X = N
    while X%ny == 0:
        X //= ny
    if X%ny == 1:
        ans+=1
        
print(ans)
#print(Myaku,Nyaku)

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    def divisors(x):
        r1 = deque()
        r2 = deque()
        for i in range(1,ceil(x**0.5)):
            if x % i == 0:
                r1.append(i)
                r2.appendleft(x//i)
        if int(x**0.5) == x**0.5:
            r1.append(int(x**0.5))
        return list(r1)+list(r2)
    #N-1の約数
    ans = len(divisors(N-1))-1
    # print(ans)
    # print(divisors(N))
    for d in divisors(N)[1:]:
        tmpN = N
        while tmpN % d == 0:
            tmpN //= d
        if tmpN % d == 1:
            ans += 1

            
            
    print(ans)


    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
"""
6:3
3141:13
314159265358:9
"""
#約分
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
r = len(make_divisors(n-1)) - 1
w = make_divisors(n)
for wi in w:
  if wi == 1:
    continue
  i = 1
  while n % (wi**i) == 0:
    i += 1
  if (n / (wi**(i-1))) % wi == 1:
    r += 1
print(r)

Submission status: Accepted

Solution code:
n = int(input());div=[];ans=[]
for i in range(1,int(n**0.5)+2):
  if n%i == 0:
    div.append(i);div.append(n//i)
    
for i in div:
  if i == 1:
    continue
  tmp = n
  while tmp % i == 0:
    tmp //= i
  if tmp % i ==1:
    ans.append(i)
    
n -= 1
for i in range(1,int(n**0.5)+2):
  if n%i == 0:
    ans.append(i);ans.append(n//i)
    
print(len(set(ans))-1)

Submission status: Accepted

Solution code:
n = int(input())
if n == 2:
    print(1)
    exit()
def ele(n):
    L = [n]
    for i in range(2, int(n**0.5)+1):
        cur = n
        while cur%i == 0:
            cur = cur//i
            L.append(i)
            L.append(n//i)
    L = list(set(L))
    return L
ans = ele(n-1)
t = ele(n)
for i in range(len(t)):
    temp = n
    while temp%t[i] == 0:
        temp = temp//t[i]
    if temp%t[i] == 1:
        ans.append(t[i])
print(len(ans))

Submission status: Accepted

Solution code:
import math

def get_divisor(n):
    sn = math.sqrt(n)
    i = 1
    divisor = []
    while i <= sn:
        if n % i == 0:
            divisor.append(i)
            if i != n // i:
                divisor.append(n // i)
        i += 1
    return divisor

n = int(input())
if n == 2:
    print(1)
    exit()
d1 = get_divisor(n)
d2 = get_divisor(n - 1)
ans = -1
for i in d1:
    tmp = int(n)
    if i == 1:
        continue
    while tmp % i == 0:
        tmp //= i
    if tmp % i == 1:
        ans += 1
ans += len(d2)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

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)

    divisors.sort()
    return divisors


n = int(input())
div = divisors(n)
div2 = divisors(n-1)

ans = 0
for d in div[1:]:
    tmp = n
    while tmp % d == 0:
        tmp //= d
    if tmp % d == 1:
        ans += 1

print(ans + len(div2) - 1)

Submission status: Accepted

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

def l_b(x):
  ok = 0
  ng = 40
  while ng - ok > 1:
    mid = (ok+ng) // 2
    if n % (k ** mid) == 0:
      ok = mid
    else:
      ng = mid
  return x ** ok
n = int(input())
L = make_divisors(n)
ans = 0
for k in L:
  if k == 1:
    continue
  k_m = l_b(k)
  if (n // k_m) % k == 1:
    ans += 1
ans += len(make_divisors(n-1))
ans -= 1
print(ans)

Submission status: Accepted

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

N=int(input())

ans=1
for K in range(2,min(N,int(N**0.5)+2)):
    num=N
    while num%K==0:
        num//=K
    if num>=K:
        num%=K
    if num==1:
        ans+=1

lst=make_divisors(N-1)

for u in lst:
    if u>=int(N**0.5)+2:
        ans+=1
        
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
from collections import *
from functools import *

def isqrt(n):
  if n > 0:
    x = 1 << (n.bit_length() + 1 >> 1)
    while True:
      y = (x + n // x) >> 1
      if y >= x:
        return x
      x = y
  elif n == 0:
    return 0
  else:
    raise ValueError

def qrime():
  yield from [2, 3, 5, 7]
  q = [i for i in range(1, 210, 2) if 0 not in (i%3, i%5, i%7)]
  yield from q[1:]
  for i in count(210, 210):
    for j in q:
      yield i + j

def factor(n):
  p = Counter()
  limit = isqrt(n)
  for q in qrime():
    if q > limit:
      break
    while n % q ==0:
      p[q] += 1
      n //= q
    if q in p:
      limit = isqrt(n)
  if n != 1:
    p[n] += 1
  return p

def divisor(n):
  p, m = zip(*factor(n).items())
  for c in product(*map(lambda x:range(x+1), m)):
    yield reduce(int.__mul__, (x**y for x, y in zip(p, c) if y), 1)

N = int(input())
ans = reduce(int.__mul__, (c+1 for c in factor(N-1).values()), 1) - 1

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
p=n
yakusu=[]
for i in range(1,int(n**0.5)+1):
	if n%i==0:
		yakusu.append(i)
		if i!=n//i:
			yakusu.append(n//i)
p-=1
yakusu_1=[]
for i in range(1,int(p**0.5)+1):
	if p%i==0:
		yakusu_1.append(i)
		if i!=p//i:
			yakusu_1.append(p//i)
ans=len(yakusu_1)-1
for x in yakusu:
	r=n
	if x!=1:
		while r%x==0:
			r//=x
		if (r-1)%x==0:
			ans+=1
print(ans)

Submission status: Accepted

Solution code:
import math

def divisors(n):
    div = [n]
    for i in xrange(2,int(math.sqrt(n))+1):
        if n%i == 0:
            div.append(i)
            div.append(n/i)
    return div

n = int(raw_input())
ndiv = set(divisors(n))
mdiv = set(divisors(n-1))
count = 0
for x in ndiv:
    for k in xrange(1,41):
        if x**k > n:
            break
        if (n%x**k)==0 and (n/x**k)%x == 1:
            count += 1
            #print x
            break
count += len(mdiv)
if n==2:
    count = 1
print count

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 x in make_divisors(n):
  if x == 1:
    continue
  m = n
  while m % x == 0:
    m //= x
  if m % x == 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
from collections import *
from math import *
def qrime():
  p = [2, 3, 5, 7]
  yield from p
  q = [i for i in range(1, 210, 2) if 0 not in (i%3, i%5, i%7)]
  yield from q[1:]
  for i in count(210, 210):
    for j in q:
      yield i + j

def factor(n):
  limit = int(sqrt(n))
  p = Counter()
  for q in qrime():
    if n == 1 or q > limit:
      break
    while n % q ==0:
      p[q] += 1
      n //= q
      limit = int(sqrt(n))
  if n != 1:
    p[n] += 1
  return p

def divisor(n):
  f = factor(n)
  p, m = zip(*f.items())
  for c in product(*map(lambda x:range(x+1), m)):
    if sum(c) == 0:
      continue
    C = 1
    for a, b in zip(p, c):
      C *= pow(a, b)
    yield C

ans = 0
N = int(input())
for d in divisor(N):
  n = N
  while n % d == 0:
    n //= d
  if n % d == 1:
    ans += 1

f = factor(N-1)
ans2 = 1
for c in f.values():
  ans2 *= c+1

print(ans + ans2 - 1)

Submission status: Accepted

Solution code:
def 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

n = int(input())

#K is a divisor of N
ans = 0
for x in Divisor(n):
    if x == 1: continue
    tmp = n
    while (tmp % x == 0):
        tmp /= x
    tmp %= x    
    if tmp == 1: 
      ans += 1
      
#K is not a divisor of N (except 1)
ans += len(Divisor(n-1))-1
print(ans)

Submission status: Accepted

Solution code:

N = int(input())


def solve(num):
    ret = set()

    p = 1
    while p * p <= num:
        if num % p == 0:
            ret.add(p)
            ret.add(num // p)
        p += 1

    return ret


s1 = solve(N)
s2 = solve(N-1)



# 1は答えに入らないので抜いた
ans = len(s2) - 1
for n in s1:
    if n == 1:
        continue
    tmp = N
    while tmp % n == 0:
        tmp = tmp // n
    if tmp % n == 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())
nlist=make_divisors(n)
n1list=make_divisors(n-1)
# print(nlist)
# print(n1list)
answer=len(n1list)-1#1を除きます
for i in nlist[1:len(nlist)]:
    pra=n
    while (pra%i==0):
        pra=pra/i
    if pra%i==1:
        answer+=1
print(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)
    # divisors.sort()
    return divisors

K = []
# N = K**n*(K*m+1)
# n >= 1

K1 = make_divisors(N)
K1.pop(0)
# print(K1)

for k in K1:
    # print("k=",k)
    n=0
    while N-k**n >= 0:
        # print((N-k**n)%(k**(n+1)))
        # print("n=",n)
        if (N-k**n)%(k**(n+1))==0:
            K.append(k)
        n += 1
# print(K)

# n == 0
K2 = make_divisors(N-1)
K2.pop(0)
K += K2

# print(K)

print(len(K))

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
X, Y = N-1, N
dic = defaultdict(int)
for p in range(2, int(N**0.5)+1):
    if X % p == 0:
        cnt = 0
        while X % p == 0:
            X //= p
            cnt += 1
        dic[p] = cnt
    if Y % p == 0:
        cnt = 0
        while Y % p == 0:
            Y //= p
            cnt += 1
        dic[p] = cnt
if X > 1:
    dic[X] = 1
if Y > 1:
    dic[Y] = 1
f = [1]
for p in dic.keys():
    f += [x*pow(p, c) for x in f for c in range(1, dic[p]+1)]
ans = 0
for x in f:
    if x == 1:
        continue
    y = N
    while y % x == 0:
        y //= x
    if y % x == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def get_divisors(n):
    """
    引数の数字の約数を列挙し、setで返します。1および引数自身を含みます。
    計算量はO(log(n))です。
    """
    divisors = set()
    i = 1
    while i * i <= n:
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
        i += 1
    return divisors


n = int(input())

n_ = get_divisors(n)
n_1 = get_divisors(n - 1)
n_.remove(1)
n_1.remove(1)
n_.difference_update(n_1)
# print(n_)
# print(n_1)
# print(n_.difference(n_1))
ans = len(n_1)
for cand in n_:
    if cand == 2 or cand == n:
        ans += 1
        continue
    tmp = n
    while tmp % cand == 0:
        tmp //= cand
    tmp %= cand
    if tmp == 1:
        ans += 1
print(ans)

Submission status: Accepted

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

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def divisors(N: int) -> set:
    from math import sqrt

    s = {1, N}
    for i in range(2, int(sqrt(N))+1):
        if N % i == 0:
            s.add(i)
            s.add(N // i)
    return s

def check(n, k):
    if k == 1:
        return False
    while n >= k:
        if n % k == 0:
            n //= k
        else:
            n %= k
    return n == 1

N = INT()

divs = divisors(N) | divisors(N-1)

ans = 0
for k in divs:
    if check(N, k):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math
N=int(input())
if N==2:
  print(1)
  exit()
def yaku(n):
    a=set()
    s=int(math.sqrt(n))
    for i in range(2,s+1):
        if n%i==0:
            a.add(i)
            a.add(n//i)
    return a
ans=len(yaku(N-1))+1
a=yaku(N)
for i in a:
    n=N
    while n%i==0:
        n=n//i
    if n%i==1:
        ans+=1
print(ans+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())


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


div_n = divisor(N)
div_n1 = divisor(N - 1)

ans = []
for d in div_n:
    if d == 1:
        continue
    n = N
    while n % d == 0:
        n //= d

    if n % d == 1 or n == 1:
        ans.append(d)

for d in div_n1:
    if d == 1:
        continue
    if N % d == 0:
        nd = N // d
        if nd % d == 1 or nd % d == 0:
            ans.append(d)
    else:
        ans.append(d)


ans = list(set(ans))
# print(ans)
print(len(ans))

Submission status: Accepted

Solution code:
# coding: utf-8

def check_divide(n):
    max_v = int(n ** (1/2))
    divide_nums = []
    for i in range(1,max_v + 1):
        if n % i == 0:
            divide_nums.append(i)
    return divide_nums

def check_divide2(n):
    divide_nums = []
    for K in range(2,n+1):
        tmp = n
        while True:
            if tmp % K ==0:
                tmp = tmp // K
            else:break
        if tmp % K == 1:
            divide_nums.append(K)
    return divide_nums

if __name__ == '__main__':
    N = int(input())
    tmp1 = check_divide(N-1)
    if tmp1[-1] ** 2 == N-1:
        tmp1 = len(tmp1) * 2 - 2
    else:
        tmp1 = len(tmp1) * 2 - 1

    candidates = check_divide(N)[1:]

    tmp2 = [N]
    for val in candidates:
        N_ = N
        while True:
            if N_ % val == 0:
                N_ = N_ / val
            else:break
        if N_ % val == 1:
            tmp2.append(val)
    tmp2 = len(tmp2)
    print(tmp1 + tmp2)

Submission status: Accepted

Solution code:
N = int(input())

def divisor(n):
    if n==1:return []
    ret = [n]
    for i in range(2,n+1):
        if i*i==n:
            ret.append(i)
        elif i*i > n:
            break
        elif n%i==0:
            ret.append(i)
            ret.append(n//i)
    ret.sort()
    return ret

ans = len(divisor(N-1))

for k in divisor(N):
    M = N
    while M%k==0:
        M//=k
    if M%k==1:
        ans += 1
print(ans)

Submission status: Accepted

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

n = int(input())
ways = len(find_divisor(n-1)) - 1
Div = find_divisor(n)
for i in range(1, len(Div)):
    quo = n
    while quo % Div[i] == 0:
        quo = quo // Div[i]
    if quo % Div[i] == 1:
        ways += 1
print(ways)

Submission status: Accepted

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


def main():
    n = int(input())
    # 1回も割り算しない場合は n mod k = 1でkは(n-1)の約数
    ans = len(make_divisors(n - 1)) - 1
    # 割り算をする場合
    l = make_divisors(n)[1:]
    for i in l:
        num = n
        while num % i == 0:
            num //= i
        if num % i == 1:
            ans += 1
    print(ans)


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)

    # divisors.sort()
    return divisors

n = int(input())

a = make_divisors(n-1)
ans = len(a)-1
b = make_divisors(n)[1:]
c=[]
for num in b:
    d = n
    while(d%num==0):
        d = d / num
    if(d%num==1):
        c.append(num)
ans += len(c)
print(ans)

Submission status: Accepted

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

n=int(input())
ans=0
t=d(n)
for i in t:
    if i==1:
        continue
    tn=n
    while tn>=i:
        if tn%i==0:
            tn//=i
        else:
            tn%=i
    if tn==1:
        ans+=1
ans+=len(d(n-1))-1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def make_divisors(n):
    divisors = []
    hei = 0
    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

m_n = make_divisors(N)
m_n.remove(1)
ans = len(make_divisors(N - 1)) - 1

for i in range(len(m_n)):
  x = N
  y = m_n[i]
  while x % y == 0:
    x = x // y
  if x % y == 1:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+100):
        if i > temp / i:
            break
        if i * i == temp:
            arr.append(i)
            break
        if temp % i == 0:
            arr.append(i)
            arr.append(temp // i)
    arr.append(n)
    return arr

N_div = factorization(N)
N_1_div = factorization(N-1)


ans = len(N_1_div)
for K in N_div:
    temp = N
    while temp % K == 0:
        temp = temp // K
    if temp % K == 1:
        ans += 1
print(ans)

Submission status: Accepted

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

n = int(input())
ans = len(divisors(n-1)) - 1 

for d in divisors(n)[1:]:
  tmp = n
  while tmp%d == 0:
    tmp = tmp//d
  if tmp%d == 1:
    ans += 1
  
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
p = []
q = []
r = []
for i in range(2,(int(n**0.5)+1)):
    N = n
    if N%i == 0:
        p.append(i)
for i in range(2,(int(n**0.5)+1)):
    N = n - 1
    if N%i == 0:
        r.append(i)
        if i != N//i:
            r.append(N//i)
for i in range(len(p)):
    N = n
    while N % p[i] == 0:
        N = N / p[i]
    if N % p[i] == 1:
        q.append(p[i])
for i in range(len(r)):
    if n % r[i] == 1:
        q.append(r[i])
if n == 2:
    print(1)
else:
    print(len(q)+2)

Submission status: Accepted

Solution code:
n = int(input())
n2 = int(n ** 0.5) + 1
n3 = n * 1
ans = 0

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

    # divisors.sort()
    return divisors

a = set(md(n-1))

for i in range(2,n2+1):
    n3 = n * 1
    while True:
        if n3 % i == 0:
            n3 //= i
        else:
            n3 %= i
            if n3 == 1:
                a.add(i)
            break
    
if n != 2:
    print(len(a))
else:
    print(1)

Submission status: Accepted

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


def divthensub(v, div):
    while v % div == 0:
        v //= div
    if v % div == 1:
        return True
    else:
        return False


n = int(input())
if n == 2:
    print(1)
else:
    print(len([i for i in gen_divs(n) if divthensub(n, i)]) + len(gen_divs(n - 1)) + 2)

Submission status: Accepted

Solution code:
#F
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

n=int(input())
ans1=divisor(n-1)
ans1.remove(1)
as0=divisor(n)
ans0=[]
for x in as0:
  if x!=1:
    m=n
    while m>=x and m%x==0:
      m=m//x
    if m%x==1:
      ans0.append(x)

ans=set(ans0)|set(ans1)
ans=list(ans)




print(len(ans))
"""
ans.sort()
print(ans)
for x in ans:
  m=n
  while m%x==0:
    m=m//x
  print(x,m%x)
"""

Submission status: Accepted

Solution code:
N = int(input())

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

ans = 0
divisors = make_divisors(N)[1:]
ans += len(make_divisors(N-1))-1

for divisor in divisors:
        divided_N = N
        while 1:
            if divided_N%divisor!=0:
                break
            else:
                divided_N //=divisor
        if divided_N % divisor == 1:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math

def prime(x):
  p = {}
  last = math.floor(x ** 0.5)
  if x % 2 == 0:
    cnt = 1
    x //= 2
    while x & 1 == 0:
      x //= 2
      cnt += 1
    p[2] = cnt
  for i in range(3, last + 1, 2):
    if x % i == 0:
      x //= i
      cnt = 1
      while x % i == 0:
        cnt += 1
        x //= i
      p[i] = cnt
  if x != 1:
    p[x] = 1
  return p

N = int(input())

P = prime(N - 1)

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

ans = 1
for i in P.keys():
  ans *= P[i] + 1
ans -= 1

P = prime(N)
D = [1]
for i in P.keys():
  L = len(D)
  n = i
  for j in range(P[i]):
    for k in range(L):
      D.append(D[k] * n)
    n *= i


for i in D:
  if i == 1: continue
  t = N
  while (t / i == t // i):
    t //= i

  t -= 1
  if t / i == t // i:
    ans += 1

print(ans)

Submission status: Accepted

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

#t = 0
ans += len(divisors(n-1)) - 1

#t > 0
for k in divisors(n):
    if k == 1:
        continue
    temp_n = n
    while temp_n % k == 0:
        temp_n /= k
    if temp_n % k == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt, log


def factor(number):
    i = 2
    s = set()
    while i * i <= number:
        if number % i == 0:
            if i != 2:
                s.add(i)
            if (number // i) != 2:
                s.add(number//i)
        i += 1
    return s


def newFactor(number):
    n = number
    i = 2
    ans = set()
    while i * i <= number:
        if number % i == 0:
            while number % i == 0:
                number //= i
            if number % i == 1:
                ans.add(i)
        number = n
        i += 1
    return ans


n = int(input())
if n == 2:
    print(1)
    exit()
if n == 3:
    print(2)
    exit()
s = set()
s.add(2)
s.add(n-1)
s.add(n)
s = s.union(factor(n-1))
s = s.union(newFactor(n))
print(len(s))