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)
