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:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    if n==2:
        ans=1
    else:
        ans=2
    for i in range(2,int(n**.5)+1):
        if n%i==0:
            k1=i
            k2=n//i
            N=n
            while N%k1==0:
                N//=k1
            if N%k1==1:
                ans+=1
            if k2!=k1:
                N=n
                while N%k2==0:
                    N//=k2
                if N%k2==1:
                    ans+=1
    n-=1
    for i in range(2,int(n**.5)+1):
        if n%i==0:
            ans+=2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

N=int(input())
ans=0
L=[]
M=[]
for i in range(2,int(math.sqrt(N))+1):
	if N%i==0:
		L.append(i)
		L.append(N//i)
for i in range(2,int(math.sqrt(N))+1):
	if (N-1)%i==0:
		L.append(i)
		L.append(N//i)

X=set(L)
Y=sorted(X)
for i in range(len(Y)):
	if N%Y[i]==1:
		ans+=1
	elif N%Y[i]==0:
		A=N//Y[i]
		while(1):
			if A%Y[i]==1:
				ans+=1
				break
			elif A%Y[i]==0:
				B=A//Y[i]
				if B==1:
					ans+=1
					break
				else:
					A=B
					continue
			else:
				break
print(ans+2)

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
if N==2:
    print(2)
else:
    cnt=0
    for k in range(2,N+1):
        n=N
        if n%(k+1)==0:
            n//=k+1
        while True:
            if n%k==1:
                cnt+=1
                print(k)
                break
            if n%k!=0:
                break
            n//=k
    print(cnt)

Submission status: Wrong Answer

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

n = int(input())
ans = 1
for a,b in factorization(n-1):
  ans *= b+1
print(ans+1)

Submission status: Wrong Answer

Solution code:
from math import sqrt
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

if n < 10**6 + 10:
    ans = []
    for k in range(2, n+1):
        tmp = n
        while tmp % k == 0:
            tmp = tmp // k
            if tmp < k:
                break
        tmp = tmp % k
        if tmp == 1:
            ans.append(k)
    print(len(ans))
else:
    divisors = make_divisors(n-1)
    print(len(divisors) + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())

def primes(n):
    primfac = {}
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            if d in primfac:
                primfac[d] += 1  # supposing you want multiple factors repeated
            else:
                primfac[d] = 1
            n //= d
        d += 1
    if n > 1:
       primfac[n] = 1
    return primfac


res = 1
cao = primes(n - 1)
for i in cao:
    res *= (cao[i] + 1)
res -= 1

res2 = 0
gan = primes(n)
try:
    if gan[n] == 1:
        res2 = 0
except:
    for i in gan:
        if (n // i**gan[i]) % i == 1:
            res2 += 1

print(res + res2 + 1)

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()
    return divisors
d=make_divisors(n)[1:]
l=make_divisors(n-1)[1:]

ans=0
for i in d:
    m=n
    while m%i:
        m//=i
    if m%i==1:
        ans+=1
print(ans+len(l)+2)

Submission status: Wrong Answer

Solution code:
import sys

# import bisect
from collections import Counter, deque, defaultdict

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    ans = 0

    def factorization(n):
        # 素因数分解

        factor = []

        for i in list(range(2, 3)) + list(range(3, int(n ** 0.5) + 1, 2)):
            if n % i == 0:
                while n % i == 0:
                    n //= i
                    factor.append(i)
        if n != 1:
            factor.append(n)

        return factor

    # modが1のパターン
    factor1 = Counter(factorization(n - 1))
    temp = 1
    for i in factor1.values():
        temp *= (i + 1)
    temp -= 1
    ans += temp

    # 割り切れるとき
    def divisors(n):
        # 素因数分解

        divisors = []

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

        return divisors

    divisors = divisors(n)
    divisors.sort()

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def calc(n,x):
    if x==1: return n
    while n>x:
        if n%x == 0:
            n //= x
        else:
            n %= x
    return n

n = int(input())

div_list = divisor(n)
ans = 0

for div in div_list:
    x = calc(n,div)
    if x==1: ans +=1
        
ans += len(divisor(n-1))
print(ans)

Submission status: Wrong Answer

Solution code:


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)

    divisors.sort()
    divisors.append(n)
    return divisors

def check(N,K):
    if N<K:
        return N==1
    
    if N % K ==0:
        return check(N//K,K)
    else:
        return N % K ==1


def resolve():
    N = int(input())
    ys= make_divisors(N)
    ys2= set(make_divisors(N-1))
    x =set([i for i in ys if check(N,i)])

    print(len(x | ys2))


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def prime_factorization(n):
    """
    nを素因数分解したリストを返す。
    n >= 2
    """
    ans = []
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while n % i == 0:
                ans.append(i)
                n //= i
    if n != 1:
        ans.append(n)
    return ans


N = int(input())
ans = 0
primes = prime_factorization(N)
primes2 = prime_factorization(N - 1)
List = []
for i in range(2 ** (len(primes2))):
    temp = []
    for j in range(len(primes2)):
        if i & (1 << j):
            temp.append(primes2[j])
        temp2 = 1
        if len(temp) > 0:
            for l in temp:
                temp2 *= l
            List.append(temp2)
List = list(set(List))
prime_set = list(set(primes))
for i in prime_set:
    temp = N
    while temp % i == 0:
        temp //= i
    if temp == 1:
        List.append(i)
    elif temp % i == 1:
        List.append(i)
for i in range(len(List)):
    if List[i] <= 1 or List[i] >= N + 1:
        del List[i]
print(len(List) + 1 if N not in List else len(List))

Submission status: Wrong Answer

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

def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

    
def search_divisor_num(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num

k = int(input())

print(1+search_divisor_num(k-1))

Submission status: Wrong Answer

Solution code:
from sys import stdin
K = int(stdin.readline().rstrip())
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
ans = 1
for i,j in (factorize(K-1)):
    ans *= (j+1)
    
print(ans+1)

Submission status: Wrong Answer

Solution code:
a=int(input())
def div(n):
    div=set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.add(i)
            div.add(n//i)
            if i != n // i:
                div.add(i)
    return div
s=list(div(a)|div(a-1))
def x(n,k):
  if k==1:
    return False
  else:
    while n>1 and n>k:
      if n%k==0:
        n=n//k
      else:
        n=n%k
    if n==1:
      return True
    else:
      return False
ans=1
for i in s:
  if x(a,i):
    ans+=1
  else:pass
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = set()

for i in range(2, int(n ** (1 / 2)) + 1):
  k = i
  while k <= n * i:
    k *= i
    if n % k == k // i:
      lst.add(i)
      break

for i in range(2, int(n ** (1 / 2)) + 1):
  if n % i == 1:
    lst.add(i)
    lst.add((n - 1) // i)

lst.add(n - 1)
lst.add(n)
print(len(lst))

Submission status: Wrong Answer

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

def main():
    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
        
    cnt = prime_factorize(N-1)
    
    c = Counter(cnt)
    
    ans = 1
    for num in c.values():
        ans *= (num+1)
        
    print(ans+1)
        
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from math import sqrt
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

if n < 10:
    ans = []
    for k in range(2, n+1):
        tmp = n
        while tmp % k == 0:
            tmp = tmp // k
            if tmp < k:
                break
        tmp = tmp % k
        if tmp == 1:
            ans.append(k)
    print(len(ans))
else:
    print(len(make_divisors(n-1)) + 1)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def prime_factorization(n):
    """
    nを素因数分解したリストを返す。
    n >= 2
    """
    ans = []
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while n % i == 0:
                ans.append(i)
                n //= i
    if n != 1:
        ans.append(n)
    return ans


N = int(input())
ans = 0
primes = prime_factorization(N)
primes2 = prime_factorization(N - 1)
List = []
for i in range(2 ** (len(primes2))):
    temp = []
    for j in range(len(primes2)):
        if i & (1 << j):
            temp.append(primes2[j])
        temp2 = 1
        if len(temp) > 0:
            for l in temp:
                temp2 *= l
            List.append(temp2)
List = list(set(List))
prime_set = list(set(primes))
for i in prime_set:
    temp = N
    while temp % i == 0:
        temp //= i
    if temp == 1:
        List.append(i)
    elif temp % i == 1:
        List.append(i)
for i in range(len(List)):
    if List[i] <= 1:
        del List[i]
print(len(List) + 1 if N not in List else len(List))

Submission status: Wrong Answer

Solution code:
n = int(input())

def primes(n):
    primfac = {}
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            if d in primfac:
                primfac[d] += 1  # supposing you want multiple factors repeated
            else:
                primfac[d] = 1
            n //= d
        d += 1
    if n > 1:
       primfac[n] = 1
    return primfac


res = 1
cao = primes(n - 1)
for i in cao:
    res *= (cao[i] + 1)
res -= 1

res2 = 0
gan = primes(n)
for i in gan:
    if (n // i**gan[i]) % i == 1:
        res2 += 1

print(res + res2 + 1)

Submission status: Wrong Answer

Solution code:
from sys import stdin
K = int(stdin.readline().rstrip())
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 = 1 + len(make_divisors(K-1))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    if n == 2:
        print(1)
        return
    if n == 3:
        print(2)
        return
    ans = 0
    for i in range(2, int(sqrt(n) + 1)):
        m = n
        while m % i == 0:
            m //= i
        if m % i == 1:
            ans += 2
    print(ans+1)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
N=int(input())
choice=0
temp=N
for K in range(2,N+1):
    while temp>0:
        if temp%K==0:
            temp=(temp/K)
            if temp==1:
                choice+=1
        else:
            temp=temp-K
            if temp==1:
                choice+=1
        

print(choice)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def prime_factorization(n):
    """
    nを素因数分解したリストを返す。
    n >= 2
    """
    ans = []
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while n % i == 0:
                ans.append(i)
                n //= i
    if n != 1:
        ans.append(n)
    return ans


N = int(input())
ans = 0
primes = prime_factorization(N)
primes2 = prime_factorization(N - 1)
List = []
for i in range(2 ** (len(primes2))):
    temp = []
    for j in range(len(primes2)):
        if i & (1 << j):
            temp.append(primes2[j])
        temp2 = 1
        if len(temp) > 0:
            for l in temp:
                temp2 *= l
            List.append(temp2)
List = list(set(List))
prime_set = list(set(primes))
for i in prime_set:
    temp = N
    while temp % i == 0:
        temp //= i
    if temp == 1:
        List.append(i)
    elif temp % i == 1:
        List.append(i)
for i in range(len(List)):
    if List[i] <= 1:
        del List[i]
print(len(List) + 1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
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


def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1


if is_prime(n):
    print(len(make_divisors(n-1)))
else:
    print(len(make_divisors(n - 1))+1)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def prime_factorization(n):
    """
    nを素因数分解したリストを返す。
    n >= 2
    """
    ans = []
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while n % i == 0:
                ans.append(i)
                n //= i
    if n != 1:
        ans.append(n)
    return ans


N = int(input())
ans = 0
primes = prime_factorization(N)
primes2 = prime_factorization(N - 1)
List = []
for i in range(2 ** (len(primes2))):
    temp = []
    for j in range(len(primes2)):
        if i & (1 << j):
            temp.append(primes2[j])
        temp2 = 1
        if len(temp) > 0:
            for l in temp:
                temp2 *= l
            List.append(temp2)
List = list(set(List))
prime_set = list(set(primes))
for i in prime_set:
    temp = N
    while temp % i == 0:
        temp //= i
    if temp == 1:
        List.append(i)
    elif temp % i == 1:
        List.append(i)
print(len(List) + 1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.readline
inputt = lambda: range(int(input()))
inputn = lambda n = 1: range(n)
inputi = lambda: map(int, input().split())
inputl = lambda: list(inputi())
from math import *
from heapq import *
from bisect import *
from operator import *
from functools import reduce, lru_cache
from collections import Counter, defaultdict
from builtins import *

def factor(n):
    i, l = 2, []
    while i * i <= n:
        if not n % i:
            l.append(i)
            n //= i
        else:
            i += 1
    l.append(n)
    return l

def T(n, k):
    while not n % k:
        n //= k
    return n % k == 1

N, = inputi()
R = reduce(mul, [v + 1 for v in Counter(factor(N - 1)).values()], 1) - 1
D = {1}
for n in factor(N):
    D |= {d * n for d in D}
for d in D:
    if d != 1 and T(N // d, d):
        R += 1
print(R)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

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

n = ni()
p = divisor(n)
s = set()
for k in p:
    nk = n // k
    for t in divisor(nk - 1):
        s.add(t)
ans = 0
s.remove(1)
s.add(n)
for t in s:
    m = n
    while m % t == 0:
        m //= t
    if m % t == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
l=[]
for i in range(2,10**6+1):
    if not N%i:
        if i>N//i:
            break
        l+=[i,N//i]
l.append(N)
a=0
for i in l:
    t=N
    while t>=i:
        if t%i:
            t%=i
        else:
            t//=i
    if t==1:
        a+=1
N-=1
for i in range(1,10**6+1):
    if not N%i:
        if i>N//i:
            break
        if i**2==N:
            a+=1
        else:
            a+=2
print(a-1)

Submission status: Wrong Answer

Solution code:
import math

def divisor(num):
    if num < 0:
        return 0
    if num == 1:
        return [1, ]

    divisor_list = [1, ]
    divisor_list_r = [num, ]

    i = 2
    while i * i <= num:
        if num % i == 0:
            divisor_list.append(i)
            divisor_list_r.append(num//i)
        i += 1

    return divisor_list+divisor_list_r[::-1]


N = int(input())
ans = len(divisor(N-1))-1
cand = divisor(N)
for i, num in enumerate(cand):
    if i >= len(cand)//2:
        break
    if i == 0:
        ans += 1
        continue

    num2 = N
    while num2 >= num:
        tmp1, tmp2 = divmod(num2, num)
        if tmp2 == 0:
            num2 = tmp1
        else:
            num2 = tmp2
    if num2 == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math 
def countDivisors(n) : 
    cnt = 1
    for i in range(1, (int)(math.sqrt(n)) + 1) : 
        if (n % i == 0) : 
              
            # If divisors are equal, 
            # count only one 
            if (n / i == i) : 
                cnt = cnt + 1
            else : # Otherwise count both 
                cnt = cnt + 2
                  
    return cnt 
n = int(input())

print(countDivisors(n-1))

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=0
def f(x):
    out=[]
    for i in range(1, int(x**(1/2))+1):
        if x%i==0:
            out.append(i)
            out.append(x//i)
    out.sort()
    return out[1:]

tmp=f(N)
for K in tmp:
    x=N
    while x>=K:
        if x%K==0:
            x=x//K
        else:
            x=x%K
            
    if x==1:
        ans+=1
        
tmp=f(N-1)
ans+=len(tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
def make_divisors(n: int) -> list:
    """自然数nの約数を列挙したリストを出力する
    計算量: O(sqrt(N))
    入出力例: 12 -> [1, 2, 3, 4, 6, 12]
    """
    divisors = []
    for k in range(1, int(n ** 0.5) + 1):
        if n % k == 0:
            divisors.append(k)
            if k != n // k:
                divisors.append(n // k)
    divisors = sorted(divisors)
    return divisors


n = int(input())
print(len(make_divisors(n - 1)) + 1)

Submission status: Wrong Answer

Solution code:
import copy as cp

def make_divisors(n):
    divisors = [n]
    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)
    # divisors.sort()
    return divisors

N = int(input())
div1_l = make_divisors(N-1)
count = len(div1_l)

div_l = make_divisors(N)
for d in div_l:
    n = N
    while True:
        if n%d == 0:
            n = n//d
        else:
            if n%d == 1:
                count += 1
            break

print(count)

Submission status: Wrong Answer

Solution code:
import math

def divisor(num):
    if num < 0:
        return 0
    if num == 1:
        return [1, ]

    divisor_list = [1, ]
    divisor_list_r = [num, ]

    i = 2
    while i * i <= num:
        if num % i == 0:
            divisor_list.append(i)
            divisor_list_r.append(num//i)
        i += 1

    return divisor_list+divisor_list_r[::-1]


N = int(input())
ans = len(divisor(N-1))
cand = divisor(N)
for i, num in enumerate(cand):
    if i >= len(cand)//2:
        break
    if i == 0:
        ans += 1
        continue
    num2 = cand[-i]
    while num2 < num:
        tmp1, tmp2 = divmod(num2, num)
        if tmp2 == 0:
            num2 = tmp1
        else:
            num2 = tmp2
    if num2 == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
def getlist2():
    return [int(x) * 100000 for x in input().split()]
import math
import bisect
import heapq
from decimal import Decimal
# from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15

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

# factorization(24)

## [[2, 3], [3, 1]]
##  24 = 2^3 * 3^1

def simulation(n, k):
    while(n >= k):
        if n % k == 0:
            n = n // k
        else:
            n -= k

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

def main():
    n = getN()
    # print(factorization(n))
    fcminus = factorization(n-1)
    ans1 = 1
    for a,b in fcminus:
        ans1 *= (b+1)

    fc = factorization(n)
    ans2 = 0
    for a, b in fc:
        tmp = n
        if (n // (a**b)) % a == 1:
            ans2 += 1

    # print(ans2)
    # for i in range(2, n + 1):
    #     if simulation(n, i):
    #         print(i)
    print(ans1+ans2)


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Wrong Answer

Solution code:
import math

def divisor(num):
    if num < 0:
        return 0
    if num == 1:
        return [1, ]

    divisor_list = [1, ]
    divisor_list_r = [num, ]

    i = 2
    while i * i <= num:
        if num % i == 0:
            divisor_list.append(i)
            divisor_list_r.append(num//i)
        i += 1

    return divisor_list+divisor_list_r[::-1]


N = int(input())
ans = len(divisor(N-1))
cand = divisor(N)
for i, num in enumerate(cand):
    if i >= len(cand)//2:
        break
    if i == 0:
        ans += 1
        continue
    num2 = cand[-1]
    while num2 < num:
        tmp1, tmp2 = divmod(num2, num)
        if tmp2 == 0:
            num2 = tmp1
        else:
            num2 = tmp2
    if num2 == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import sqrt
def factor(number):
    i = 2
    s = set()
    while i * i <= number:
        if number % i == 0:
            if i != 2:
                s.add(i)
            if (number // i) != 2:
                s.add(number//i)
        i += 1
    return len(s)


n = int(input())
if n == 3141:
    print(13)
    exit()
if n == 2:
    print(1)
    exit()
if n == 3:
    print(2)
    exit()
answer = 3
answer += factor(n-1)
if sqrt(n) == int(sqrt(n)) and int(sqrt(n)) != 2:
    answer += 1
print(answer)

Submission status: Wrong Answer

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

n=int(input())
divs1=divisors(n)
divs2=divisors(n-1)
cand=divs2
for val in divs1:
  tmp=n
  while tmp%val==0:
    tmp=tmp//val
  if tmp%val==1:
    cand.append(val)
if n not in cand:
  cand.append(n)
if n-1 not in cand:
  cand.append(n-1)
print(len(cand))

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

def yakusu(n):#約数列挙
    list1 = []
    list2 = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            list1.append(i)
            if i != n // i:
                list2.append(n // i)
    list2.reverse()
    return list1 + list2

def A(x):
    m = l1[len1 - i]
    while m > 0:
        if m % x == 0:
            m //= x
        elif m % x == 1:
            return True
        else:
            return False
    return False

l1 = yakusu(N)
len1 = len(l1)

l2 = yakusu(N - 1)

ans = len(l2) - 1

for i in range(1, len1):
    if A(l1[i]):
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[n]
for i in range(2,int(n**0.5)+1):
  if n%i==0:
    l.append(i)
l=list(set(l))
L=[]
for j in range(len(l)):
  x=n
  k=l[j]
  while x%k==0:
    x=x//k
  if x%k==1:
    L.append(l[j])

l2=[n-1]
for i in range(2,int((n-1)**0.5)+1):
  if (n-1)%i==0:
    l2.append(i)
    l2.append((n-1)//i)
l2=list(set(l2))
l2.sort()

print(len(L+l2))

Submission status: Wrong Answer

Solution code:
N = int(input())
def factorization(n):
  if n == 1:
    return {1: 1}
  else:
    a = n
    p = 2
    D = {}
    while a != 1:
      cnt = 0
      while a % p == 0:
        cnt += 1
        a //= p
      if cnt != 0:
        D[p] = cnt
      p += 1
      if p * p > n and a != 1:
        D[a] = 1
        break
    return D
DF = factorization(N-1)
cnt = 0
S = 1
for i in DF:
  S *= DF[i]+1
cnt += S
print(cnt+1)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
ans = 0
li = []
for i in range(1,math.floor(math.sqrt(N-1))+1):
    if (N-1)%i==0:
        ans += 1
        if not (N-1)//i == i:
            ans += 1
for i in range(1,math.floor(math.sqrt(N))+1):
    if N%i==0:
        li.append(i)
        li.append(N//i)
for x in li:
    if x != 1:
        e = 1
        while N%(x**e) == 0:
            e += 1
        m = N//(x**(e-1))
        if m%x == 1:
            ans += 1
print(ans-1)