AtCoder Beginner Contest 114
問題番号が綺麗。
C - 755
問題
- 1以上以下の整数の内、“753数”の個数を求めよ
- “753数”とは、7,5,3が1回以上現れ、その他の数字が現れない数を指す
例
335577 ... 753数 335574 ... 753数ではない(その他の数字が現れる) 555577 ... 753数ではない(3が現れない)
解法
の最大数 を1つ1つ“753数”かどうか確かめるのは時間的に無理。だが、3つの数字のみで構成された数だけを調べれば、 個くらいしか無いので大丈夫。
このような、使う数字が決められた数を順に調べるには、3進数を1ずつ増やしていき、0,1,2 を 3,5,7 にそれぞれ置き換える方法が考えられる。
生成される数は、もう1つの条件「3,5,7が最低1回は現れる」を満たさない物も含まれるので、そこだけチェックする。
しかし注意点として、3進数変換の方法だと最初に3が来るような数を上手く扱えない。(3進数に変換時に頭の0は省略されてしまうため)
よって、桁数を1からの桁数まで増やしながら固定し、に満たない分は0(→3に変換)で補うなどの方法が考えられる。
また、今回の場合制約がゆるいので、4進数で考えて、0を0のまま扱い、1,2,3 を 3,5,7 に置き換える方法もよい。(753数のチェック時に、0が含まれないかを追加する)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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
問題
- の約数を考える
- この中で、約数がちょうど75個であるものは何個あるか求めよ
解法
約数の個数は、素因数分解と関係がある。
と素因数分解できるの約数の個数は、個である。
さて、75個ということは、具体的な素数はさておき、次のいずれかのように表される数ということになる。
は、それぞれ自身の指数以上の因数が の中に無いといけない。 ( なら、 は の計算過程で4回以上掛け合わされていないといけない)
逆に、4回以上掛け合わされていたら、他の素因数の部分についてはどうなっていてもの約数には含まれる。 なので各素数がにいくつ含まれるかは独立に求めることが出来る。
では、どこまでの素数について求めておけばよいか。
上記のパターンの中で最低の指数は2なので、は、最低に2個は無いといけない。 一般論として、 を因数に持つ数で一番小さいのは、2番目に小さいのは のため、2個含まれているためには、 でないといけない。 よって、 の半分未満の素数までを調べておけばよい。
(注:この問題では関係ないが、個以上含まれるかどうかは必ずしも ではない。途中にやがあると、一気に指数が2,3個増えるため)
各素数がに含まれる個数を求めたら、各パターンで答えを計算する。 例えば の場合、(4個以上含まれる素数の個数)×(4個以上含まれる素数の個数-1)×(2個以上含まれる素数の個数ー2)/2で求まる。 同じ素数を選ぶことは出来ないため、-1,-2している。またこのパターンに限り、は入れ替え可能なので1/2している。 これを他のパターンでも求めればよい。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
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) |