Problem:


Score : 600 points

Problem Statement

Given is a positive integer N.

We will choose an integer K between 2 and N (inclusive), then we will repeat the operation below until N becomes less than K.

Operation: if K divides N, replace N with N/K; otherwise, replace N with N-K.

In how many choices of K will N become 1 in the end?

Constraints

2 \leq N \leq 10^{12}

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the number of choices of K in which N becomes 1 in the end.

Sample Input 1

6

Sample Output 1

3

There are three choices of K in which N becomes 1 in the end: 2, 5, and 6.

In each of these choices, N will change as follows:

When K=2: 6 \to 3 \to 1

When K=5: 6 \to 1

When K=6: 6 \to 1

Sample Input 2

3141

Sample Output 2

13

Sample Input 3

314159265358

Sample Output 3

9



Sample input:
6


Sample output:
3

Submission status: Accepted

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

    # divisors.sort()
    return divisors

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

    # divisors.sort()
    return divisors

n=int(input())
l = make_divisors(n-1)
ans = len(l)

l2 = make_divisors2(n)
for i in l2[1:]:
    n1 = n
    while n1%i == 0:
        n1 = n1//i
    if n1%i == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()
from math import sqrt


def factor(n):
    """
    nの約数を個数と共にリストにして返す。
    ただしあとの都合上１は除外する。
    """

    if n == 1:
        return 0, []
    if n == 2:
        return 1, [2]
    if n == 3:
        return 1, [3]

    d = int(sqrt(n))
    num = 1
    factor_pre = []
    factor_post = [n]
    for i in range(2, d):
        if n % i == 0:
            factor_pre.append(i)
            factor_post.append(n // i)
            num += 2
    if d * d == n:
        factor_pre.append(d)
        num += 1
    elif n % d == 0:
        factor_pre.append(d)
        factor_post.append(n // d)
        num += 2
    factor_post.reverse()
    return num, factor_pre + factor_post


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

    """
    題を満たすKは、
        N = K^e * n、(n, K) = 1
    として
        n = K * m + 1 (m ¥in ¥mathbb{N})
    とかければ良い。

    ２つ目の式からnとKが互いに素なのは明らかなので、問題文は
        N = K^e * (K * m + 1) (m ¥in ¥mathbb{N})
    なるKを求めることに同値。

    なのでまずはNの約数を全列挙して、あとはNをそれで割った商がKで割って1余るか確かめれば良い。
    """

    _, fact = factor(N)
    ans, ans_list = factor(N - 1)
    # print(ans_list)

    # print("Now we check the list {}".format(fact))
    for K in fact:
        n = N
        while n % K == 0:
            n //= K
        if n % K == 1:
            ans += 1
            ans_list.append(K)
            # print("{} added".format(K))
    # print("ans={}: {}".format(ans, ans_list))
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
 
N = int(input())
 
 
def divisor(N):
    x = np.arange(1, int(N**(1/2))+1, dtype=np.int64)
    div = set(x[N % x == 0])
    return div | set(N // x for x in div)
 
 
cand = divisor(N) | divisor(N - 1)
 
 
def test(N, K):
    if K == 1:
        return False
    while N % K == 0:
        N //= K
    return N % K == 1
 
 
answer = sum(test(N, d) for d in cand)
print(answer)

Submission status: Accepted

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

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

    ans |= (trial_division(N))
    ans |= (trial_division(N-1))
    answer = 0
    for k in ans:
        cur = N
        while cur % k == 0 and cur != 1:
            cur //= k
        if cur == 1 or cur % k == 1:
            answer += 1
    print(answer)


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

ans = len(make_divisors(N-1)) - 1
#print(ans)

divisors = make_divisors(N)
def dfs(x,N):
    while N % x == 0:
        N //= x
#        print(N)
    N %= x
#    print(N)
    return N == 1

counta = 0
for i in range(1,len(divisors)):
    if dfs(divisors[i],N):
        counta += 1
#print(counta)
ans += counta

print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
if N == 2:
    print(1)
else:
    ans = [N-1,N]

    #N-1
    for i in range(2,int(math.sqrt(N-1)+1)):
        if (N-1) % i == 0:
            ans.append(i)
            if i != (N-1)//i:
                ans.append((N-1)//i)

    #N
    for j in range(2,int(math.sqrt(N))+1):
        if N % j == 0:
            n1 = N
            n2 = N
            while n1 % j == 0:
                n1 = n1/j
            if n1 % j == 1:
                ans.append(j)
            if j != N//j:
                while n2 % N//j == 0:
                    n2 = n2*j//N
                if n2 % j == 1:
                    ans.append(N//j)
        
    print(len(ans))

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from copy import deepcopy

def sieve(n):
    prime = []
    limit = n ** 0.5
    data = [i + 1 for i in range(1,n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e%p != 0]


def main():
    primes = sieve(1000005)
    n = int(input())
    div = set()
    for i in range(2,int(n ** 0.5) + 1):
        if n%i == 0:
            div.add(i)
            div.add(n//i)
    
    ans = 0
    for d in div:
        k = deepcopy(n)
        while k%d == 0:
            k //= d
        if k%d == 1:
            ans += 1
    
    m2 = n - 1
    cnt = 1
    for p in primes:
        tmp = 1
        while  m2%p == 0:
            m2 //= p
            tmp += 1
        cnt *= tmp           
    
    if m2 != 1:
        cnt *= 2
    
    print(ans + cnt)

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
from math import sqrt
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def is_ok(n, k):
    while n % k == 0:
        n //= k
    if n < k:
        return n == 1
    else:
        return n % k == 1


def prime_enumeration(n):
    div = []
    for i in range(1, int(sqrt(n))+1):
        if n % i == 0:
            if i != 1:
                div.append(i)
            if n // i != i:
                div.append(n // i)

    #div.sort()
    return div


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

    div_n = prime_enumeration(N)
    div_n1 = prime_enumeration(N-1)
    #print(div_n)
    #print(div_n1)

    ans = 0
    for d in div_n:
        if is_ok(N, d):
            ans += 1
    
    for d in div_n1:
        if is_ok(N, d):
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

ans = []
# KがNの約数ではないとき、割り算を適用しない
# つまり、あまりが1となるようなKを考える
# よって、N-1の約数を1以外カウント
i = 1
while i * i <= (N - 1):
    if (N - 1) % i == 0:
        ans.append(i)
        if i * i != (N - 1):
            ans.append((N - 1) // i)
    i += 1

# NがKの倍数のとき、つまりKがNの約数のとき
divisor = []
i = 1
while i * i <= N:
    if N % i == 0:
        divisor.append(i)
        if i * i != N:
            divisor.append(N // i)
    i += 1

# 約数のそれぞれに対し、実際に操作を行ってみる
for d in divisor:
    if d == 1:
        continue
    tmp_N = N
    while tmp_N % d == 0:
        tmp_N = tmp_N // d
    if tmp_N % d == 1:
        ans.append(d)

print(len(set(ans)) - 1)

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 = make_divisors(N-1)
del ans[0]
cand = make_divisors(N)
del cand[0]
for one in cand:
    n = N
    while True:
        if n%one==0:
            n = n//one
        else:
            if n%one==1:
                ans.append(one)
            break

print(len(ans))

Submission status: Accepted

Solution code:
N = int( input() )
C = 0

def ch(k):
  global C
  if k < 2:
    return
  
  n = N
  while (n >= k) and (n%k == 0):
    n = n // k
  if ( n%k == 1 ):
    C += 1
  return

#　k = 1
ch(N)
ch(N-1)
#
nn = int( N**0.5 )
for k in range(2,nn+1):
  z = N%k
  if z <= 1:
    ch(k)
    k2 = N//k
    if k!=k2:
      ch(k2)
#
print(C)

Submission status: Accepted

Solution code:
import math
N = int(input())
M = int(math.sqrt(N))
M2 = int(math.sqrt(N-1))
y = []
for i in range(1,M2+1):
    if (N-1)%i == 0:
        m = (N-1)//i
        if not m == 1:
            y.append(m)
        if i == 1 or i == m:
            continue
        else:
            y.append(i)
count = len(y)

y = []
for i in range(1,M+1):
    if N%i == 0:
        m = N//i
        y.append(m)
        if i == 1 or i == m:
            continue
        else:
            y.append(i)

for i in y:
    NN = N
    while NN%i == 0:
        NN /= i
    # print(NN)
    if int(NN) % i == 1:
        count += 1
        # print(i)

print(count)

Submission status: Accepted

Solution code:
import math


N = int(input())

nn = int(math.sqrt(N))
# nn = int(N / 2)

ans = 1
for x in range(2,nn+1):

    if N % x == 1:
        ans += 1
        continue
    
    if N % x > 1:
        continue

    tmp = N
    while tmp > x:
        tmp = tmp / x
        if tmp % x == 1 :
            ans += 1
            break
        elif tmp % x > 1 :
            break
        elif tmp == x:
            ans += 1
            break

x = 1
tmp = N - 1
while tmp / x  > nn:
    if tmp % x == 0:
        ans += 1
    x += 1

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
N = int(input())
ans = 0
divisors = []

for i in range(2, int(sqrt(N))+1):
    if N%i==0:
        divisors.append(i)
        divisors.append(N//i)

for d in set(divisors):
    i = 1
    while N%(d**i)==0:
        i += 1
    n = N//(d**(i-1))
    if n%d==1:
        ans+=1

for i in range(2, int(sqrt(N))+1):
    if (N-1)%i==0:
        if i**2!=N-1:
            ans += 2
        else:
            ans += 1
if N==2:
    print(1)
else:
    print(ans+2)

Submission status: Accepted

Solution code:
import math
import copy

n = int(input())
m = int(math.sqrt(n)+.1)+1

def f(x):
    a = copy.copy(n)
    while a%x == 0:
        a /= x
    return a%x == 1

ans = {n}
if n > 2:
    ans.add(n-1)

for k in range(2,m):
    if (n-1)%k == 0:
        ans.add(k)
        ans.add((n-1)//k)
    elif f(k):
        ans.add(k)
print(len(ans))

Submission status: Accepted

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

def main():
    N=int(input())
    ans=len(make_devisor(N-1))-1
    d=make_devisor(N)
    for i in d:
        if i==1:
            continue
        tmp=0
        n=N
        while tmp==0:
            n//=i
            tmp=n%i
        if tmp==1:
            ans+=1
    print(ans)

main()

Submission status: Accepted

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

N = int(input())


class Prime(object):
    @staticmethod
    def is_prime(n: int) -> bool:
        """
        素数判定
        >>> p = Prime()
        >>> p.is_prime(2)
        True
        >>> p.is_prime(43)
        True
        >>> p.is_prime(4)
        False
        """

        if n == 1:
            return False
        if n == 2:
            return True

        for i in range(2, n):
            if n % i == 0:
                return False
            if i * i > n:
                return True

    @staticmethod
    def divisor(n: int, sort: bool = False) -> list:
        """
        約数列挙
        >>> p = Prime()
        >>> p.divisor(6)
        [1, 2, 3, 6]
        """
        res = []
        if n == 1:
            return [1]

        for i in range(1, n):
            if n % i == 0:
                res.append(i)
                if i != n / i:
                    res.append(int(n / i))
            if (i+1) * (i+1) > n:
                if sort:
                    res.sort()
                return res


# N-1の約数：1以外が全て当てはまる
temp1 = Prime.divisor(N - 1, sort=False)
# print(temp1)
cnt1 = len(temp1) - 1

# Nの約数K：Kで割り切った後でN % K == 1かどうかを見る
temp2 = Prime.divisor(N, sort=True)[1:]
# print(temp2)
cnt2 = 0

for temp in temp2:
    a = N
    while a % temp == 0:
        a = a / temp
    if a % temp == 1:
        cnt2 += 1

print(cnt1 + cnt2)

Submission status: Accepted

Solution code:
N = int(input())
def divisor(x):
  ret = set()
  for i in range(1,int(x**0.5+1)):
    if x%i == 0:
      ret.add(i)
      ret.add(x//i)
  return ret

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

Submission status: Accepted

Solution code:
import math
def solve():
    n = int(input())

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

    print(ans)

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

if __name__ == '__main__':
    solve()

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()
    divisors.remove(1)
    return divisors

ans = make_divisors(n-1) #n-1の約数(1以外)を列挙し、それらは対象になる
y = make_divisors(n) #nの約数を列挙

for i in y:
    z = n
    while z >= i and z%i == 0: #割り切れるところまで割る(nがi以上のとき)
        z = int(z / i)
        if z % i == 1: #z(=余り)が1だったら
            ans.append(i)
            break

set(ans)
#print(ans)
print(len(ans))

Submission status: Accepted

Solution code:
#ABC161-F Division or Substraction
"""
nとn-1の約数の個数が答え
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())

"""約数の個数"""
#参考：青チャp280
#注意：1も約数としてカウントされる
def factrize(n):
    b = 2
    fct = []
    while b*b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b+1
    if n > 1:
        fct.append(n)
    if len(fct) == 1: #素数だった場合
        return 2 #1と、その数の2通り
    
    divisor = dict()
    for i in fct:
        if not i in divisor:
            divisor[i] = 1
        else:
            divisor[i] += 1
    ans = 1
    for i in divisor.values():
        ans *= (i+1)
    return ans
def factrize_all(n):
    b = 2
    fct = []
    while b*b <= n:
        if n%b == 0:
            fct.append(b)
        b += 1
    return fct + [n]

ans = 0
res2 = []
for i in factrize_all(n):
    res = n
    while True:
        if res == 0:
            break
        if res%i != 0:
            res2.append([i,res])
            break
        res = res//i

for i,j in res2:
    if j%i == 1:
        ans += 1

print(ans+factrize(n-1)-1) #1を2回引く

Submission status: Accepted

Solution code:
from math import sqrt, ceil

def factors_set(number):
    factors = set()
    for i in range(1, ceil(sqrt(number))+1):
        if number % i == 0:
            factors.add(i)
            factors.add(number // i)
    return factors

N = int(input())

Ks = factors_set(N-1) | factors_set(N)
Ks.remove(1)

ans = 0
for K in Ks:
    N_tmp = N
    while N_tmp % K == 0:
        N_tmp //= K
    if N_tmp % K == 1:
        ans += 1

print(ans)

Submission status: Accepted

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

N = int(input())
ans = len(make_divisors(N-1))
N_divisors = make_divisors(N)
for divisor in N_divisors:
    x = N
    while x % divisor == 0:
        x /= divisor
    if x % divisor == 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

def all_pattern(l):
    global n
    ans=0
    for ds in make_divisors(l)[1:]:
        k=n
        while k%ds==0:
            k//=ds
        ans+=(k%ds==1)
    return ans

n=int(input())
print(all_pattern(n)+all_pattern(n-1))

Submission status: Accepted

Solution code:
def divisors(N):
  result = {1, N}
  for i in range(2, int(N**0.5)+2):
    if N % i == 0:
      result.add(i)
      result.add(N//i)
  return result

N = int(input().strip())
if N == 2: print(1)
else:
  ans = len(divisors(N-1))-1
  for k in divisors(N):
    if k == 1: continue
    n = N
    while n%k == 0: n = n//k
    if n%k == 1: ans += 1
  print(ans)

Submission status: Accepted

Solution code:
n = int(input())

divisors = set()
for i in range(1, int(-(-n**.5//1))+1):
    if n % i == 0:
        divisors |= {i, n//i}

ans = set()
for div in divisors:
    x = n
    if div == 1:
        continue
    while x % div == 0:
        x = x//div
    if x % div == 1:
        ans |= {div}


n -= 1
for i in range(1, int(-(-n**.5//1))+1):
    if n % i == 0:
        ans |= {i, n//i}

ans ^= {1}
print(len(ans))

Submission status: Accepted

Solution code:
#!/usr/bin/python3

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

n = int(input())
c = 0

#n = ak + 1
c += len(calcDivisors(n - 1)) - 1

#n = k^n(ak + 1)
divs = calcDivisors(n)
divs.sort()
for k in divs[1:]:
    r = n
    while r % k == 0:
        r //= k
    if r % k == 1:
        c += 1

print(c)

Submission status: Accepted

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

def all_pattern(l):
    global n
    ans=0
    for ds in make_divisors(l)[1:]:
        k=n
        while k%ds==0:
            k//=ds
        ans+=(k%ds==1 or k-k%ds==1)
    return ans

n=int(input())
print(all_pattern(n)+all_pattern(n-1))

Submission status: Accepted

Solution code:
n = int(input())

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

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

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

print(ans)

Submission status: Accepted

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

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

for d in divs:
    if d==1:
        continue
    
    N2 = N
    
    while N2%d==0:
        N2 //= d
    
    if (N2-1)%d==0:
        ans += 1

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

Submission status: Accepted

Solution code:
n=int(input())
ans=0
s=dict()
s[n]=0
for i in range(1,int(n**0.5)+1):
  if n%(i+1)==0:
    if i+1 not in s:
      s[i+1]=0
    if n//(i+1) not in s:
      s[n//(i+1)]=0
s=list(s.items())
for i,j in s:
  if i==1:
    continue
  l=n
  while l%i==0:
    l//=i
  if l%i==1:
    ans+=1
d=dict()
k=n-1
for i in range(1,int((n-1)**0.5)+1):
  t=0
  while k%(i+1)==0:
    k//=(i+1)
    t+=1
  if t>0:
    if i+1 not in d:
      d[i+1]=t
    else:
      d[i+1]+=t
if k>1:
  if k not in d:
    d[k]=1
  else:
    d[k]+=1
d=list(d.items())
m=1
for p,root in d:
  m*=(root+1)
print(ans+m-1)

Submission status: Accepted

Solution code:
import math

N = int(input())

# 割れるだけ割る
KMAX = math.floor(math.sqrt(N)) + 1

Kn = [N]  # N の約数であるような K
Kn1 = [N-1]  # N - 1 の約数であるような K

# N の約数であるような K (Kn)を求める
for K in range(2,KMAX):
    
    if N % K == 0:
        Kn.append(K)
        tmp = N//K
        if tmp == K:
            continue
        Kn.append(N//K)
        
Knn = []

# Kn のうち、割れるだけ割った(tN)あと、tN mod Kn == 1 であるような Kn
for K in Kn:
    tN = N
    while tN % K == 0:
        tN = tN // K  # K で割れなくなるまで割る
    
    if (tN - 1) % K == 0:
        Knn.append(K)
        
# N-1 の約数であるような K を求める
for K in range(2,KMAX):

    if (N - 1) % K == 0:
        Kn1.append(K)
        tmp = (N-1) // K
        if tmp == K:
            continue
        Kn1.append(tmp)

Knn.extend(Kn1)
if 1 in Knn:
    Knn.remove(1)
print(len(Knn))

Submission status: Accepted

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

def div_or_sub(n, k):
    while k <= n:
        if n % k == 0:
            n //= k
        else:
            n %= k
    return n

n = int(input())
cnt = len(calc_divisors(n - 1)) - 1
n_divisors = calc_divisors(n)
for divisor in n_divisors[1:]:
    if div_or_sub(n, divisor) == 1:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from math import sqrt

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

N = int(input())

# N-1 mod K == 0 となる K の数
res = 0
res += len(make_divisors(N-1))
res -= 1 # 1 は今回の条件から除外

# N mod K == 0 となる K で N を割り切れなくなるまで割った後に mod が 1 になる数
divisors = make_divisors(N)
divisors.remove(1)
for d in divisors:
    n = N
    while n != 0 and n % d == 0:
        n /= d
    if n % d == 1:
        res += 1

print(res)

Submission status: Accepted

Solution code:
import sys
from math import sqrt, floor

def divisors(n):
    res = set()
    for i in range(1, floor(sqrt(n)) + 1):
        if not n % i:
            res.add(i)
            res.add(n // i)
    return res - set([1])

n = int(sys.stdin.readline().rstrip())

def main():
    res = divisors(n - 1) 
    cnt = len(res)
    for i in divisors(n):
        m = n
        while not m % i:
            m //= i
        if (m - 1) % i == 0:
            cnt += 1
    print(cnt)

if __name__ ==  '__main__':
    main()

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:
import math
N = int(input())

k = 2
res = 0

ts = set()
kn = {N}
kn_1 = {N-1}
while k <= math.sqrt(N):
    if N % k == 0:
        nk = N//k
        while nk % k == 0:
            nk //= k

        if nk % k == 1:
            kn.add(k)
        if k % nk == 1:
            kn.add(nk)

        ts.add(k)
        ts.add(nk)

    if (N-1) % k == 0:
        kn_1.add(k)
        kn_1.add((N-1)//k)

    k+=1

kn_1 -= {1}
print(len(kn)+len(kn_1))

Submission status: Accepted

Solution code:
n,a=int(input()),1
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+(n>2))

Submission status: Accepted

Solution code:
import sys
from math import sqrt, floor

def divisors(n):
    res = set()
    for i in range(1, floor(sqrt(n)) + 1):
        if n % i == 0:
            res.add(i)
            res.add(n // i)
    return res - set([1])

n = int(sys.stdin.readline().rstrip())

def main():
    res = divisors(n - 1) 
    cnt = len(res)
    for i in divisors(n):
        if i in res: continue
        m = n
        while m % i == 0:
            m //= i
        if (m - 1) % i == 0:
            cnt += 1
    print(cnt)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    N = int(input())
    
    table1 = set()
    i = 1
    while i*i <= N:
        if N%i == 0:
            table1.add(i)
            table1.add(N//i)
        i += 1
    
    cnt = 0
    for p in table1:
        if p == 1:
            continue
        n = N
        while n % p == 0:
            n = n // p
        if n % p == 1:
            cnt += 1
    
    table2 = set()
    N -= 1
    j = 1
    while j*j <= N:
        if N % j == 0:
            table2.add(j)
            table2.add(N//j)
        j += 1

    res = cnt + len(table2) - 1     # table2 に含まれる 1 を除外
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s=set()
a=s.add
def f(n):
  for i in range(1,int(n**.5)+1):
    if n%i<1:
      a(i)
      if i!=n//i:a(n//i)
n=int(input())
f(n-1),f(n)
a=0
for i in s-{1}:
  m=n
  while m%i<1:m//=i
  a+=m%i<2
print(a)

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
  m = n
  while m%i == 0:
    m//=i
  if m%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:
def f(n):
  d=[]
  for i in range(1,int(n**0.5)+1):
    if n%i<1:
      d+=i,
      if i!=n//i:d+=n//i,
  return d[1:]
n=int(input())
a=f(n-1)
for i in f(n):
  m=n
  while m%i<1:m//=i
  if m%i<2:a+=i,
print(len(set(a)))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

div = []
ans = 0

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

for d in div:
    if d == 1: continue
    tmp = N
    while tmp % d == 0:
        tmp //= d
    if tmp % d == 1:
        ans += 1    

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

print(ans + len(div2)-1)

Submission status: Accepted

Solution code:
def make_yakusuu(n):
    r_list = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            r_list.append(i)
            r_list.append(n // i)
        i += 1
    return sorted(r_list)
n = int(input())
tmp = make_yakusuu(n)
out = []
for i in tmp:
    m = n
    if i == 1:
        continue
    while m % i == 0:
        m //= i
    if m % i == 1 or m % i == 0:
        out.append(i)

out += make_yakusuu(n - 1)
print(len(set(out)) - 1)

Submission status: Accepted

Solution code:
import sys,math,copy,queue,itertools,bisect
NI = lambda : int(sys.stdin.readline())
INF = 10**18

N = NI()
if N == 2:
    print (1)
    exit (0)
ans = 0
max_b = int(math.log(N,2))
for x in range(2,int(math.sqrt(N-1))+1):
    if (N-1) % x == 0:
        if (N-1) == x**2:
            ans += 1
        else:
            ans += 2
for x in range(1, int(math.sqrt(N)) + 1):
    if N % x == 0:
        for b in range(1,max_b+1):
            k = round(x**(1/b))
            if k**b == x and k > 1:
                if (N//x-1) % k == 0:
                    ans += 1
            if x**2 != N:
                x = N // x
                k = round(x ** (1 / b))
                if k ** b == x and k > 1:
                    if (N // x - 1) % k == 0:
                        ans += 1

print(ans+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)

    #divisors.sort()
    return divisors

ans = 2
N = int(input())

div = make_divisors(N)
div_1 = make_divisors(N-1)
ans = 0
for i in div:
    p = N
    if i == 1:
        continue
    while p%i == 0:
        p = p//i
    if p%i == 1:
        ans +=1

print(ans + len(div_1)-1)

Submission status: Accepted

Solution code:
import sys

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

N = ir()

def make_divisors(n): # nの約数を列挙、1を除く
    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:]

d1 = make_divisors(N-1)
answer = len(d1)
d2 = make_divisors(N)
for x in d2:
    M = N
    while M%x == 0:
        M //= x
    if M%x == 1:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
n = int(input())

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



ls = divisor(n-1)
ls2 = divisor(n)
a1 = len(ls)-1
a2 = 0
for num in ls2:
    cnt = 1
    s = n
    if num ==1:
        continue
    while True:
        if s % num ==0:
            s = s//num
        else:
            if s % num ==1:
                a2 +=1
            break
print(a1+a2)