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())

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-1の約数(1は除く)　Nそのもの
#2
d=make_divisors(N-1)
if not 2 in d:
  d.append(2)
#print(d)
d2=make_divisors(N)
#print(len(d))
for i in d2:
  if i!=N and i!=1 and i not in d:
    now=N
    while now%i==0:
      now/=i
    if now%i==1:
      d.append(i)
print(len(d))

Submission status: Wrong Answer

Solution code:
N = int(input())

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


div_N = divisor(N)
div_N_1 = divisor(N-1)

ans = 0

for k in div_N[1:]:
    n = N
    while n % k == 0:
        n //= k
    if n == 1:
        ans += 1

ans += len(div_N_1)

print(ans)

Submission status: Wrong Answer

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

for i in range(2,int((N-1)**0.5)+1):
    if (N-1)%i == 0:
        count += 1
        if (N-1)//i != i:
            count += 1

for j in range(2,int(N**0.5)+1):
    if N%j == 0:
        n = N
        while n%j == 0:
            n = n//j
        if n%j == 1:
            count += 1
        if N//j != j:
            n = N
            while n%(N//j) == 0:
                n = n//(N//j)
            if n%(N//j) == 1:
                count += 1
print(count+2)

Submission status: Wrong Answer

Solution code:
N = int(input())

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


div_N = divisor(N)
div_N_1 = divisor(N-1)

ans = 0

for k in div_N[1:]:
    n = N
    while n % k == 0:
        n //= k
    if n == 1:
        ans += 1

ans += len(div_N_1)

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

    if n//i != i:
      tmp = n;i = n//i
      while tmp % i==0:
        tmp //= i
      if (tmp-1) % i == 0:ans += 1

for i in range(2,int((n-1)**.5 )+ 1):
  if (n-1) % i == 0:
    if (n-1) // i == i: ans += 1
    else: ans += 2
# print(ans)
print(ans+2)

Submission status: Wrong Answer

Solution code:
import sys
def solve():
    input = sys.stdin.readline
    N = int(input())
    if N == 2: print(1)
    else:
        K = {N, N-1}
        for i in range(2, N + 1):
            if i ** 2 > N: break
            if N % i == 0:
                k = N
                while k % i == 0:
                    k //= i
                if k % i == 1: K |= {k}
            
            if (N - 1) % i == 0:
                K |= {i}
                if i ** 2 != N - 1: K |= {(N - 1) // i}
        print(len(K))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
def solve():
    input = sys.stdin.readline
    N = int(input())
    if N == 2: print(1)
    else:
        K = {N, N-1}
        for i in range(2, N + 1):
            if i ** 2 > N: break
            if N % i == 0:
                k = N
                while k % i == 0:
                    k //= i
                if k % i == 1: K |= {k}
                revi = N // i
                k = N
                while k % revi == 0:
                    k //= revi
                if k % revi == 1: K |= {revi}
            
            if (N - 1) % i == 0:
                K |= {i}
                if (N - 1) // i > 1 and i ** 2 != N - 1: K |= {(N - 1) // i}
        print(len(K))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
def solve():
    input = sys.stdin.readline
    N = int(input())
    if N == 2: print(1)
    else:
        K = {N, N-1}
        for i in range(2, N + 1):
            if i ** 2 > N: break
            if N % i == 0:
                k = N
                while k % i == 0:
                    k //= i
                if k % i == 1: K |= {k}
                revi = N // i
                k = N
                while k % revi == 0:
                    k //= revi
                if k % revi == 1: K |= {revi}
            
            if (N - 1) % i == 0:
                K |= {i}
                if (N - 1) // i > 1: K |= {(N - 1) // i}
        print(len(K))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
def solve():
    input = sys.stdin.readline
    N = int(input())
    if N == 2: print(1)
    else:
        K = {N, N-1}
        for i in range(2, N + 1):
            if i ** 2 > N: break
            if N % i == 0:
                k = N
                while k % i == 0:
                    k //= i
                if k % i == 1: K |= {k}
            
            if (N - 1) % i == 0:
                K |= {i, (N - 1) // i}
        K -= {1}
        print(len(K))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
def solve():
    input = sys.stdin.readline
    N = int(input())
    K = {N, N-1}
    for i in range(2, N + 1):
        if i ** 2 > N: break
        if N % i == 0:
            k = N
            while k % i == 0:
                k //= i
            if k % i == 1: K |= {k}
            
        if (N - 1) % i == 0:
            K |= {i, (N - 1) // i}
    print(len(K))
    return 0

if __name__ == "__main__":
    solve()

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

ans = 0
K = make_divisors(N-1)
ans = len(K)-1

K = make_divisors(N)
for k in K:
    if k == 1:
        next
    else:
        if (N//k)%k == 1:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
cnt = 0
for k in range(2,n):
  m = n
  while(m>0):
    if (m%k == 0):
      m = m/k
    else:
      m = m-k
    if (m==1):
      cnt += 1
      break
print(cnt)

Submission status: Wrong Answer

Solution code:
import math


def list_divisor(n):
    divisor1 = {1}
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisor1.add(i)

    divisor2 = {n}
    for i in divisor1:
        divisor2.add(n // i)

    return divisor1 & divisor2


def main():
    n = int(input().rstrip())

    sub_only = len(list_divisor(n - 1)) - 1

    div_included = 0
    for d in list_divisor(n):
        n1 = n // d
        while n1 % d == 0:
            n1 = n1 // d

        if d in list_divisor(n1 - 1):
            div_included += 1
    
    print(sub_only + div_included)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

def enumerate_divisors(N):
  for divisor in range(1, int(math.sqrt(N)) + 1):
    if N%divisor == 0:
      yield (divisor, N/divisor)

def calculate_reminder(N, d):
  while True:
    reminder = N%d
    if reminder == 0:
      N /= d
    else:
      return reminder

counter = 0
if N == 2:
  counter = 1

else:
  for _ in enumerate_divisors(N-1):
    counter += 2
  counter -= 1

  for div, N_div in enumerate_divisors(N):
    if (div != 1) and (calculate_reminder(N, div) == 1):
      counter += 1
    if calculate_reminder(N, N_div) == 1:
      counter += 1

print(counter)

Submission status: Wrong Answer

Solution code:
#  not resolved
n =int(input())
cnt = 0

num = n - 1
sq = int(num**.5)
for k in range(2, sq+1):
	if k == sq and num % k == 0:
		cnt += 1
	elif num % k == 0:
		cnt += 2
cnt += 1

sq2 = int(n ** .5)
for k in range(2, sq2+1):
	x = n
	if x % k == 0:
		while x % k == 0:
			x = x//k
		if x % k == 1:
			cnt += 1

cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
#  not resolved
n =int(input())
cnt = 1

num = n - 1
sq = int(num**.5)
for k in range(2, sq+1):
	if k == sq and num % k == 0:
		cnt += 1
	elif num % k == 0:
		cnt += 2
cnt += 1

sq2 = int(n ** .5)
for k in range(2, sq2+1):
	x = n
	if x % k == 0:
		while x % k == 0:
			x = x/k
		if x % k == 1:
			cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
#  not resolved
n =int(input())
cnt = 0

num = n - 1
sq = int(num**.5)
for k in range(2, sq+1):
	if k == sq:
		cnt += 1
	elif num % k == 0:
		cnt += 2
cnt += 1

sq2 = int(n ** .5)
for k in range(2, sq2+1):
	x = n
	if x % k == 0:
		while x % k == 0:
			x = x/k
		if x % k == 1:
			cnt += 1

print(cnt)

Submission status: Wrong Answer

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

# 1以外のNの約数
divisors = []
for i in range(1, int(math.sqrt(n)) + 1):
    if n % i == 0:
        divisors.append(i)
        divisors.append(n // i)
divisors.sort()

candidates = set()
for k in divisors[1:]:
    tmp = n
    while True:
        if tmp % k != 0:
            break
        tmp = tmp // k
    if (tmp - 1) % k == 0:
        candidates.add(k)

# N-1の約数
divisors = []
for i in range(1, int(math.sqrt(n-1)) + 1):
    if (n-1) % i == 0:
        divisors.append(i)
        divisors.append((n-1) // i)

for k in divisors[1:]:
    candidates.add(k)

print(len(candidates))

Submission status: Wrong Answer

Solution code:
import math

n = int (input())
sqr = int (math.sqrt(n))
ans = 1 # n itself

def check (x) :
    tmp = n
    while (tmp % x == 0) :
        tmp /= x
    return True if tmp % x == 1 else False

for i in range (2, sqr + 1) :
    if (n % i == 0) :
        if (check (i)) :
            ans += 1
        if (i != n / i and check (n / i)) :
            ans += 1
    
m = n - 1
if (m > sqr) :
    ans += 1 # m
    for i in range (2, sqr + 1) :
        if (m % i == 0) :
            ans += 1 + 1 if i != m / i else 0

print (ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

print(gcd(120, 24))

Submission status: Wrong Answer

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

n = int(input())
if n==2:
    print(1)
else:
    k = decomposition(n-1)
    if 2 not in k:
        print(len(k)+1)
    else:
        print(len(k))

Submission status: Wrong Answer

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

n = int(input())
if n==2:
    print(1)
else:
    k = decomposition(n-1)
    print(len(k)+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)

print(len(make_divisors(N-1))+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
sqrt_N = int(N ** 0.5)

dividers_for_N = [N]
ans_list = [N - 1]

for i in range(2, sqrt_N + 1):
    if (N - 1) % i == 0:
        ans_list.append(i)
        if i != (N - 1) // i:
            ans_list.append((N - 1) // i)

    if N % i == 0:
        dividers_for_N.append(i)
        if i != N // i:
            dividers_for_N.append(N // i)

for i in dividers_for_N:
    num = N
    while num % i == 0:
        num //= i
    if num % i == 1:
        ans_list.append(i)

ans = len(ans_list)

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
def make_divisors(n):
    mod0 = set()
    mod1 = set()
    for i in range(2, int(n**0.5)+1):
        if n%i==0:
            mod0.add(i)
            mod0.add(n/i)
        if (n-1)%i==0:
            mod1.add(i)
            mod1.add((n-1)/i)
    print(mod0)
    print(mod1)
    return mod0,mod1

N=list(map(int,(stdin.readline().strip().split())))
num=N[0]
K=0
mod0,mod1=(make_divisors(num))
# mod0.remove(1)
# mod1.remove(1)
for i in mod0:
    num = N[0]
    while(num % i == 0):
        num/=i

    if num%i==1:
        K+=1
K+=len(mod1)+2
print(K)

Submission status: Wrong Answer

Solution code:
from sys import stdin
def make_divisors(n):
    mod0 = set()
    mod1 = set()
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            mod0.add(i)
            # mod0.add(n//i)
        if (n-1)%i==0:
            mod1.add(i)
            # mod1.add((n-1)//i)
    return mod0,mod1

N=list(map(int,(stdin.readline().strip().split())))
num=N[0]
K=0
mod0,mod1=(make_divisors(num))
mod0.remove(1)
mod1.remove(1)
for i in mod0:
    num = N[0]
    while(num % i == 0):
        num//=i

    if num%i==1:
        K+=1
K+=len(mod1)
print(K)

Submission status: Wrong Answer

Solution code:
from sys import stdin
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()
    return divisors
N=list(map(int,(stdin.readline().strip().split())))
num=N[0]
K=len(make_divisors(num-1))+2
num_list=(make_divisors(num))
for i in num_list:
    num = N[0]
    while(num % i == 0):
        num//=i

    if num%i==1:
        K+=1
print(K)

Submission status: Wrong Answer

Solution code:
from sys import stdin
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()
    return divisors
N=list(map(int,(stdin.readline().strip().split())))
num=N[0]
K=len(make_divisors(num-1))+1
num_list=(make_divisors(num))
num_list.append(num)
for i in num_list:
    num = N[0]
    while(True):
        if num % i != 0 or num== 1: break
        num//=i

    if num%i==1 or num==1:
        K+=1
print(K)

Submission status: Wrong Answer

Solution code:
from sys import stdin
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()
    return divisors
N=list(map(int,(stdin.readline().strip().split())))
num=N[0]
K=len(make_divisors(num-1))+1
num_list=(make_divisors(num))
num_list.append(num)
for i in num_list:
    num = N[0]
    while(True):
        if num % i != 0 or num== 1: break
        num/=i

    if num%i==1 or num==1:
        K+=1
print(K)

Submission status: Wrong Answer

Solution code:
from sys import stdin
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()
    return divisors
N=list(map(int,(stdin.readline().strip().split())))
num=N[0]
K=len(make_divisors(num-1))+1
num_list=(make_divisors(num))
num_list.append(num)
for i in num_list:
    num = N[0]
    while(True):
        if num % i != 0 or num / i == 1: break
        num=num/i

    if num%i==1 or num/i==1:
        K+=1
print(K)

Submission status: Wrong Answer

Solution code:
from sys import stdin
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()
    return divisors
N=list(map(int,(stdin.readline().strip().split())))
num=N[0]
K=len(make_divisors(num-1))+1
num_list=(make_divisors(num))
num_list.append(num)
for i in num_list:
    num = N[0]
    while(True):
        num=num/i
        if num%i!=0 or num/i==1:break
    if num%i==1 or num/i==1:
        K+=1
print(K)

Submission status: Wrong Answer

Solution code:
from sys import stdin
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()
    return divisors
N=list(map(int,(stdin.readline().strip().split())))
num=N[0]
K=len(make_divisors(num-1))+2
num_list=(make_divisors(num))
for i in num_list:
    num = N[0]
    while(True):
        num=num/i
        if num%i!=0:break
    if num%i==1:
        K+=1
print(K)

Submission status: Wrong Answer

Solution code:
import math


def divisors(n):
    divs = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divs.extend([i, n // i])
    divs.extend([n])
    return set(divs)


n = int(input())

ans = divisors(n - 1)

for k in divisors(n):
    tmp = n
    while tmp % k == 0:
        tmp //= k

    if tmp % k == 1:
        ans.add(k)

print(len(ans))

Submission status: Wrong Answer

Solution code:
import math


def divisors(n):
    divs = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divs.extend([i, n // i])
    divs.extend([n])
    return set(divs)


n = int(input())

d2 = divisors(n - 1)
ans = len(d2)

for k in divisors(n):
    tmp = n
    while tmp % k == 0:
        tmp //= k

    if tmp % k == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math


def divisors(n):
    divs = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divs.extend([i, n // i])
    divs.extend([n])
    return set(divs)


n = int(input())

d1 = divisors(n)
d2 = divisors(n - 1)

for k in d1:
    tmp = n
    while tmp % k == 0:
        tmp //= k

    if tmp % k == 1:
        d2.add(k)

print(len(d2))

Submission status: Wrong Answer

Solution code:
import math


def divisors(n):
    divs = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divs.extend([i, n // i])
    divs.extend([n])
    return set(divs)


n = int(input())

d1 = divisors(n)
d2 = divisors(n - 1)

for k in d1:

    tmp = n
    while tmp >= k:
        if tmp % k == 0:
            tmp //= k
        else:
            tmp -= k

    if tmp == 1:
        d2.add(k)

print(len(d2))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N=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

#整数N-1の約数は全て答えにカウントして良い
ans=set(make_divisors(N-1))

K=make_divisors(N)  #Nの約数の集合
#整数Nの約数について条件にマッチングするかを1つ1つ調べる
for k in K:
    if k==1: continue
    n=N
    while n%k==0:
        n/=k
    else:
        #print "n,k :: ",n,k
        if n/k==1 or n%k==1:
        #if n%k==1: AC
        #if n==1 or n%k==1: AC
            ans.add(k)
print len(ans)-1

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N=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=set()

#整数N-1の約数は全て答えにカウントして良い
ans=set(make_divisors(N-1))

K=make_divisors(N)  #Nの約数の集合
#整数Nの約数について条件にマッチングするかを1つ1つ調べる
for k in K:
    if k==1: continue
    n=N
    while n%k==0:
        n/=k
    else:
        if n/k==1 or n%k==1:
            ans.add(k)
print len(ans)-1

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N=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=set()

#整数N-1の約数は全て答えにカウントして良い
ans=set(make_divisors(N-1))

K=make_divisors(N)  #Nの約数の集合
#整数Nの約数について条件にマッチングするかを1つ1つ調べる
for k in K:
    if k==1: continue
    n=N
    while n%k==0:
        n=n/k
    else:
        if n/k==1 or n%k==1:
            ans.add(k)
print len(ans)-1

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N=input()

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

ans=0

#整数N-1の約数は全て答えにカウントして良い
ans+=len(make_divisors(N-1))-1  #整数Kの中から1は除外するので-1

K=make_divisors(N)  #Nの約数の集合
#整数Nの約数について条件にマッチングするかを1つ1つ調べる
for k in K:
    if k==1: continue
    n=N
    while n%k==0:
        n=n/k
    else:
        #print "k,n ::",k,n
        if n/k==1 or n%k==1:
            ans+=1
print ans

Submission status: Wrong Answer

Solution code:
from collections import Counter
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 dict(Counter(a))
#n%k!=0
cnt=1
lst2=list(prime_factorize(n-1).values()) 
for k in lst2:
	cnt*=k+1
#n%k==0
lst1=list(prime_factorize(n).keys())
for k in lst1:
	t=n
	while t%k==0:
		t//=k
	t%=k
	if  t==1:
		cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
import math
def listup(num) :
    r,l = [],[]
    mx = int(math.sqrt(n))
    for i in range(1,mx+1) :
        if num % i == 0 :
            l.append(i)
            r.insert(0,int(num/i))
    l.extend(r)
    return l

n = int(input())

ans = listup(n-1)
ls = listup(n)

while(len(ls) > 0) :
    tmp = n
    x = ls.pop()
    while tmp % x == 0 and tmp / x > 1  and x > 1:
        tmp = tmp / x
    if tmp / x == 1 :
        ans.append(x)

print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
 
m = 0
for i in range (2 , N + 1):
    if N % i == 1:
        m = m + 1
    elif N % i == 0:
        while N % i == 0:
            N //= i
        if N % i == 1:
            m = m + 1
 
print ( m )

Submission status: Wrong Answer

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

# N-1の約数を数える
N = int(input())
factor = collections.Counter(prime_factorize(N-1))
K = 1
for i in list(factor.values()):
    K *= i+1
K -=1
print(K)
for f in range(2, int(N**0.5)+1):
    n = N
    if n%f != 0:
        continue
    while n%f ==0:
        n//=f
    if n%f ==1 or n==1:
        print(f)
        K+=1
#最後は自分自身を加える。
K +=1
print(K)

Submission status: Wrong Answer

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

# N-1の約数を数える
N = int(input())
factor = collections.Counter(prime_factorize(N-1))
K = 1
for i in factor.values():
    K *= i+1
K -=1

for f in range(2, int(N**0.5)+1):
    while N%f ==0:
        print(f)
        N//=f
    if N%f ==1 or N==1:
        K+=1
#最後は自分自身を加える。
K +=1
print(K)

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==2:
    count=1
else:
    count=2
for i in range(2,int(n**0.5)+1):
    if n%i==0:
        k=n//i
        if k==i:
          count+=1
        while k>i:
            if k%i==0:
                k=k//i
            else:
                if k%i==1:
                    count+=1
                break
    elif (n-1)%i==0:
        count+=1
        if i!=(n-1)//i:
            count+=1
print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
count=2
for i in range(2,int(n**0.5)+1):
    if n%i==0:
        k=n//i
        if k==i:
          count+=1
        while k>i:
            if k%i==0:
                k=k//i
            else:
                if k%i==1:
                    count+=1
                break
    elif (n-1)%i==0:
        count+=1
        if i!=(n-1)//i:
            count+=1
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

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

for i in range(2, int(n ** 0.5) + 1):
    if n % i == 0:
        k = i
        temp = n
        while temp % k == 0:
            temp //= k
        if temp % k == 1:
            ans += 1
        if i * i != n-1:
            k = n // i
            temp = n
            while temp % k == 0:
                temp //= k
            if temp % k == 1:
                ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
N = int(input())
def solve(num):
    d = math.floor(num**(1/2))
    for i in range(1,d+1):
        if num % i == 0:
            yield [i,num//i]

if N == 2:
    print(0)
    sys.exit()

cnt = 0
for a,b in solve(N-1):
    if a == b:
        cnt += 1
    else:
        cnt += 2

cnt -= 1

for s in solve(N):
    for a in s:
        if a == 1:
            continue

        tmp = N
        while True:
            tmp,m = divmod(tmp, a)
            if m == 0:
                continue
            elif m == 1:
                cnt += 1
            break

print(cnt)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
def solve(num):
    d = math.floor(num**(1/2))
    for i in range(1,d+1):
        if num % i == 0:
            yield [i,num//i]

cnt = 0
for a,b in solve(N-1):
    cnt += 2

cnt -= 1

for s in solve(N):
    for a in s:
        if a == 1:
            continue

        tmp = N
        while True:
            tmp,m = divmod(tmp, a)
            if m == 0:
                continue
            elif m == 1:
                cnt += 1
            break

print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
def sq(n,k) :
    if n == 1:
        return 1
    elif n - k < 0 :
        return 0
    else :
        if n % k == 0 :
            return sq(int(n/k),k)
        else:
            return sq(n%k,k)
cnt = 2
mx = int(n/2) + 1
for i in range(2,mx) :
    if sq(n,i) == 1:
        cnt +=1
        mx = int(n/i)+1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

if n == 3:
    print(2)
    exit()

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)
if n%2 == 0:
    print(len(d)+1)
elif n%3 == 0:
    print(len(d)+1)
else:
    print(len(d))

Submission status: Wrong Answer

Solution code:


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

    def prime_factorize(n):
        res = []
        while n % 2 == 0:
            res.append(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                res.append(f)
                n //= f
            else:
                f += 2
        if n != 1:
            res.append(n)
        return res

    def isqrt(n):
        x = n
        y = (x + 1) // 2
        while y < x:
            x = y
            y = (x + n // x) // 2
        return x

    # N = K^a * (bK + 1)
    # if a == 0
    ans = 1 # i == N-1
    for i in range(2, isqrt(N-1)+1):
        if (N-1) % i == 0:
            ans += 1
            if i != (N-1) // i:
                ans += 1
    
    # if a >= 1:
    divs = [N]
    for i in range(2, isqrt(N)+1):
        if N % i == 0:
            divs.append(i)
            j = N // i
            if i != j:
                divs.append(j)
    
    for div in divs:
        M = N
        while M % div == 0:
            M //= div
        if M % div == 1:
            ans += 1
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:


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

    def prime_factorize(n):
        res = []
        while n % 2 == 0:
            res.append(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                res.append(f)
                n //= f
            else:
                f += 2
        if n != 1:
            res.append(n)
        return res

    def isqrt(n):
        x = n
        y = (x + 1) // 2
        while y < x:
            x = y
            y = (x + n // x) // 2
        return x

    # N = K^a * (bK + 1)
    # if a == 0
    ans = 1
    for i in range(2, isqrt(N-1)+1):
        if (N-1) % i == 0:
            ans += 1
            if i != (N-1) // i:
                ans += 1
    
    # if a >= 1:
    divs = []
    for i in range(2, isqrt(N)+1):
        if N % i == 0:
            divs.append(i)
            j = N // i
            if i != j:
                divs.append(j)
    
    for div in divs:
        while N % div == 0:
            N //= div
        if N % div == 1:
            ans += 1
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def yakusu(A):
  arr = []
  limit = int(math.sqrt(A))
  for i in range(2,limit+1):
    if A % i == 0:
      arr.append(i)
      if i != A // i:
        arr.append(A//i)
  arr.append(A)
  arr.sort()
  return(arr)

yakusu_N = yakusu(N)
yakusu_N1 = yakusu(N-1)


      
def ope(a,N):
  while True:
    if N % a == 0:
      N = N / a
      if N == 1:
        return 1
        break
    else:
      N = N % a
      if N != 1:
        return 0
        break
      else :
        return 1
        break



count = 0 
for i in yakusu_N:  
  if ope(i,N) == 1:
    count += 1

print(count + len(yakusu_N1))

Submission status: Wrong Answer

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

def yakusu(A):
  arr = []
  limit = int(math.sqrt(A))
  for i in range(2,limit+1):
    if A % i == 0:
      arr.append(i)
      if i != A // i:
        arr.append(A//i)
  arr.append(A)
  arr.sort()
  return(arr)

yakusu_N = yakusu(N)
yakusu_N1 = yakusu(N-1)


      
def ope(a,N):
  while True:
    if N % a == 0:
      N = N / a
    else:
      N = N % a
      if N != 1:
        return 0
        break
    if N == 1:
      return 1
      break
    elif N < 1:
      return 0
      break



count = 0 
for i in yakusu_N:  
  if ope(i,N) == 1:
    count += 1

print(count + len(yakusu_N1))