AtCoder Beginner Contest 114

AtCoder Beginner Contest 114

問題番号が綺麗。

C - 755

問題

  • 1以上$N$以下の整数の内、“753数”の個数を求めよ
  • “753数”とは、7,5,3が1回以上現れ、その他の数字が現れない数を指す
  • $N \le 10^9$

335577 ... 753数
335574 ... 753数ではない(その他の数字が現れる)
555577 ... 753数ではない(3が現れない)

解法

$N$ の最大数 $10^9$ を1つ1つ“753数”かどうか確かめるのは時間的に無理。だが、3つの数字のみで構成された数だけを調べれば、$3^9 \le 20000$ 個くらいしか無いので大丈夫。

このような、使う数字が決められた数を順に調べるには、3進数を1ずつ増やしていき、0,1,2 を 3,5,7 にそれぞれ置き換える方法が考えられる。

生成される数は、もう1つの条件「3,5,7が最低1回は現れる」を満たさない物も含まれるので、そこだけチェックする。

しかし注意点として、3進数変換の方法だと最初に3が来るような数を上手く扱えない。(3進数に変換時に頭の0は省略されてしまうため)

よって、桁数$d$を1から$N$の桁数まで増やしながら固定し、$d$に満たない分は0(→3に変換)で補うなどの方法が考えられる。

また、今回の場合制約がゆるいので、4進数で考えて、0を0のまま扱い、1,2,3 を 3,5,7 に置き換える方法もよい。(753数のチェック時に、0が含まれないかを追加する)

def base_10_to_n_ex(x, n=4):
    d, m = divmod(x, n)
    mm = '0' if m == 0 else '3' if m == 1 else '5' if m == 2 else '7'
    if d:
        return base_10_to_n_ex(d, n) + mm
    return mm


n = int(input())
i = 27
s = '357'
ans = 0
while int(s) <= n:
    if '3' in s and '5' in s and '7' in s and '0' not in s:
        ans += 1
    i += 1
    s = base_10_to_n_ex(i)
print(ans)

D - 756

問題

  • $N!=1 \times 2 \times \ldots \times N$ の約数を考える
  • この中で、約数がちょうど75個であるものは何個あるか求めよ
  • $N \le 100$

解法

約数の個数は、素因数分解と関係がある。

$x=p^aq^br^c$ と素因数分解できる$x$の約数の個数は、$(a+1)(b+1)(c+1)$個である。

さて、75個ということは、具体的な素数$p,q,r$はさておき、次のいずれかのように表される数ということになる。

  • $p^4q^4r^2$
  • $p^{14}q^4$
  • $p^{24}q^2$
  • $p^{74}$

$p,q,r$は、それぞれ自身の指数以上の因数が $N!$ の中に無いといけない。 ($p^4$ なら、$p$ は $N!$ の計算過程で4回以上掛け合わされていないといけない)

逆に、4回以上掛け合わされていたら、他の素因数の部分についてはどうなっていても$N!$の約数には含まれる。 なので各素数が$N!$にいくつ含まれるかは独立に求めることが出来る。

では、どこまでの素数について求めておけばよいか。

上記のパターンの中で最低の指数は2なので、$p,q,r$は、最低$N!$に2個は無いといけない。 一般論として、$p$ を因数に持つ数で一番小さいのは$p$、2番目に小さいのは$2p$ のため、2個含まれているためには、$2p \le N$ でないといけない。 よって、$N$ の半分未満の素数までを調べておけばよい。

(注:この問題では関係ないが、$k \ge 3$個以上含まれるかどうかは必ずしも$kp \le N$ ではない。途中に$p^2$や$p^3$があると、一気に指数が2,3個増えるため)

各素数が$N!$に含まれる個数を求めたら、各パターンで答えを計算する。 例えば $p^4q^4r^2$ の場合、(4個以上含まれる素数の個数)×(4個以上含まれる素数の個数-1)×(2個以上含まれる素数の個数ー2)/2で求まる。 同じ素数を選ぶことは出来ないため、-1,-2している。またこのパターンに限り、$p,q$は入れ替え可能なので1/2している。 これを他のパターンでも求めればよい。

from itertools import takewhile


def prime_cnt(x):
    y = x
    ret = 0
    while y <= n:
        z = y
        while z > 0 and z % x == 0:
            ret += 1
            z //= x
        y += x
    return ret


n = int(input())
ps = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
pc = list(map(prime_cnt, ps))

l2 = len(list(takewhile(lambda x: x >= 2, pc)))
l4 = len(list(takewhile(lambda x: x >= 4, pc)))
l14 = len(list(takewhile(lambda x: x >= 14, pc)))
l24 = len(list(takewhile(lambda x: x >= 24, pc)))
l74 = len(list(takewhile(lambda x: x >= 74, pc)))
ans = l4 * max(0, l4 - 1) * max(0, l2 - 2) // 2
ans += l14 * max(0, l4 - 1)
ans += l24 * max(0, l2 - 1)
ans += l74

print(ans)

programming_algorithm/contest_history/atcoder/2018/1202_abc114.txt · 最終更新: 2018/12/03 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0