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 ... \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)

            

        
      