AtCoder Beginner Contest 114 - 競プロやります。

C - 755
D - 756

C - 755

https://atcoder.jp/contests/abc114/tasks/abc114_c

方針

$N$ 以下の全ての整数について七五三数であるかをチェックしていくと間に合いません。他方で七五三数はそんなに多くないので、 $10^9$ 以下の七五三数を全て列挙し、 $N$ 以下のものを数えるという方針でいきます。

列挙の際は、まず $n = 0$ をもとに $10n + 3, 10n+5, 10n+7$ を再帰的にvectorに詰めていきます( $10^9$ より大きくなったところで打ち切ります)。これらは3, 5, 7のみが現れる数ですが、例えば33や5575など、七五三数ではないものも含まれます。そこで $N$ 以下を判定するときに、一緒に3, 5, 7を全て含むかどうかもチェックすればよいです。値をstringに変換し、findを使えばこのチェックが出来ます。

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll> num753;

void append(ll n){
    if(n < 1e9){
        num753.push_back(n);
        append(n*10+3);
        append(n*10+5);
        append(n*10+7);
    }
}
int main(){
    int N;  cin >> N;
    append(0);

    int n = num753.size();
    int ans = 0;
    for(int i=0; i<n; i++){
        if(num753[i]<=N){
            string S = to_string(num753[i]);
            if(find(S.begin(), S.end(), '3') != S.end() && find(S.begin(), S.end(), '5') != S.end() && find(S.begin(), S.end(), '7') != S.end()){
                ans++;
            }
        }
    }
    cout << ans << endl;
}

メモ

ある数 $n$ が七五三数のとき、1桁目に3, 5, 7を追加した $10n + 3, 10n+5, 10n+7$ も七五三数になります。当初、3桁の七五三数とこの関係を用いれば全ての七五三数が列挙出来ると誤解しましたが、例えば3557が反例になりますね。

D - 756

https://atcoder.jp/contests/abc114/tasks/abc114_d

方針

ある数 $n$ が素数 $\{p_i\}$ を用いて $n = p_1^{i_1}~p_2^{i_2} \dots$ と素因数分解出来るとき、 $n$ の約数の数は $(i_1+1)(i_2+1) \dots$ となります。したがって、 $n$ が約数をちょうど75個持つとき、 $(i_1+1)(i_2+1) \dots = 75$ となります。 $75 = 3*5*5$ ですから、これは $n$ が

$p_1^{74}$
$p_1^{2}~p_2^{24}$
$p_1^{4}~p_2^{14}$
$p_1^{2}~p_2^{4}~p_3^{4}$

のどれかで書けることと同値です。今回 $n$ は $N!$ の約数なので、まずは $N!$ を素因数分解し、そこから上記を満たす $n$ をいくつ作れるかを考えます。以下では $N! = p_1^{i_1}~p_2^{i_2} \dots$ とします。

(1) $n = p_1^{74}$ のとき
$i_1, i_2, \dots$ の中に、74以上のものが何個あるかを数えればよいです。

(2) $n = p_1^{2}~p_2^{24}$ のとき
$i_1, i_2, \dots$ の中の、(24以上のものの数)×(2以上のものの数 - 1) です。1を引いているのは、24以上のものの数を1個使うと、2以上のものが1個減るからです。

(3) $n = p_1^{4}~p_2^{14}$ のとき
(2)と同じで、(14以上のものの数)×(4以上のものの数 - 1)

(4) $n = p_1^{2}~p_2^{4}~p_3^{4}$ のとき
(4以上のものを2つ選ぶ場合の数)×(2以上のものの数 - 2) = (4以上のものの数)*(4以上のものの数 - 1) /2 * (2以上のものの数 - 2)

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;  cin >> N;
    vector<bool> prime(N+1, true);
    // N以下の素数を列挙する。i が素数の時 prime[i] = true。
    prime[0] = false; prime[1] = false; prime[2] = true;
    for(int i=3; i<=N; i++) for(int j=2; j<i; j++) if(i%j==0){
        prime[i] = false;
        break;
    }

    // N! を素因数分解し、j の指数を a[j] に格納する。
    // j が素数でないときは a[j] = 0。
    vector<int> a(N+1,0);
    for(int i=2; i<=N; i++){
        int n = i;
        for(int j=2; j<=N; j++){
            if(prime[j]){
                while(n%j==0){n/=j;  a[j]++;}
            }
        }
    }
    sort(a.begin(), a.end());
    int ans = 0;
    ans += a.end() - lower_bound(a.begin(), a.end(), 74);
    ans += (a.end() - lower_bound(a.begin(), a.end(), 24))*(a.end() - lower_bound(a.begin(), a.end(), 2) - 1);
    ans += (a.end() - lower_bound(a.begin(), a.end(), 14))*(a.end() - lower_bound(a.begin(), a.end(), 4) - 1);
    ans += (a.end() - lower_bound(a.begin(), a.end(), 4))*(a.end() - lower_bound(a.begin(), a.end(), 4) - 1) / 2 * (a.end() - lower_bound(a.begin(), a.end(), 2) - 2);
    cout << ans << endl;
}

メモ

lower_bound(a.begin(), a.end(), num) は a の中の num 以上の値が格納される一番最初のイテレータを返します。これを用いると、a が昇順にソートされているとき、num 以上の値の数を以下で求めることができます。

a.end() - lower_bound(a.begin(), a.end(), num)