Problem:


Score : 600 points

Problem Statement

Given is a positive integer N.

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

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

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

Constraints

2 \leq N \leq 10^{12}

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

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

Sample Input 1

6

Sample Output 1

3

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

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

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

When K=5: 6 \to 1

When K=6: 6 \to 1

Sample Input 2

3141

Sample Output 2

13

Sample Input 3

314159265358

Sample Output 3

9



Sample input:
6


Sample output:
3

Submission status: Wrong Answer

Solution code:
N = int(input())

import collections
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):
    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

y = 0

m = 0
# print("m,n=",0,1)
k = N
# print("m,n=",m,1)
# print("k=",k)
y += 1

for n in range(2,40):
    # print("m,n=",m,n)
    t = N**(1/n)
    for k in range(int(t),int(t)+2):
        if N == k**n:
            # print("m,n=",m,n)
            # print("k=",k)
            y += 1

n = 0
c = collections.Counter(prime_factorize(N-1))
a = 1
# print(c)
for i in c.values():
    a *= i+1
# print("a=",a)
y += a

n = 1
for k in make_divisors(N):
    if N>k>=2 and (N-k)%k**2==0:
        # print(k)
        y += 1

for m in range(1,100000):
    for n in range(2,20000):
        # print("")
        # print("( m,n=",m,n,")")
            
        l = (N/(m+0.5))**(1/(n+1))
        r = (N/m)**(1/(n+1))
        # print("m,n=",m,n)
        # print("l={},r={}".format(l,r))
        if int(l) == int(r) or r<2:
            break
        else:
            for k in range(int(l)+1,int(r)+1):
                if N == k**n*(k*m+1):
                    # print("m,n=",m,n)
                    # print("k=",k)
                    y += 1
      
print(y-1)
"""
for k in range(2,3):
    n = N
    # print(n)
    while n % k == 0:
        n = n//k
        print(n)
    if n % k == 1:
        print(k)
"""

Submission status: Wrong Answer

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:
        tmp //= cand
    if tmp == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

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(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:
        tmp //= cand
    if tmp == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
def yaku(n):
    a=[]
    s=int(math.sqrt(n))
    for i in range(2,s+1):
        if n%i==0:
            a.append(i)
            a.append(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
    while n>=i:
        n-=i
    if n==1:
        ans+=1
print(ans+1)

Submission status: Wrong Answer

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))
    # 割り算をする場合
    l = make_divisors(n)[1:]  # 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: Wrong Answer

Solution code:
N = int(input())


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

Solution code:
N = int(input())


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+100):
        if i >= temp / 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: Wrong Answer

Solution code:
N = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if i >= temp / 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: Wrong Answer

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
            
print(len(a))

Submission status: Wrong Answer

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)
        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])
print(len(q)+2)

Submission status: Wrong Answer

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(2)
else:
    print(len([i for i in gen_divs(n) if divthensub(n, i)]) + len(gen_divs(n - 1)) + 2)

Submission status: Wrong Answer

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())
print(len([i for i in gen_divs(n) if divthensub(n, i)]) + len(gen_divs(n - 1)) + 2)

Submission status: Wrong Answer

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

    finds = [N]
    for n in range(2, N):
        print(n)
        if n == 2:
            finds.append(n)
            continue

        if N % n == 1:
            finds.append(n)
            continue

        if N % n == 0:
            div = N / n
            if div < n and N % div != 1:
                continue
            if N % div == 0:
                finds.append(n)
                continue

    print(len(finds))


divSub()

Submission status: Wrong Answer

Solution code:
N = int(input())

def factorization(n):
    arr = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i]=cnt

    if temp!=1:
        arr[temp] = 1

    if arr==[]:
        arr[n] = 1

    return arr

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
fact_d = factorization(N)
ans += len(make_divisors(N-1))-1

for fact in fact_d:
    for i in range(1, fact_d[fact]+1):
        divided_N = N
        while 1:
            divided_N //= fact**i
            if divided_N%fact != 0:
                break
            if divided_N == 0:
                break
        if divided_N%(fact)**i==1:
            ans+=1

if len(fact_d) != 1:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

def factorization(n):
    arr = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i]=cnt

    if temp!=1:
        arr[temp] = 1

    if arr==[]:
        arr[n] = 1

    return arr

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
fact_d = factorization(N)
ans += len(make_divisors(N-1))-1

for fact in fact_d:
    for i in range(1, fact_d[fact]+1):
        divided_N = N
        while 1:
            divided_N //= fact
            if divided_N%fact != 0:
                break
        if divided_N%(fact)**i==1:
            ans+=1

print(ans+1)

Submission status: Wrong Answer

Solution code:
import numpy as np
 
N = int(input())
 
 
def divisor(N):
    x = np.arange(1, int(N**(1/2)), 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: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
 
N = int(read())
 
 
def divisor(N):
    x = np.arange(1, int(N**(1/2)), 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: Wrong Answer

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


def factor(n):
    """
    nの約数を個数と共にリストにして返す。
    ただしあとの都合上１は除外する。
    """
    d = int(sqrt(n))
    num = 1
    factor_pre = []
    factor_post = [n]
    for i in range(2, d + 1):
        if n % i == 0:
            factor_pre.append(i)
            factor_post.append(n // i)
            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, _ = factor(N - 1)
    for K in fact:
        n = N
        while n % K == 0:
            n //= K
        if n % K == 1:
            ans += 1
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline
def make_divisors(n):
    divisors = []
    for i in range(2, 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())
    ret=1
    div=make_divisors(N)
    div=div+make_divisors(N-1)
    div.append(N)
    for k in div:
        n=N
        while n%k==0:
            n=n//k
        ret += n%k==1
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
if N == 2:
    print(2)
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: Wrong Answer

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

Solution code:
import math
N = int(input())
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
        while n2 % N//j == 0:
            n2 = n2*j//N
        
        
        if n1 % j == 1:
            ans.append(j)
        if n2 % j == 1:
            ans.append(N//j)


print(len(ans))

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
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
        while n2 % N//j == 0:
            n2 = n2*j//N
        
        
        if n1 % j == 1:
            ans.append(j)
        if n2 % j == 1:
            ans.append(N//j)

print(ans)
print(len(ans))

Submission status: Wrong Answer

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:
            if N//one==n:
                ans.append(one)
                break
            n = N//one
        else:
            if n%one==1:
                ans.append(one)
            break

print(len(ans))

Submission status: Wrong Answer

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)

for one in cand:
    n = N
    while True:
        if n%one==0:
            if N//one==n:
                break
            n = N//one
        else:
            if n%one==1:
                ans.append(one)
            break
print(len(ans))

Submission status: Wrong Answer

Solution code:
import math


N = int(input())

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

ans = 2
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 = 2
tmp = N - 1
while tmp / x  > nn:
    if tmp % x == 0:
        ans += 1
    x += 1

print(ans)

Submission status: Wrong Answer

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
        y.append(m)
        if i == 1 or i == m:
            continue
        else:
            y.append(i)
count = len(y)
y = []
for i in range(1,M2+1):
    if N%i == 0:
        m = N//i
        y.append(m)
        if i == 1 or i == m:
            continue
        else:
            y.append(i)
# print(y)
for i in y:
    NN = N
    while NN%i == 0:
        NN /= i
    if int(NN) % i == 1:
        count += 1
        # print(i)

print(count)

Submission status: Wrong Answer

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)
        if i**2!=N:
            divisors.append(N//i)

for d in 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
print(ans+2)

Submission status: Wrong Answer

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

def ch(k):
  global C
  n = N%k
  if k < 2:
    return
  if n > 1:
    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)

while 1:
  k += 1
  k2 = N//k
  k3 = (N-1)//k
  if k > k3:
    break
  ch(k)
  if k2 != k:
    ch(k2)
  if (k3 != k) and(k3 != k2):
    ch(k3)
#
print(C)

Submission status: Wrong Answer

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

def ch(k):
  global C
  n = N%k
  if n > 1:
    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)

while 1:
  k += 1
  k2 = N//k
  k3 = (N-1)//k
  if k > k3:
    break
  ch(k)
  if k2 != k:
    ch(k2)
  if (k3 != k) and(k3 != k2):
    ch(k3)
#
print(C)

Submission status: Wrong Answer

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

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

#
k = 1
ch(N)
ch(N-1)

while 1:
  k += 1
  k2 = N//k
  k3 = (N-1)//k
  if k > k3:
    break
  ch(k)
  if k2 != k:
    ch(k2)
  if (k3 != k) and(k3 != k2):
    ch(k3)
#
print(C)

Submission status: Wrong Answer

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

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
        y.append(m)
        if not i == 1:
            y.append(i)
count = len(y)
y = []
for i in range(2,M+1):
    if N%i == 0:
        m = N//i
        y.append(m)
        if not i == 1:
            y.append(i)

for i in y:
    while N%i == 0:
        N = N/i
    if N % i == 1:
        count += 1
        break

print(count+1)

Submission status: Wrong Answer

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)%1
        y.append(m)
        if not i == 1:
            y.append(i)
count = len(y)
divsion = []
for i in range(2,M+1):
    if N%i == 0:
        divsion.append(i)

for i in divsion:
    while N%i == 0:
        N = N/i
    if N % i == 1:
        count += 1
        break

print(count+1)

Submission status: Wrong Answer

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

divsion = []
for i in range(2,M+1):
    if N%i == 0:
        divsion.append(i)

for i in divsion:
    while N%i == 0:
        N = N/i
    if N % i == 1:
        count += 1
        break

print(count+1)

Submission status: Wrong Answer

Solution code:
from math import sqrt, ceil

def factors_set(number):
    factors = set()
    for i in range(1, ceil(sqrt(number))):
        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: Wrong Answer

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

def ch(k):
  global C
  n = N
  while n%k == 0:
    n = n // k
  if ( n%k == 1 ):
    C += 1

#
k = 1
ch(N)
ch(N-1)

while 1:
  k += 1
  k2 = N//k
  k3 = (N-1)//k
  if k > k3:
    break
  ch(k)
  if k2 != k:
    ch(k2)
  if (k3 != k) and(k3 != k2):
    ch(k3)
#
print(C)

Submission status: Wrong Answer

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:
        z = z // i
    if z % i == 1:
        ans.append(i)        

set(ans)
print(len(ans))

Submission status: Wrong Answer

Solution code:
import collections
from itertools import combinations
from functools import reduce
import fractions
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 gcd(*numbers):
    return reduce(fractions.gcd, numbers)

L = collections.Counter(prime_factorize(N-1))
# print(L)
A = 1
for i,v in L.items():
    A *= (v+1)
# 1を抜く
A -= 1 

c = collections.Counter(prime_factorize(N))
prime = list(dict(c).keys())
d = []
for i in range(1,len(c)):
    d += list(combinations(prime,i))
be = list(c.values())


D = 0
if len(be) > 1:
    # print(be)
    beki = gcd(be)
else:
    beki = be[0]
    while beki%2 == 0:
        beki = beki //2
        D += 1

# C = 1
# for i,v in L.items():
#     C *= (v+1)
# C -= 1

B = 1
# print(c)
for divisor in d:
    a = N
    b = 1
    # print(divisor)
    for i in divisor:
        a /= (i ** c[i])
        b = i
    # print(a,b)
    for j in range(c[i]):
        b = b**(j+1)
        if a > b:
            amari = a%b
            # print(b,a,amari)
            if amari == 1:
                B += 1

# print(A,B,D)
print(A+B+D)

Submission status: Wrong Answer

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 and (n//i)%i == 1:
            divisors.append(i)

    # divisors.sort()
    return divisors

n=int(input())
l = make_divisors(n-1)
ans = len(l)
l2 = make_divisors2(n)
ans += len(l2)
print(ans)

Submission status: Wrong Answer

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(n):
    ans=0
    for ds in make_divisors(n):
        k=n
        if ds==1:
            continue
        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: Wrong Answer

Solution code:
N=int(input())
import math
lists=[]
listT=[]
t=2
T=0
n=N-1
p=1
while t<=math.sqrt(N):
    if n%t==0:
        T=T+1
        n=n//t
        p=p*t
        lists.append(t)
        if n==1:
            listT.append(T)
            break
    else:
        t=t+1
        if T!=0:
            listT.append(T)
            T=0
if p==1:
    lists.append(1)
    lists.append(N)
    listT=[1]
elif n!=1:
    lists.append(n)
    listT.append(1)
def prod(lista):
    p=1
    for i in range(10000):
        try:
            p=p*(lista[i]+1)
        except IndexError:
            return (p-1)
A=prod(listT)+2
print (A)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
 
KMAX = math.floor(math.sqrt(N)) + 1
# KMAX = 1000
 
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)
print(len(Knn))
# print(sorted(Knn))

Submission status: Wrong Answer

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:
    if div_or_sub(n, divisor) == 1:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=1
s=set()
for i in range(1,int(n**0.5)+1):
  if n%(i+1)==0:
    k=n
    cnt=1
    c=0
    while k%(i+1)==0:
      k//=(i+1)
      cnt*=(i+1)
      if cnt not in s:
        s.add(cnt)
        c+=1
    for j in range(1,c+1):
      if k%((i+1)**j)==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: Wrong Answer

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:
    if div_or_sub(n, divisor) == 1:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=1
s=set()
for i in range(1,int(n**0.5)):
  if n%(i+1)==0:
    k=n
    cnt=1
    c=0
    while k%(i+1)==0:
      k//=(i+1)
      cnt*=(i+1)
      if cnt not in s:
        s.add(cnt)
        c+=1
    for j in range(1,c+1):
      if k%((i+1)**j)==1:
        ans+=1
d=dict()
k=n-1
for i in range(1,int((n-1)**0.5)):
  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: Wrong Answer

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))
n_divisors = calc_divisors(n)
for divisor in n_divisors:
    if div_or_sub(n, divisor) == 1:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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