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:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
# 約数を列挙　n=10^12までいける
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()
    divisors.remove(1)
    return divisors


def main():
    n = ni()

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

    yaku = set(make_divisors(n - 1))

    ans = ans | yaku

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())

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

    # divisors.sort()
    return divisors


#print(make_divisors(3141))
#N, N-1, 2
#%*==1
ans=[2]
if N not in ans:
    ans.append(N)
if (N%(N-1)!=0) and (N-1 not in ans):
    ans.append(N-1)
D=make_divisors(N)
for d in D:
    now=N
    if d==1:
        continue
    while now%d==0:
        now=now//d
    if now%d==1:
        if d not in ans:
            ans.append(d)
#print(ans)

ans2=[]
for a in ans:
    i=1
    while a**i<=N:
        x=a**i
        now=N
        while now%x==0:
            now=now//x
        if now%x==1:
            if x not in ans2:
                ans2.append(x)

        i+=1
#print(ans2)
d2=make_divisors(N-1)
for d in d2:
    if d!=1 and (d not in ans2):
        ans2.append(d)
#print(ans2)
print(len(ans2))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

        return divisors
    
    N = int(input())

    div_1 = make_divisors(N)
    res = 0
    for k in div_1:
        if k == 1:
            continue
        n = N
        while n > 1:
            if n % k == 0:
                n //= k
            else:
                if n >= k:
                    n %= k
                else:
                    n -= k
        if n == 1:
            res += 1

    div_2 = make_divisors(N - 1)
    res += len(div_2) - 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
def main():
    N = int(input())
    P = []
    for k in range(1,1+int((N-1)**(1/2))):
        if (N-1)%k == 0:
            P.append((N-1)//k)
            P.append(k)
    P = set(P)
    ans = len(P)
    for k in range(2,1+int(N**(1/2))):
        if N%k == 0:
            t = N//k
            while t%k == 0:
                t //= k
            if t%k == 1:
                ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

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

N = int(input())
ds = make_divs(N)
ans = 0

for d in ds:
    if d==1:
        continue
    
    N2 = N
    
    while N2%d==0:
        N2 //= d
    
    if (N2-1)%d==0:
        ans += 1
    
ans += len(make_divs(N-1))-1
print(ans)

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    ans = {N}
    if N > 2: ans |= {N-1}
    for i in range(2, N): #N-1の約数ならばsubtractした後1になる。もしくはpow(k, x) == Nの場合
        if i ** 2 > N: break
        if (N - 1) % i == 0:
            ans |= {i}
            if i ** 2 < N - 1:
                ans |= {(N - 1) // i}
        if N % i == 0:
            k = N
            while k % i == 0:
                k //= i
            if k % i == 1: ans |= {i}
            if i ** 2 < N:
                k = N
                while k % i == 0:
                    k //= i
                if k % i == 1: ans |= {i}
    print(len(ans))
    #print(ans)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    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 = int(input())

tmp = n - 1
ret = len(make_divisors(tmp)) - 1

tmplen = make_divisors(n)

for item in tmplen:
    if item == 1:
        continue
    val = n
    while True:
        if val % item == 0:
            val = val // item
        else:
            if val % item == 1:
                ret += 1
            break

print(ret)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    if n == 2:
        print(1)
        exit()

    def al_div(n):
        pn = 1
        div = []
        while pn**2 < n:
            if n%pn == 0:
                div.append(pn)
                div.append(n//pn)
            pn += 1
        if pn**2 == n:
            div.append(pn)
        return div
    ans = 0
    for i in al_div(n-1):
        if i == 1:
            continue
        else:
            if n%i == 1:
                ans += 1
    for i in al_div(n):
        if i == 1:
            continue
        ni = n
        while ni%i == 0:
            ni //= i
        if ni%i == 1:
            ans += 1

    print(ans)

    return

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())
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
sys.setrecursionlimit(2000)
def joken(a,n):
  if n==1:
    return 0
  elif a%n==0 and a//n>=n:
    return joken(a//n,n)
  elif a%n==1:
    return 1
  elif a%n==0 and a//n==1:
    return 1
  else:
    return 0
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    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=int(input())
c=len(make_divisors(N-1))
d=make_divisors(N)
a=0
for i in range(len(d)):
  a+=joken(N,d[i])
print(a+c-1)

Submission status: Accepted

Solution code:
import math
import copy
def prime_factorize(n):
    a = [n]
    for i in range(2, math.floor(n ** 0.5) + 1):
        if n % i == 0:
            a.append(i)
            if n // i != i:
                a.append(n // i)
    return a

N = int(input())
prime_n = prime_factorize(N)
prime_n_1 = prime_factorize(N - 1)

ans = 0
for i in prime_n:
    n = copy.deepcopy(N)
    while (n % i) == 0:
            n = n // i
    if (n % i) == 1:
        ans += 1
ans += len(prime_n_1)
if N > 2:
    print(ans)
else:
    print(1)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    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]
ans = {N}
li1 = make_divisors(N-1)[1:]
for er in li1:
    ans.add(er)
li0 = make_divisors(N)[1:-1]
for i in li0:
    n = N
    while n % i == 0:
        n /= i
    if (n-1) % i == 0:
        ans.add(i)
print(len(ans))

Submission status: Accepted

Solution code:
N=int(input())
import math
a=0
for i in range(1,int(math.sqrt(N-1))+1):
  if (N-1)%i==0:
    a+=2
    i+=1
  else:
    i+=1
a-=1

if int(math.sqrt(N-1))==math.sqrt(N-1):
  a-=1
for i in range(2,int(math.sqrt(N))+1):
  if N%i==0:
    t=N
    while t%i==0:
      t=t/i
    if t%i==1:
      a+=1
      i+=1
    else:
      i+=1
a+=1
print(a)

Submission status: Accepted

Solution code:
N=int(input())
import math
ans=0
for i in range(1,int(math.sqrt(N-1))+1):
  if (N-1)%i==0:
    ans+=2
    i+=1
  else:
    i+=1
ans-=1

if int(math.sqrt(N-1))==math.sqrt(N-1):
  ans-=1
for i in range(2,int(math.sqrt(N))+1):
  if N%i==0:
    temp=N
    while temp%i==0:
      temp=temp/i
    if temp%i==1:
      ans+=1
      i+=1
    else:
      i+=1
ans+=1
print(ans)

Submission status: Accepted

Solution code:
# F - Division or Subtraction
def pf(x):
    plist = [1]
    p = 2
    while x>1:
        t = 0
        while x%p==0:
            x /= p
            t += 1
        now = list(plist)
        for i in range(t):
            now = list(map(lambda y:int(y*p), now))
            plist.extend(now)
        if p>int(x**0.5)+1:
            p = x
        elif p==2:
            p = 3
        else:
            p += 2
    return plist
        
N = int(input())
ans = len(pf(N-1))-1
for x in pf(N)[1:]:
    M = N
    while M>1 and M%x==0:
        M //= x
    if M==1 or M%x==1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
k=2
ans=1
factors=[]
i=1
while i*i<N-1:
  if (N-1)%i==0:
    ans+=1
  i+=1
while k*k<=N:
  n=0
  while pow(k,n)<=N:
    if (N-pow(k,n))%(pow(k,n+1))==0:
      ans+=1
      break
    n+=1
  k+=1
print(ans)

Submission status: Accepted

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def nu_of_factors1(n):
    result_set = set()
    sqrtn = int(n**0.5)
    for i in range(1,sqrtn+1):
        q, r = n/i, n%i
        if r == 0:
            result_set.add(q)
            result_set.add(i)
    return len(result_set)


def getDivisors(n):
    # Note that this loop runs till square root
    factors = []
    i = 1
    while i <= sqrt(n):

        if (n % i == 0):

            # If divisors are equal, print only one
            if (n / i == i):
                factors.append(i)
            else:
                # Otherwise print both
                factors.append(i)
                factors.append(n//i)
        i = i + 1
    return factors

n = INT()
ans = 0

ans+=nu_of_factors1(n-1) - 1

divisors = getDivisors(n)


for el in divisors:
    if(el!=1):
        temp = n
    else:
        continue

    flag = 1
    while(temp!=1):
        if((temp/el).is_integer()):
            temp/=el
            continue
        else:
            if(temp%el==1):
                ans+=1
            flag = 0
            break

    if(flag==1):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
"""
0, K, 2K, 3K, 4K, ... = N-1 のとき, 答え.
"""
def makediv(n):
	lower_divisors , upper_divisors = [], []
	i = 1
	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 = int(input())
ans = 0
themakedivlist = makediv(n-1)
for i in themakedivlist:
	if i >= 2:
		ans += 1
k = makediv(n)
k.remove(1)
for i in k:
	tmpn = n
	while True:
		if tmpn == 1:
			ans += 1
			break
		elif tmpn % i == 0:
			tmpn //= i
		elif (tmpn-1) % i == 0:
			ans += 1
			break
		else:
			break
print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    def divisor(n):
        res = []
        for i in range(1, int(np.sqrt(n)) + 1):
            if n % i == 0:
                res.append(i)
                j = n // i
                if j != i:res.append(j)
        res.sort(reverse = True)
        return res[::-1]
    n = int(input())
    div1 = divisor(n - 1)
    div2 = divisor(n)
    ans = len(div1) - 1
    for d in div2:
        if d == 1: continue
        nn = n
        while nn % d == 0:
            nn //= d
        if nn % d == 1:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import collections

N = int(input())

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

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    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]


c = collections.Counter(prime_factorize(N-1))
ans = 1
lis = make_divisors(N)

for i in c.values():
    ans *= i+1
ans -=1

for i in lis:
    if i==1:continue
    tmp = N
    while tmp%i==0:
        tmp //= i
    if tmp%i==1:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    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 = int(input())
l = make_divisors(n - 1)
l2 = make_divisors(n)
del l2[0]
ans = len(l) - 1
for i in l2:
    k2 = n
    while True:
        if k2 % i == 1:
            ans += 1
        k2 /= i
        if k2 % 1 != 0:
            break
print(ans)

Submission status: Accepted

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


L1 = factorization(N - 1)
s = 1
# print(L1)
for [a, b] in L1:
    s *= (b + 1)
# print(s)


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    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]


for i in set(make_divisors(N))-{1}:
    temp = N
    while temp % i == 0:
        temp //= i
    if (temp-1) % i == 0:
        s += 1
s -= 1
if N == 2:
    print(1)
else:
    print(s)

Submission status: Accepted

Solution code:
n=int(input())
orgn=n
m=n-1
orgm=m
ncounter=1
mcounter=1
for i in range(2,int(m**0.5)+1):
	if m % i == 0:
		tmpc=1
		m //= i
		while m % i ==0:
			tmpc += 1
			m //= i
		mcounter *= tmpc + 1

if m == orgm and m != 1:
	mcounter += 1
elif m > int(orgm**0.5):
	mcounter *= 2
mcounter -= 1


for i in range(2,int(n**0.5)+1):
	if orgn % i == 0:
		n = orgn // i
		while n % i ==0:
			n //= i
		if n % i == 1:
			ncounter += 1

print(ncounter+mcounter)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int):
    if N < 5:
        print(N - 1)
        return
    i = 2
    ret = 2
    while i * i <= N:
        tmp = N
        while tmp % i == 0:
            tmp //= i
        tmp %= i
        if tmp == 1:
            ret += 1

        if N % i == 1 and i * i + 1 != N:
            ret += 1
        i += 1
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
from math import sqrt
#N mod K = 0 or 1 となるk をさがす
#K = Nの約数　or N-1 の約数
def divisor(num):
    max_num = int(sqrt(num))
    divisor_list = []
    for i in range(1, max_num + 1):
        if num % i == 0:
            if i != 1:
                divisor_list.append(i)
            if num // i != 1:
                divisor_list.append(num//i)
    #sorted_divisor_list = sorted(divisor_list)
    return divisor_list

K_1 = divisor(N-1)
K_2 = divisor(N)
K_3 = []
count = 0
for k in K_2:
    temp = N
    while temp % k == 0:
        temp //= k
    if temp == 1 or temp % k == 1:
        count += 1
        K_3.append(k)
kk = K_1 + K_3
ans = len(set(kk))
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt, ceil


def divisors(n):
    out = []
    nn = ceil(sqrt(n))
    for i in range(1, nn):
        if n % i == 0:
            out.append(i)
            out.append(n//i)

    if nn ** 2 == n:
        out.append(nn)

    out.sort()
    return out


n = int(input())
a = len(divisors(n-1)[1:])

d = divisors(n)
for dd in d[1:]:
    nn = n
    while nn % dd == 0:
        nn = nn // dd
    if nn % dd == 1:
        a += 1

print(a)

Submission status: Accepted

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


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


def main():
    N = int(input())
    ans = 0
    for cand in divisors(N):
        if is_ok(N, cand):
            ans += 1
    for cand in divisors(N-1):
        if is_ok(N, cand):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

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

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

res = cnt - 1
for v in div[1:]:
    tmp = n
    while tmp % v == 0:
        tmp //= v
    if tmp % v == 1:
        res += 1

print(res)

Submission status: Accepted

Solution code:
n = int(input())

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    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]

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

divs1 = make_divisors(n - 1)
divs2 = make_divisors(n)
ans = set(divs1[1:])

for kk in divs2[1:]:
    A = n
    while True:
        if A % kk == 0:
            A //= kk
        else:
            break

    if (A - 1) % kk == 0:
        ans.add(kk)

ans.add(n)
print(len(ans))

Submission status: Accepted

Solution code:
n = int(input())
ans = set()
#n-1の約数は確定でOK

for i in range(1,int(pow(n-1,0.5)) + 1):
    if (n-1) % i == 0:
        ans.add((n-1)//i)
        ans.add(i)
#n = (1 + pk) * k^q の形になるkを探す。q ≠ 0のとき、kはnの約数
for i in range(2,int(pow(n,0.5)) + 1):
    if n % i == 0:
        tmp = n
        while tmp % i == 0:
            tmp = tmp // i
        if (tmp - 1) % i == 0:
            ans.add(i)
print(len(ans))

Submission status: Accepted

Solution code:

def check(N,K):
    while N % K == 0:
        N //= K
    return (N % K == 1)

def divisor(N):
    d = []
    K = 1
    while K*K <= N:
        if N % K == 0:
            d.append(K)
            if K*K != N:
                d.append(N//K)
        K += 1
    #ans += (N - 1)//K
    return d


N = int(input())

divi = divisor(N)

ans = 0

for x in divi:
    if x > 1:
        ans += int(check(N,x))

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

Submission status: Accepted

Solution code:
N = int(input())

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

    # divisors.sort()
    return divisors

ans = len(make_divisors(N-1))-1
ls = make_divisors(N)[1:]

for i in ls:
    n = N
    while n % i == 0:
        n //= i
    if n % i == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ans = 0
wnasi = []
for i in range(1, int(pow(N - 1, 0.5)) + 1):
    if (N - 1) % i == 0:
        wnasi.append(i)
        if i != (N - 1) // i:
            wnasi.append((N - 1) // i)
ans += len(wnasi) - 1
wari = []
for i in range(2, int(pow(N, 0.5)) + 1):
    if N % i == 0:
        wari.append(i)
        if i != N // i:
            wari.append(N // i)

for i in wari:
    if i == 1:
        continue
    tmpN = N
    while True:
        if tmpN % i == 0:
            tmpN //= i
        else:
            if tmpN % i == 1:
                ans += 1
            break

print(ans + 1)

Submission status: Accepted

Solution code:
N = int(input())

def divisors(n):
    ret1 = []
    ret2 = []
    i = 1
    while i**2 <= N:
        if n%i == 0:
            ret1 += [i]
            ret2 += [n//i]
        i += 1
    return ret1 + ret2

ans1 = len(set(divisors(N-1))) - 1
ans2_cand = set(divisors(N))
ans2 = 0
for k in ans2_cand:
    if k == 1: continue
    n = N
    while n%k == 0:
        n = n//k
    if n%k == 1:
        ans2 += 1


print(ans1 + ans2)

Submission status: Accepted

Solution code:
N = int(input())

def divisors(n):
    ret1 = []
    ret2 = []
    i = 1
    while i**2 <= N:
        if n%i == 0:
            ret1 += [i]
            ret2 += [n//i]
        i += 1
    return ret1 + ret2

ans1 = set(divisors(N-1))
ans2_cand = set(divisors(N))
ans2 = 0
for k in ans2_cand:
    if k == 1: continue
    n = N
    while n%k == 0:
        n = n//k
    if n%k == 1:
        ans2 += 1


print(len(ans1) + ans2 -1)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
# 候補はNかN-1の約数
answer = 0

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

cand = make_divisors(N) + make_divisors(N-1)
for x in cand:
    M = N
    while M % x == 0:
        M //= x
    r = M % x
    if r == 1:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:



N = int(input())

"""
愚直にやると、Kを2～Nの範囲で全部調べて数え上げる。N <= 10**12 なので間に合わない。


たとえば N=100だと、
[2, 3, 4, 9, 10, 11, 33, 99, 100]
が条件を満たす数字になる。

割り算を行わないとき、明らかに N % K = 1 になる
これは、「NをKで割ったら、１あまる」であるから、「N-1をKでわったら割り切れる」ともいえる。
なので、割り算が起こらないものは、N-1の約数。

割り算が起こるやつは、割れるだけ割った後、余りを調べればよい。
"""



def solve(n):
    i = 1
    ret = set()
    while i * i <= n:
        if n % i == 0:
            ret.add(i)
            ret.add(n // i)
        i += 1

    return ret


div_N_sub_1 = solve(N-1)
div_N = solve(N)

ans = len(div_N_sub_1) - 1

for i in div_N:
    if i == 1:
        continue
    tmp = N
    while tmp % i == 0:
        tmp //= i
    if tmp % i == 1:
        ans += 1


print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
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
u=len(make_divisors(n-1))-1
lis=make_divisors(n)
lis.remove(1)
#print(lis)
def divsub(n,k):
    flag=True
    while flag==True:
        n//=k
        if n%k==1:
            return 1
            flag=False
        elif n%k!=0:
            return 0
            flag=False
#print(divsub(10,5))
ans=0
for i in range(len(lis)):
    ans+=divsub(n,lis[i])
print(ans+u)

Submission status: Accepted

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

Nod = make_divisors(N-1)
divs = make_divisors(N)

for d in divs:
    c = N
    while True:
        if d == 1:
            break
        if c%d == 1:
            Nod.append(d)
            break
        elif c%d == 0:
            c = c//d;
            continue
        else:
            break

print(len(Nod)-1)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    max_i = int(math.log2(N))
    div = []
    for i in range(1,int(math.sqrt(N))+1):
        if N % i == 0:
            div.append((i,N//i)); div.append((N//i,i))

    ans = 0
    for a,b in div:
        if a == 1:
            for i in range(1,int(math.sqrt(b-1))+1):
                if (b-1) % i == 0:
                    p = 2 - (i*i == b-1) - (i == 1)
                    ans += p
        else:
            for i in range(1,max_i+1):
                c = round(math.pow(a,1/i))
                if c ** i == a:
                    if b % c == 1: ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

# 約数
# O(N**0.5)
def yakusu(N):
    ret = [[], []]
    for i in range(1, int(N ** 0.5)+1):
        if N % i == 0:
            ret[0].append(i)
            if i ** 2 != N:
                ret[1].append(N//i)
    return ret[0] + ret[1][::-1]

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