0の個数を求めます

3070 ワード
アルゴリズム#アルゴリズム# テキストリンク

0は2と5の積です。



「backjun1676号：工場0個」を初めて解いたとき、factorial関数を実装して演算し、文字列に変換し、後で文字の計算を開始しようとしました.しかし、結果は失敗だった.500!の場合、数字が大きいです.
検索してみると、実際の計算をする必要がないという問題です.
0=2× 5なので、Nの2と5個まで数えたら、小さい値が正解です.

𕼧2と5はどちらが多いですか。


しかし考えてみれば、2は5未満の授与なので、小因式を分解した結果、自然と5の個数が減る.したがって,0の個数は1からN,数に含まれる5の個数でよい.
(もちろん、通常は2と5の数を数えてから、小さい値を答えにします.)
実施に際して注意すべき点は、5の平方数(例えば25、125)が複数の5を含むため、処理が必要であることである.

📍 実施(bj 1676)


[1]

while (n >= 5) {
    cnt += n / 5; 
    n /= 5;
}
単純に5に分けるのではなく、繰り返し文を5に分けて累積値を求める.

[2]

for (int i = 1; i <= n; i++) {

    int num = i;
    while (num % 5 == 0) {  // 5로 나눠떨어질 때만 고려 
        num /= 5;
        cnt++;
    }
}

[3]一般的には-2と5を考慮する

int main() {
    int n;
    int two = 0;
    int five = 0;
    cin >> n;

    for (int i = 2; i <= n; i *= 2) {
        two += n / i; 
    }

    for (int i = 5; i <= n; i *= 5) {
         five += n / i; 
    }

    // two, five 중에 작은 값이 정답 
    if (two > five) cout << five;
    else cout << two;
}

一般を見る



白駿2004号:組み合わせ0の個数も同様の問題である.

n,kおよび(n−k)についてそれぞれ2および5個の数を求める.
2と5の「n!時数-(k!時数+(n-k)!時数)」の小さな値が正解です.

📍 実施(bj 2004)

pair<long long, long long> getZero(long long n) {
    long long two = 0, five = 0;

    for (long long i = 2; i <= n; i *= 2) two += n / i;
    for (long long i = 5; i <= n; i *= 5) five += n / i;

    return (pair<long long, long long> (two, five));
}
整数の範囲を考慮して、長い資料型を使います.
関連問題-白準1676号：工場0の個数、白駿2004号:組み合わせ0の個数
注意リンク:https://st-lab.tistory.com/165、https://sihyungyou.github.io/baekjoon-1676/、
フル・バックアップとインクリメンタル・バックアップ・スクリプト
[BOJ/C+]#2267単番号