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: Runtime Error

Solution code:
N=int(input())
count=0
list2=[]
for i in range(1,N+1) :
  if (N-1)%i==0 :
    if float((N-1)/i)>float(i) :
      if float(i)==float(1) :
      	list2.append(N-1)
      else :
        list2.append(i)
        list2.append(int(((N-1)/i)))
      
    elif float((N-1)/i)==float(i) :
      list2.appnd(i)
      
    else :
      
      break

count=len(list2)
list1=[]
for i in range(1,N+1) :
  if N%i==0 :
    if float(N/i)>float(i) :
      if float(i)==float(1) :
      	list1.append(N)
      else :
        list1.append(i)
        list1.append(int((N/i)))
      
    elif float(N/i)==float(i) :
      list1.appnd(i)
      
    else :
      
      break


for youso in list1 :
  
  if N%youso==0 :
    n1=N
    while (n1%youso==0) :
      n1=n1/youso
    if n1%youso==1 :
      count+=1
  
print(count)

Submission status: Runtime Error

Solution code:
sousa(n1,k) :
  n1=n
  while(i>1)
    if n%k=0 :
      n=n/k
    else :
      n-=k
  if n1==1 :
    return True
  else :
    return False
  
N=int(input())
count=0
for i in range(N):
  if sousa(N,i) :
    count+=1
print(count)

Submission status: Runtime Error

Solution code:
n=int(input())
nlist=make_divisors(n)
n1list=make_divisors(n-1)
# print(nlist)
# print(n1list)
answer=len(n1list)-1#1を除きます
for i in nlist[1:len(nlist)]:
    pra=n
    while (pra%i==0):
        pra=pra/i
    if pra%i==1:
        answer+=1
print(answer)

Submission status: Runtime Error

Solution code:
N=int(input())
if N%2==1:
  a=b
import numpy as np
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 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=np.array(make_divisors(N))
soin=factorization(N)
#print(d)
#(K: 314132908543,  )
#割り切れて１になる。。。。Nの一通り
#Kで割ってK+1になった 約数の差が１
# M*(x-K)=K+1
#(x-K)%K==1
#(x-K)/K=M:::1
#x-K=M*K+1
#N-1の約数
#２は必ず入る
#素因数分解して素数一つならそれも
count=0


#print(make_divisors(N-1))
S=make_divisors(N-1)
#print(soin)
#１除くN加える
ans=len(S)-1+1
if 2 not in S:
  ans+=1
if len(soin)==1 and soin[0][0]!=N:
  for i in range(1,soin[0][1]+1):
    if soin[0][1]%i==0 and (soin[0][0])**i not in S and (soin[0][0])**i not in [2,N]:
      ans+=1
      #print((soin[0][0])**i)
  
print(ans)
#print(S)

Submission status: Runtime Error

Solution code:
import collections
from itertools import combinations
import math
from functools import reduce
N = int(input())

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

def gcd(*numbers):
    return reduce(math.gcd, numbers)

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

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


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

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

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

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

Submission status: Runtime Error

Solution code:
import collections
from itertools import combinations
import math
from functools import reduce
N = int(input())

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

def gcd(*numbers):
    return reduce(math.gcd, numbers)

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

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


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

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

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

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

Submission status: Runtime Error

Solution code:
import collections
from itertools import combinations
import math
N = int(input())

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

def gcd(*numbers):
    return reduce(math.gcd, numbers)

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

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


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

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

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

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

Submission status: Runtime Error

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

def all_pattern(n):
    ans=0
    for ds in make_divisors(n):
        k=n
        if ds==1:
            continue
        while k%ds==0:
            k//=ds
        ans+=(k%ds==1 or k-k%ds==1)

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math

N = int(input())

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

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

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

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

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

Knn.extend(Kn1)
Knn.remove(1)
print(len(Knn))

Submission status: Runtime Error

Solution code:
N = int(input())

KMAX = math.floor(math.sqrt(N)) + 1
# KMAX = 1000

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

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

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

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

Knn.extend(Kn1)
print(len(Knn))
# print(sorted(Knn))

Submission status: Runtime Error

Solution code:
N=int(input)

ans = 0
for k in range(2, N//2+1):
  if N%k == 0:
    if (N/k-1)%k == 0: cnt +=1
  elif (N-1)%k==0: cnt += 1
    
print(ans)

Submission status: Runtime Error

Solution code:
class Tree():
    def __init__(self, n, edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - 1].append(e[1] - 1)
            self.tree[e[1] - 1].append(e[0] - 1)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)

    def rerooting(self, func, merge, ti, ei):
        dp = [ti for _ in range(self.n)]
        lt = [ei for _ in range(self.n)]
        rt = [ei for _ in range(self.n)]
        inv = [ei for _ in range(self.n)]
        self.setroot(0)
        for node in self.order[::-1]:
            tmp = ti
            for adj in self.tree[node]:
                if self.parent[adj] == node:
                    lt[adj] = tmp
                    tmp = func(tmp, dp[adj])
            tmp = ti
            for adj in self.tree[node][::-1]:
                if self.parent[adj] == node:
                    rt[adj] = tmp
                    tmp = func(tmp, dp[adj])
            dp[node] = tmp
        for node in self.order:
            if node == 0:
                continue
            merged = merge(lt[node], rt[node])
            par = self.parent[node]
            inv[node] = func(merged, inv[par])
            dp[node] = func(dp[node], inv[node])
        return dp

class Factorial():
    def __init__(self, n, mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i + 1] = self.factorial[i] * (i + 1) % mod
        self.inv[n] = pow(self.factorial[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod

    def fact(self, m):
        return self.factorial[m]

    def invfact(self, m):
        return self.inv[m]

import sys
input = sys.stdin.readline

MOD = 1000000007

N = int(input())
E = [tuple(map(int, input().split())) for _ in range(N - 1)]

T = Tree(N, E)
F = Factorial(N + 1, MOD)

def func(node, adj):
    size = node[1] + adj[1]
    count = node[0] * adj[0] * F.invfact(adj[1]) * F.fact(size - 1) * F.invfact(node[1] - 1)
    count %= MOD
    return count, size

def merge(lt, rt):
    size = lt[1] + rt[1] - 1
    count = lt[0] * rt[0] * F.invfact(lt[1] - 1) * F.invfact(rt[1] - 1) * F.fact(size - 1)
    count %= MOD
    return count, size

ti = (1, 1)
ei = (1, 0)

D = T.rerooting(func, merge, ti, ei)

res = []

for i in range(N):
    res.append(D[i][0])

print('\n'.join(map(str, res)))

Submission status: Runtime Error

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))
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
            a[i] //= a[j]
print(ans)

Submission status: Runtime Error

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 True
    if N % K ==1:
        return True
    if N<K:
        return False
    
    if N % K ==0:
        return check(N//K,K)
    else:
        return False


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

    print(len(x | ys2))


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
N = int(input())

def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return (_N-1)%p == 0

n = int(N**0.5) + 1
P0 = set([N])
P1 = set([N-1])
for i in range(2, n+1):
  if (N-1)%i == 0:
    P1.add(i)
    P1.add((N-1)//i)
  if N%i == 0:
    P0.add(i)
    P0.add(N//i)

P2.discard(1)
P1.discard(1)
ans = len(P1)
for p in P0:
  ans += check(p)

print(ans)

Submission status: Runtime Error

Solution code:
from copy import deepcopy
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
            if N//i != i:
                ans.append(i)
    return ans

def check(K,N):
    while N>=K:
        if N%K == 0:
            N = N//K
        else:
            N = N%K
    if N == 1:
        return True
    else:
        return False

N = int(input())
ans = len(factor(N-1)[1:])
for K in factor(N)[1:]:
    if check(K,N):
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
from copy import deepcopy
import numpy as np
def factor(N):
    ans = []
    for i in range(1,int(np.sqrt(N))+1):
        if N%i == 0:
            ans.append(i)
            if N//i != i:
                ans.append(i)
    return ans

def check(K,N):
    while N>=K:
        if N%K == 0:
            N = N//K
        else:
            N = N%K
    if N%K == 1:
        return True
    else:
        return False

N = int(input())
ans = len(factor(N-1)[1:])
for K in factor(N)[1:]:
    if check(K,N):
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
cnt = 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 != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
N1_yakusu = make_divisors(N-1)
N_yakusu = make_divisors(N)
cnt += len(N1_yakusu)
for s in N_yakusu:
    new_N = s
    while(new_N%K==0):
        new_N = new_N//K
    if(new_N%K == 1):
        cnt += 1
print(cnt)

Submission status: Runtime Error

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

import collections
A=collections.Counter(prime_factorize(n-1))
B=collections.Counter(prime_factorize(n))
ans=1
cnt=0
for a,b in A.items():
    ans*=(b+1)

import math
for i in range(1,math.floor(n**0.5)+1):
    if n%i==0:
        if j in B.keys():
            if (n // (j ** B[j])) % j == 1:
                cnt+=1
        else:
            if (n//i)%i==1:
                cnt+=1
                
        if (i-1)%(n//i)==0:
            cnt+=1
            
print(ans-1+cnt)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
typedef pair<int,int> P;
const int inf=1000000007;
const int MOD=1000000007;

int calc(int n){
  vector<int> p(1000008,1);
  //cout<<"OK"<<endl;
  int buf=n;
  for(int i=2;i<=1000007;i++){
    while(buf%i==0){
      p[i]++;
      buf/=i;
      //printf("i=%lld\n",i);
    }
    if(buf==1)break;
  }
  //cout<<"OK"<<endl;
  int hoge=1;
  rep1(i,1000007){
    hoge*=p[i];
  }
  //cout<<buf<<"\n";
  if(buf!=1){
    hoge*=2;
  }
  //printf("ans=%lld\n",21*buf);
  return hoge-1;
}
signed main(){
  int n;cin>>n;
  int res=1;
  if(n<=1000007){
    for(int i=2;i<n;i++){
      int buf=n;
      if(buf%i!=0){
        buf%=i;
        if(buf==1)res++;
      }
      else{
        while(buf%i==0){
          buf/=i;
        }
        buf%=i;
        if(buf==1)res++;
      }
    }
  }
  else{
    res=1;
    for(int i=2;i<=1000007;i++){
      int buf=n;
      if(buf%i!=0){
        buf%=i;
        //if(buf==1)res++;
      }
      else{
        while(buf%i==0){
          buf/=i;
        }
        buf%=i;
        if(buf==1){
          res++;
          //cout<<i<<endl;
        }
      }
      //cout<<i<<"\n";
    }
    //cout<<res<<"\n";
    res+=calc(n-1);
    //cout<<calc(n-1)<<"\n";
  }
  cout<<res<<"\n";
  return 0;
}

Submission status: Runtime Error

Solution code:
n=int(input())
N=[n]
import collections
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0 and i!=1:
      divisors.append(i)
      if i != n // i and n//i!=1:
        divisors.append(n//i)
  return divisors+[n]
t=make_divisors(n)+make_divisor(n-1)
ans=0
for k in t:
  n=N[0]
  while n>=k:
    if n%k==0:
      n//=k
    else:
      n-=k
  if n==1:
    ans+=1
print(ans)

Submission status: Runtime Error

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())
a = factorization(n)
ans = 1
if len(a) == 1 and a[0]!=n:
  ans += a[1]-1
b = factorization(n-1)
chk = 1
for i in range(len(b)):
  chk *= (b[i][1]+1)
ans += chk-1
if len(a) >= 2:
  for i in range(len(a)):
    for j in range(1,a[i][1]+1):
      #print(a[i][0]**(j),int(n/(a[i][0]**(j))),int(n/(a[i][0]**(j)))%(a[i][0]**(j)))
      if int(n/(a[i][0]**(a[i][1]+1-j)))%(a[i][0]**(j)) == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

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

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

    # divisors.sort()
    return divisors


def warizan(x,k):
    a = 1
    for _ in range(1000000000):
        print(k^(a+1))
        if x % (k^(a+1)) != 0:
            break
        else:
            a += 1
    return x/(k^a)

k_list = make_divisors(N)
for k in k_list:
    x = warizan(N,k)
    if (x-1) % k == 1:
        ans_list.append(x)

k_list_2 =  make_divisors(N-1)
ans_list.extend(k_list_2)
print(len(set(ans_list)))

Submission status: Runtime Error

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())
a = factorization(n)
ans = 1
if len(a) == 1 and a[0]!=n:
  ans += a[1]-1
b = factorization(n-1)
chk = 1
for i in range(len(b)):
  chk *= (b[i][1]+1)
ans += chk-1
#print(a)
if len(a) >= 2:
  for i in range(len(a)):
    for j in range(a[i][1]+1):
      if j!=0 and int(n/(a[i][0]**(j)))%(a[i][0]**(j)) == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

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())
a = factorization(n)
ans = 1
if len(a) == 1 and a[0]!=n:
  ans += a[1]-1
b = factorization(n-1)
chk = 1
for i in range(len(b)):
  chk *= (b[i][1]+1)
ans += chk-1
print(a)
if len(a) >= 2:
  for i in range(len(a)):
    for j in range(a[i][1]+1):
      if j!=0 and int(n/(a[i][0]**(j)))%(a[i][0]**(j)) == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
n, k, c = [int(x) for x in input().split()]
s = input()
counts = [[0] * 2 for i in range(n)]
for i in range(n):
    if s[i] == 'x':
        if i > 0:
            counts[i] = [max(counts[i - 1]), 0]
        else:
            counts[0]= [0, 0]
        continue
    if i == 0:
        counts[0]= [0, 1]
    elif i <= c:
        counts[i] = [max(counts[i - 1]), 1]
    else:
        counts[i] = [max(counts[i - 1]), max(counts[i - c - 1]) + 1]
r = []
checkk = k
nextgap = n
for i in range(n - 1, -1, -1):
    if i < nextgap and counts[i][1] >= checkk:
        if counts[i][0] < checkk:
            r.append(i + 1)
        checkk -= 1
        if checkk == 0:
            break
        nextgap = i - c
for i in range(len(r) - 1, -1, -1):
    print(r[i])

Submission status: Runtime Error

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 True
    if N % K ==1:
        return True
    if N<K:
        return False
    
    if N % K ==0:
        return check(N//K,K)
    else:
        return False


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

    print(len(x|x2))


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

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 True
    if N % K ==1:
        return True
    if N<K:
        return False
    
    if N % K ==0:
        return check(N//K,K)
    else:
        return False


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

    print(len(x))


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
N = int(input())

ans = 2 # N and N-1                                                                                                                                                                 
for K in range(2, N):
    if K*K>N: break
    n = N
    if n%K!=0: continu-e
    while n%K==0: n//=K
    if n%K==1: ans +=1

y = 0
N_ = N-1
for K in range(2, N):
    if K*K>=N_: break
    if N_%K==0: y +=2
if K*K==N_: y += 1

print(ans+y)

Submission status: Runtime Error

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

prod = functools.partial(functools.reduce, operator.mul)
MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def solve():
    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)
    prime_temp = []
    primes2 = prime_factorization(N - 1)
    List = []
    for i in range(2 ** (len(primes2))):
        prid = prod([primes2[j] if i & (1 << j) else 1 for j in range(len(primes2))])
        if prid != 1:
            List.append(prid)
    List = list(set(List))
    prime_set = list(set(primes + prime_temp))
    for i in prime_set:
        temp = N
        while temp % i == 0:
            temp //= i
        if temp % i == 1:
            List.append(i)
    List = list(set(List))
    print(len(List) + 1 if N not in List else len(List))


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
n = int(input())
n = n-1
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 != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

li = make_divisors(n)

for i in range(2,n+1):
    if i**2 > n:
        break
    tmp = n
    #print(i)
    while tmp % i == 0:
        #print(tmp)
        #exit()
        tmp = tmp / i
    if tmp % i == 1:
        ans += 1
        li.append(i)
        
print(unique(li)-1)

exit()

for i in range(2,n+1):
    """
    if i**2 > n:
        break
    """
    tmp = n
    #print(i)
    if tmp % i == 0:
        #print(tmp)
        #exit()
        #tmp = tmp / i
        ans += 1
        print(i)
    """
    if tmp == 1:
        ans += 1
        print(i)
    """
        
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
cnt=0
for k in range(w, N):
    x = N
    while x < k:
        if x % k == 0:
            x /= k
        else:
            x -= K
    if x == 1:
        cnt += 1

Submission status: Runtime Error

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())
a = factorization(n)
ans = 2
if len(a) == 1 and a[0]!=n:
  ans += a[1]-1
b = factorization(n-1)
chk = 1
for i in range(len(b)):
  chk *= (b[i][1]+1)
ans += chk-1

if len(a) >= 2:
  for i in range(len(a)):
    for j in range(a[i][1]):
      if int(n/(a[i][0]**j))%a[i][0]**j == 0:
        ans += 1
print(ans)

Submission status: Runtime Error

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,min(n-1,int(n**.5)+1)):
# for i in range(2,n*+1):
  if n % i == 0:
    tmp = n

    while tmp % i == 0:
      tmp //= i
    if tmp % i == 1:ans += 1
  
    if tmp //i ==
    tmp = n; i = n // i
    while tmp % i == 0:
      tmp //= i
    if tmp % i == 1:ans += 1

  elif (n-1) % i == 0:ans += 2

if n != 1:ans += 2
else: ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
res=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 != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
if (n<1000007):
    for i in range(n+1):
        if(i<=1):
            continue
        if(n%i!=0):
            if(n%i==1):
                res+=1
        else:
            buf=n
            while(buf%i==0):
                buf//=i
            if(buf%i==1):
                res+=1
else:
    res=1
    for i in range(1000006):
        if(i<=1):
            continue
        if(n%i!=0):
            if(n%i==1):
                res+=1
        else:
            buf=n
            while(buf%i==0):
                buf//=i
            if(buf%i==1):
                res+=1
    n-=1
    l+=make_divisors(n)
    hoge=1
    for i in range(l):
        hoge*=l[i]+1
    res+=hoge
print(res)

Submission status: Runtime Error

Solution code:
N = int(input())

def yakusu(n):
	rn = int(n ** 0.5)
	ans = 0
	for i in range(1, int(n**0.5)):
		if n % i == 0:
			ans += 2
	if rn*rn == n:
		ret += 1
	return ret

#A = [True for i in range(10**6 + 1)]
ans = 1 # K = N
for i in range(2, min(N, 10**6+1)):
	if N % i > 0:
		continue
	if i == 2:
		ans += 1
		continue
	n = N
	while n % i == 0:
		n = n // i
	if n % i == 1:
		ans += 1
print(ans + yakusu(N-1) - 1)

Submission status: Runtime Error

Solution code:
n=int(input())
cnt=0
for i in range(n):
    if ((n/i-1)%n)==0:
        cnt+=1

print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())
cnt=0
for i in range(n):
    if (n/i-1)%n==0:
        cnt+=1

print(cnt)