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:
#F
import math
N = int(input())
M = N-1
n,m = int(math.sqrt(N)),int(math.sqrt(M))
yakuN = []
for i in range(1,n+1):
    if N%i == 0:
        if i != 1:
            yakuN.append(i)
        yakuN.append(N//i)
yakuM = []
for i in range(1,m+1):
    if M%i == 0:
        if i != 1:
            yakuM.append(i)
        yakuM.append(M//i)

ans = len(yakuM)
for yn in yakuN:
    X = N
    while True:
        if X%yn == 0:
            X //= yn
        else:
            X -= yn
            
        if X%yn == 1:
            ans+=1
            break
        elif X < 1:
            break
    

print(ans)

Submission status: Wrong Answer

Solution code:
#F
import math
N = int(input())
M = N-1
n,m = int(math.sqrt(N)),int(math.sqrt(M))
yakuN = []
for i in range(1,n+1):
    if N%i == 0:
        if i != 1:
            yakuN.append(i)
        yakuN.append(N//i)
yakuM = []
for i in range(1,m+1):
    if M%i == 0:
        if i != 1:
            yakuM.append(i)
        yakuM.append(M//i)
        
yakuN.sort()
yakuM.sort()

ans = len(yakuM)
for yn in yakuN:
    X = N
    while True:
        if X%yn == 0:
            X //= yn
        else:
            X -= yn
            
        if X%yn == 1:
            ans+=1
            break
        elif X < 1:
            break
    

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=2
s=set()
s.add(n)
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
for i in range(1,int((n-1)**0.5)+1):
  if (n-1)%(i+1)==0:
    if (n-1)//(i+1)==i+1:
      ans+=1
    else:
      ans+=2
print(ans)

Submission status: Wrong Answer

Solution code:
def f(n):
  d=[]
  for i in range(1,int(n**0.5)+1):
    if n%i<1:
      d+=i,
      if i!=n//i:d+=n//i,
  return d
n=int(input())
print(len(set(f(n-1)+[i for i in f(n)if n//i%i<2]))-1)

Submission status: Wrong Answer

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

N = int(input())

div = []
ans = 0

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

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

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

print(ans + len(div2)-1)

Submission status: Wrong Answer

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

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

print(ans+1)

Submission status: Wrong Answer

Solution code:
import sys,math,copy,queue,itertools,bisect
from fractions import gcd
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
EPS = 10**-8
INF = 10**18
MOD = 10**9 + 7
DD = ((1,0),(0,1),(-1,0),(0,-1))

N = NI()
ans = 0
max_b = int(math.log(N,2))
for x in range(2,int(math.sqrt(N))+1):
    if (N-1) % x == 0:
        if (N-1) == x**2:
            ans += 1
        else:
            ans += 2

    if N % x == 0:
        for b in range(1,max_b+1):
            k = round(x**(1/b))
            if k**b == x and k > 1:
                if (N//x-1) % k == 0:
                    ans += 1
            if x**2 != N:
                x = N // x
                k = round(x ** (1 / b))
                if k ** b == x and k > 1:
                    if (N // x - 1) % k == 0:
                        ans += 1

print(ans+2)

Submission status: Wrong Answer

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

N = int(input())

ans = 0

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

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


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

Submission status: Wrong Answer

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

N = int(input())

div = []
ans = 0

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

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

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

print(ans + len(div2)-1)

Submission status: Wrong Answer

Solution code:
import sys,math,copy,queue,itertools,bisect
from fractions import gcd
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
EPS = 10**-8
INF = 10**18
MOD = 10**9 + 7
DD = ((1,0),(0,1),(-1,0),(0,-1))

N = NI()
ans = 0
max_b = int(math.log(N,2))
for x in range(1,int(math.sqrt(N))+1):
    if (N-1) % x == 0:
        if (N-1) == x**2 or x == 1:
            ans += 1
        else:
            ans += 2

    if N % x == 0:
        for b in range(1,max_b+1):
            k = int(x**(1/b)+EPS)
            if k**b == x and k > 1:
                if (N//x-1) % k == 0:
                    ans += 1
print(ans+1)

Submission status: Wrong Answer

Solution code:
import sys,math,copy,queue,itertools,bisect
from fractions import gcd
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
EPS = 10**-8
INF = 10**18
MOD = 10**9 + 7
DD = ((1,0),(0,1),(-1,0),(0,-1))

N = NI()
ans = 0
max_b = int(math.log(N,2))
for x in range(1,int(math.sqrt(N))+1):
    if (N-1) % x == 0:
        if (N-1) == x**2 or x == 1:
            ans += 1
        else:
            ans += 2

    if N % x == 0:
        for b in range(1,max_b):
            k = int(x**(1/b)+EPS)
            if k**b == x and k > 1:
                if (N//x-1) % k == 0:
                    ans += 1
print(ans+1)

Submission status: Wrong Answer

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

N = int(input())

ans = 0

div = []
ans = 0

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

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

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

print(ans + len(div2)-1)

Submission status: Wrong Answer

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

N = int(input())

ans = 0

div = []
ans = 0

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

for d in div:
    tmp = N
    if N == d:
        ans += 1
        continue
    while tmp > d * 2:
        tmp //= d
    if (tmp-1) % d == 0:
        ans += 1

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

div2 = div2[1:]

print(ans + len(div2))

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
  
def divisorize(n):
    ## 約数
    f = factorization(n)
    divisors = [1]
    for k in range(len(f)):
        num_divisors = len(divisors)
        for i in range(1, f[k][1] + 1):
            for j in range(num_divisors):
                divisors.append(divisors[j] * f[k][0] ** i)
    return sorted(divisors)
  
n = int(input())
ans = 1
b = factorization(n-1)
chk = 1
for i in range(len(b)):
  chk *= (b[i][1]+1)
ans += chk-1
#print(divisorize(n))
for i in divisorize(n)[1:]:
  m = n
  while True:
    if m < i:
      break
    if m%i == 0:
      m = m//i
    else:
      m = m%i
      if m == 1:
        ans += 1
        break
        
if n == 2:
  ans = 1
  
print(ans)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

ans = 0

for i in range(2, N + 1):
    if i * i > N:
        if N == 2:
            ans += 1
        else:
            ans += 1
        break
    if (N - 1) % i == 0:
        ans += 1
        if (N - 1) // i != i:
            ans += 1
    elif N % i == 0:
        cand = [i]
        if N // i != i:
            cand.append(N // i)
        for c in cand:
            tmp = N
            while tmp % c == 0:
                tmp //= c
            if tmp % c == 1:
                ans += 1

# i = N-1, N
print(ans)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())

ans = 0

for i in range(2, N + 1):
    if i * i > N:
        ans += 2
        break
    if (N - 1) % i == 0:
        ans += 1
        if (N - 1) // i != i:
            ans += 1
    elif N % i == 0:
        cand = [i]
        if N // i != i:
            cand.append(N // i)
        for c in cand:
            tmp = N
            while tmp % c == 0:
                tmp //= c
            if tmp % c == 1:
                ans += 1

# i = N-1, N
print(ans)

Submission status: Wrong Answer

Solution code:
from math import sqrt


def divisors(x):
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            yield i
            yield x // i


n = int(input())

ans = 0
for e in divisors(n):
    if e == 1:
        continue

    r = n
    while r % e == 0:
        r //= e

    if r % e == 1:
        ans += 1

ans += len(list(divisors(n - 1))) - 1

print(ans)

Submission status: Wrong Answer

Solution code:
from math import sqrt


def divisors(x):
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            yield i
            yield x // i


n = int(input())

ans = 0
for e in divisors(n):
    if e == 1:
        continue

    r = n
    while r % e == 0:
        r //= e

    if r % e == 1:
        ans += 1

for e in divisors(n - 1):
    if e == 1:
        continue

    if n % e == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def gen(x):
    root = int(pow(x, 0.5))

    yield x

    for k in range(2, root):
        if x % k == 0:
            yield k
            yield x // k

    if x % root == 0:
        yield root
        if root != x // root:
            yield x // root


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

    # N%K!=0
    cnt = sum(1 for _ in filter(lambda x: x > 1, gen(N - 1)))

    # N%K==0
    for k in filter(lambda x: x > 1, gen(N)):
        x = N
        while x % k == 0:
            x //= k

        if x % k == 1:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ans = set([n])
    divisors = get_divisors(n)
    ans |= set(get_divisors(n-1))
    ans |= set([divisor for divisor in divisors if is_ok(n, divisor)])
    ans -= set([1])
    print(len(ans))

def is_ok(n, d):
    if d < 2:
        return False
    while n%d == 0:
        n //= d
    return n%d == 1

def get_divisors(n):
    out = []
    if n < 1:
        return out
    m = int(n**0.5)
    for i in range(1, m):
        if not n%i:
           out.append(i)
           out.append(n//i)
    if n == m**2 or n%m == 0:
        out.append(m)
    return out


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

n = int(input())
ans = set()

for x in make_divisors(n-1):
    if x != 1:
        ans.add(x)

for x in make_divisors(n):
    if x ==1 :
        continue
    if x == n:
        ans.add(x)
        continue
    m = n
    while m % x == 0:
        m = m//x
    
    if x in sorted(make_divisors(m-1)):
        # log(x)
        ans.add(x)

print(len(ans))

Submission status: Wrong Answer

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


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 solve(N: int):
    print(len(make_divisors(N-1))+1)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans = []
l = round(math.log2(N))
for i in range(1,l+1):
  if N**(1/i)%1==0:
    ans.append(N**(1/i)//1)

for i in range(2,round((N-1)**0.5)+1):
  if (N-1)%i == 0:
    ans.append(i)
    if (N-1)//i != i:
      ans.append((N-1)//i)
ans.append(N-1)

for i in range(2,round(N**0.5)+1):
  if N%i == 0:
    n = N
    while n%i==0:
      n//=i
    if n != 1 and n%i==1:
      ans.append(i)

print(len(ans))

Submission status: Wrong Answer

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

ans = []
l = round(math.log2(N))
for i in range(1,l+1):
  if N**(1/i)%1==0:
    ans.append(N**(1/i)//1)

for i in range(2,round((N-1)**0.5)+1):
  if (N-1)%i == 0:
    ans.append(i)
    if (N-1)//i != i:
      ans.append((N-1)//i)
ans.append(N-1)

for i in range(2,round(N**0.5)+1):
  if N%i == 0:
    n = N
    while n%i==0:
      n//=i
    if n != 1 and n%i==1:
      ans.append(i)

print(len(set(ans)))

Submission status: Wrong Answer

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

ans = []
l = round(math.log2(N))
for i in range(1,l+1):
  if round(N**(1/i))**i==N:
    ans.append(round(N**(1/i)))

for i in range(2,round((N-1)**0.5)+1):
  if (N-1)%i == 0:
    ans.append(i)
    if (N-1)//i != i:
      ans.append((N-1)//i)
ans.append(N-1)

for i in range(2,round(N**0.5)+1):
  if N%i == 0:
    n = N
    while n%i==0:
      n//=i
    if n != 1 and n%i==1:
      ans.append(i)

print(len(set(ans)))

Submission status: Wrong Answer

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

ans = []
l = round(math.log2(N))
for i in range(1,l+1):
  if round(N**(1/i))**i==N:
    ans.append(round(N**(1/i)))

for i in range(2,round((N-1)**0.5)+1):
  if (N-1)%i == 0:
    ans.append(i)
    if (N-1)//i != i:
      ans.append((N-1)//i)
ans.append(N-1)

for i in range(2,round(N**0.5)+1):
  if N%i == 0:
    n = N
    while n%i==0:
      n//=i
    if n != 1 and n%i==1:
      ans.append(i)

print(len(ans))

Submission status: Wrong Answer

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

ans = []
l = int(math.log2(N))
for i in range(1,l+1):
  if round(N**(1/i))**i==N:
    ans.append(round(N**(1/i)))

for i in range(2,round((N-1)**0.5)+1):
  if (N-1)%i == 0:
    ans.append(i)
    if (N-1)//i != i:
      ans.append((N-1)//i)
ans.append(N-1)

for i in range(2,round(N**0.5)+1):
  if N%i == 0:
    n = N
    while n%i==0:
      n//=i
    if n != 1 and n%i==1:
      ans.append(i)

print(len(ans))

Submission status: Wrong Answer

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

def factorize(n):
  b = 2
  fct = []
  while b * b <= n:
    while n % b == 0:
      n //= b
      fct.append(b)
    b = b + 1
  if n > 1:
    fct.append(n)
  return list(set(fct))

ans = []
l = int(math.log2(N))
for i in range(1,l+1):
  if round(N**(1/i))**i==N:
    ans.append(round(N**(1/i)))

for i in range(2,round((N-1)**0.5)+1):
  if (N-1)%i == 0:
    ans.append(i)
    if (N-1)//i != i:
      ans.append((N-1)//i)
ans.append(N-1)

fct = factorize(N)
for f in fct:
  n = N
  while n%f == 0:
    n //= f
  if n % f == 1 and n != 1:
    ans.append(f)

print(len(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
k = 2
count = set()
while k * k <= n:
    if n % k == 1:
        count.add(k)
        count.add((n-1)//k)
    elif n % k == 0:
        n_copy = n
        while n_copy % k == 0:
            n_copy //= k
        if n_copy % k == 1:
            count.add(k)
    k += 1
count.add(n-1)
count.add(n)
print(len(count))

Submission status: Wrong Answer

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

def factorize(n):
  b = 2
  fct = []
  while b * b <= n:
    while n % b == 0:
      n //= b
      fct.append(b)
    b = b + 1
  if n > 1:
    fct.append(n)
  return list(set(fct))

ans = []
l = int(math.log2(N))
for i in range(1,l+1):
  if int(N**(1/i))**i==N:
    ans.append(int(N**(1/i)))

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

fct = factorize(N)
for f in fct:
  n = N
  while n%f == 0:
    n //= f
  if n % f == 1 and n != 1:
    ans.append(f)

print(len(ans))

Submission status: Wrong Answer

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

def factorize(n):
  b = 2
  fct = []
  while b * b <= n:
    while n % b == 0:
      n //= b
      fct.append(b)
    b = b + 1
  if n > 1:
    fct.append(n)
  return list(set(fct))

ans = []
l = int(math.log2(N))
for i in range(1,l):
  if int(N**(1/i))**i==N:
    ans.append(int(N**(1/i)))

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

fct = factorize(N)
for f in fct:
  n = N
  while n%f == 0:
    n //= f
  if n % f == 1 and n != 1:
    ans.append(f)

print(len(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
k = 2
count = 0
while k * k <= n:
    if n % k == 1:
        if k*k == n-1:
            count += 1
        else:
            count += 2
    elif n % k == 0:
        n_copy = n
        while n_copy % k == 0:
            n_copy //= k
        if n_copy % k == 1:
            if k*k == n_copy-1:
                count += 1
            else:
                count += 2
    k += 1
print(count+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
k = 2
count = 0
while k * k <= n:
    if n % k == 1:
        if k == n-1 or k*k == n-1:
            count += 1
        else:
            count += 2
    elif n % k == 0:
        n_copy = n
        while n_copy % k == 0:
            n_copy //= k
        if n_copy % k == 1:
            if k == n_copy-1 or k*k == n_copy-1:
                count += 1
            else:
                count += 2
    k += 1
print(count)

Submission status: Wrong Answer

Solution code:
def check(i):
	tot=k
	while(tot%i==0):
		tot//=i
	if(tot%i==1):
		setl.add(i)
import math
k=int(input())
if(k==2):
	print(2)
	exit()
setl = set()
setl.add(k); setl.add(k-1)
for x in range(2,int(math.sqrt(k))+1):
	check(x)
	check(k//x)
print(len(setl))

Submission status: Wrong Answer

Solution code:
def check(i):
	tot=k
	while(tot%i==0):
		tot//=i
	if(tot%i==1):
		setl.add(i)
import math
k=int(input())
setl = set()
setl.add(k); setl.add(k-1)
for x in range(2,int(math.sqrt(k))+1):
	check(x)
	check(k//x)
print(len(setl))

Submission status: Wrong Answer

Solution code:
N = int(input())
cnt = 2

ret = []
for i in range(2, int(N**0.5)+1):
    if N % i == 0:
        k = N//i
        while k % i == 0:
            k //= i
        if k % i == 1:
            cnt += 1

        if N // i != i:
            j = N // i
            k = i
            while k % j == 0:
                k //= j
            if k % j == 1:
                cnt += 1

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

print(cnt)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
ans = 1
a_ = prime_factorize(n)
a = list(set(a_))
acol = collections.Counter(a_)
b = collections.Counter(prime_factorize(n-1))
for i in b.values():
    ans *= (i+1)
for i in range(len(a)):
    for j in range(i):
        if a[i]%a[j] == 1:
            temp = a[j]
            while a[i] % temp == 1:
                ans += 1
                temp *= a[j]
if sum(list(acol.values())) > 1 and len(a) == 1:
    ans += 1
# if list(acol.values()) == [1]:
#     ans = 2
# print(list(acol.values()))
print(ans)

Submission status: Wrong Answer

Solution code:
def yakusu(N):
    fin = int(N**0.5)

    num = list()
    for i in range(2, fin+1):
        if N % i == 0:
            num.append(i)
            if N != i**2:
                num.append(N//i)
    num.append(N)
    
    return num


N = int(input())


#N-1の約数の個数(から1を除く)
ans = len(yakusu(N-1))


#Nの約数の内、条件を満たすもの
arr = yakusu(N)
for i in range(len(arr)):
    tmp = N
    while tmp % arr[i] == 0:
        tmp //= arr[i]
    
    if tmp % arr[i] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def waru(n,k):
    while(n >= k):
        if(n%k == 0):
            n //= k
        else:
            n %= k
    if(n == 1):
        return 1
    else:
        return 0
n = int(input())
p = 0
if(n < 100):
    for i in range(2,n+1):
        p += waru(n,i)
    print(p)
else:
    for i in range(2,int(n**0.5)+2):
        if(n%i == 1):
            p += 1
        p += waru(n,i)
    print(p+2)

Submission status: Wrong Answer

Solution code:
def waru(n,k):
    while(n >= k):
        if(n%k == 0):
            n //= k
        else:
            n %= k
    if(n == 1):
        return 1
    else:
        return 0
n = int(input())
p = 0
if(n < 100):
    for i in range(2,n+1):
        p += waru(n,i)
    print(p)
else:
    for i in range(2,int(n**0.5)+1):
        if(n%i == 1):
            p += 1
        p += waru(n,i)
    print(p+2)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


def inpl():
    return list(map(int, input().split()))


def factor(n):
    ret = {}
    p = 2
    root_n = int(n**0.5)
    while n > 1:
        if n % p == 0:
            n //= p
            ret[p] = ret.get(p, 0) + 1
        elif p <= root_n:
            p += 1
        else:
            p = n
    return ret


def gcd(a, b):
    # greatest common divisor
    while b > 0:
        a, b = b, a % b

    return a


def backtrack(pn_list, k=1):
    if (not pn_list) and k != 1 and k != N:
        yield k

    p, v = pn_list[0]
    pn_list = pn_list[1:]
    for i in range(v + 1):
        backtrack(pn_list, k * (p**i))


def check(k):
    t = N
    while t % k == 0:
        t //= k
    return t % k == 1


def solve():
    pn = factor(N)
    ans = 0
    a = 1
    for v in pn.values():
        a = gcd(a, v)
    for v in factor(a).values():
        a *= v + 1
    ans += a

    a = 1
    for v in factor(N - 1).values():
        a *= v + 1
    ans += a

    pn_list = list(pn.items())
    for k in backtrack(pn_list):
        if check(k):
            ans += 1

    return ans


N = int(input())

print(solve())

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
ans = 1
a_ = prime_factorize(n)
a = list(set(a_))
acol = collections.Counter(a_)
b = collections.Counter(prime_factorize(n-1))
for i in b.values():
    ans *= (i+1)
for i in range(len(a)):
    for j in range(i):
        if a[i]%a[j] == 1:
            ans += 1
if sum(list(acol.values())) > 1 and len(a) == 1:
    ans += 1
# if list(acol.values()) == [1]:
#     ans = 2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


def inpl():
    return list(map(int, input().split()))


def factor(n):
    ret = {}
    p = 2
    root_n = int(n**0.5)
    while n > 1:
        if n % p == 0:
            n //= p
            ret[p] = ret.get(p, 0) + 1
        elif p <= root_n:
            p += 1
        else:
            p = n
    return ret


def gcd(a, b):
    # greatest common divisor
    while b > 0:
        a, b = b, a % b

    return a


def backtrack(pn_list, k=1):
    if not pn_list and k != 1 and k != N:
        yield k

    p, v = pn_list[0]
    pn_list = pn_list[1:]
    for i in range(v + 1):
        backtrack(pn_list, k * (p**i))


def check(k):
    t = N
    while t % k == 0:
        t //= k
    return t % k == 1


def solve():
    pn = factor(N)
    ans = 0
    a = 1
    for v in pn.values():
        a = gcd(a, v)
    ans += a

    a = 1
    for v in factor(N - 1).values():
        a *= v + 1
    ans += a

    pn_list = list(pn.items())
    for k in backtrack(pn_list):
        if check(k):
            ans += 1

    return ans


N = int(input())

print(solve())

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

# 約数を全列挙する関数
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

N0 = int(input())
ans = 0

# N = K^a (bK + 1) と表現できるので K は N or N-1 の約数であることが必要
K_cand = set(make_divisors(N0) + make_divisors(N0-1))
print(K_cand)

for K in K_cand:
    N = deepcopy(N0)
    if K == 1:  # K = 1 を除外
        continue
    else:
        while N%K == 0:
            N = N // K  # 割れるだけ割る
        N = N%K  # 引けるだけ引く
        if N == 1:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
nn=n-1
ans=set([nn])
for i in range(2,int(nn**0.5)+1):
  if nn%i==0:
    ans.add(i)
    ans.add(nn//i)
l=set()
l.add(n)
for i in range(2,int(n**0.5)+1):
  if n%i==0:
    l.add(i)
    l.add(n//i)
for j in l:
  m=n
  while m%j==0:
    m//=j
  if m%j==1:
    ans.add(j)
print(len(ans))

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
def check(x,m):
    if m % x == 0:
        return check(x,m//x)
    return m % x == 1

def count(n):
    cnt = 1
    f = defaultdict(int)
    for i in range(2,int(math.sqrt(n))+1):
        if n % i == 0 and f[i] == 0:
            cnt += 1
            f[i] = 1
            if f[n//i] == 0:
                cnt += 1
                f[n//i] = 1
    return cnt

def count2(n):
    cnt = 1
    f = defaultdict(int)
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            if check(i,n) and f[i] == 0:
                cnt += 1
                f[i] = 1
            if check(n//i,n) and f[n//i] == 0:
                cnt += 1
                f[n//i] = 1
    return cnt

ans = count(n-1)
ans += count2(n)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())


# nの約数列挙
def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass  # sortされていない


div_n = divisor(N)
div_n1 = divisor(N - 1)

ans = []
for d in div_n:
    nd = N // d
    if nd % d == 1 or nd % d == 0:
        ans.append(d)

for d in div_n1:
    if N % d == 0:
        nd = N // d
        if nd % d == 1 or nd % d == 0:
            ans.append(d)
    else:
        ans.append(d)


ans = list(set(ans))
# print(ans)
print(len(ans)-1)