Problem:

C: 約数ゲーム / Divisor Game

問題

tsutaj くんは約数ゲームで遊ぼうとしています。

約数ゲームでは、まず 2 以上の自然数 N が与えられ、その後は以下の手順でゲームが進んでいきます。

 N 以外の N の約数の中から、整数を 1 つ宣言する。ただしこのとき、既に宣言したことがある整数の約数になるものは宣言できない。

 宣言できる整数がある限りこれを繰り返し、宣言できるものがなければゲームは終了する。

ゲームを終了させるまでに行われた宣言の回数としてあり得る数の最小値と最大値を求めてください。

入力形式

入力は 1 行で与えられる。

N

制約

 2 \leq N \leq 10^{12}

出力形式

宣言回数の最小値と最大値を、スペース区切りで 1 行に出力せよ。

入力例1

18

出力例1

2 5

宣言回数を 2 回にする一例は以下の通りです。

 9 を宣言する。

 6 を宣言する。 (6 は 9 の約数ではないため宣言が可能である)

これを行うと、18 の約数で 18 でない任意の整数は今まで宣言してきた整数の約数になるため、ゲームが終了します。

既に宣言したことがある整数の約数になるものは宣言できないことに注意してください。例えば、 9 を宣言したあとに 3 を宣言することはできません。なぜなら、3 は 9 の約数になるからです。

入力例2

99

出力例2

2 5

入力例3

10000000019

出力例3

1 1

入力は 32 bit 整数型に収まらない場合があります。



Sample input:
18


Sample output:
2 5

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(input())
    import math
    
    
    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f
    def make_prime_list_2(num):
        if num < 2:
            return []
    
        # 0のものは素数じゃないとする
        prime_list = [i for i in range(num + 1)]
        prime_list[1] = 0  # 1は素数ではない
        num_sqrt = math.sqrt(num)
    
        for prime in prime_list:
            if prime == 0:
                continue
            if prime > num_sqrt:
                break
    
            for non_prime in range(2 * prime, num, prime):
                prime_list[non_prime] = 0
    
        return [prime for prime in prime_list if prime != 0]
    
    
    def prime_factorization_2(num):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""
    
        if num <= 1:
            # 例えば1を食ったときの対処の仕方は問題によって違うと思うのでそのつど考える。
            # cf. https://atcoder.jp/contests/abc110/submissions/12688244
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)
    
            dict_counter = {}  # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452
    
            for prime in prime_list:
                while num % prime == 0:
                    if prime in dict_counter:
                        dict_counter[prime] += 1
                    else:
                        dict_counter[prime] = 1
                    num //= prime
            if num != 1:
                if num in dict_counter:
                    dict_counter[num] += 1
                else:
                    dict_counter[num] = 1
    
            return dict_counter
    d=prime_factorization_2(n)
    val=1
    for v in d.values():
        val*=(v+1)
    print(len(d),val-1)

    
resolve()

Submission status: Accepted

Solution code:
import math

n = int(input())
p = list()
m = int(math.sqrt(n)+1)
for i in range(2,m):
    if n%i == 0:
        c = 0
        while n%i == 0:
            c += 1
            n //= i
        p.append(c)
if n != 1:
    p.append(1)
maxi = 1
for x in p:
    maxi *= (x+1)
print(len(p),maxi-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''
import copy

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 main():
    N = int(input())
    yakusu = make_divisors(N)
    max_times = len(yakusu) - 1
    min_times = 0
    result = []
    for i in reversed(yakusu[:-1]):
        if i in result:
            continue
        result.extend(make_divisors(i))
        # print(result)
        min_times += 1
    print(min_times, max_times)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools as ite
from decimal import *
import math

INF = 10 ** 18

n = input()
i = 2
ls = []
while i * i <= n:
    if n % i == 0:
        cnt = 0
        while n % i == 0:
            cnt += 1
            n /= i
        ls += [cnt]
    i += 1
if n != 1:
    ls += [1]
ans1 = len(ls)
ans2 = 1
for num in ls:
    ans2 *= num + 1
ans2 -= 1
print ans1, ans2

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
"""
n,m = LI()
a = LI()
b = LI()
li = list(set(a)|set(b))
li2 = list(set(a)&set(b))
li.sort()
li2.sort()
print(len(li2),len(li))
for i in li2:
    print(i)
for i in li:
    print(i)
"""

#B
"""
n = I()
p = LI()
p.append(float("inf"))
ans = ""
i = 0
l = 0
k = [i+1 for i in range(n)]
while i < n:
    if p[i] < p[i+1]:
        a = p[l:i+1][::-1]
        if a != k[l:i+1]:
            print(":(")
            quit()
        l = i+1
        for d in range(len(a)):
            ans += "("
        for d in range(len(a)):
            ans += ")"
    i += 1
print(ans)
"""
#C
def fact(n):
    i = 2
    a = n
    if n < 4:
        return [1,n],[n]
    li = [1,n]
    while i**2 <= a:
        if n%i == 0:
            li.append(i)
            if i != n//i:
                li.append(n//i)
        i += 1
    li.sort()
    i = 2
    if len(li) == 2:
        return li,[a]
    k = []
    b = a
    while i**2 <= b:
        if a%i == 0:
            k.append(i)
            while a%i == 0:
                a//= i
        i += 1
    if a!=1:
        k.append(a)
    return li,k
n = I()
l,k = fact(n)
if len(l) == 2:
    print(1,1)
else:
    print(len(k),len(l)-1)
#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e7))
from collections import deque
def inpl(): return list(map(int, input().split()))

def primes(N):
    sieve = [1]*(N+1)
    sieve[0], sieve[1] = 0, 0
    P = []
    for i in range(2, N+1):
        if sieve[i]:
            P.append(i)
            for j in range(2*i, N+1, i):
                sieve[j] = 0
    return P

N = int(input())
P = primes(10**6 + 10)

factors = [0]*len(P)
for i in range(len(P)):
    p = P[i]
    while N%p == 0:
        factors[i] += 1
        N = N//p

factors += [N!=1]
a = sum([f > 0 for f in factors])
b = 1
for i in range(len(P)+1):
    b *= factors[i] + 1

b -= 1

print(a, b)