AGC047-A Integer Product
(Test/AtCoder/agc047_a.test.cpp)

• View this file on GitHub
• Last update: 2023-08-14 16:52:13+09:00
• Problem: https://atcoder.jp/contests/agc047/tasks/agc047_a

入力を全て $10^9$ して、整数の問題として考えると積が $10^18$ の倍数であるようなものの個数を数えれば良い。

これは積の素因数分解したものについて、 $2$ の指数と $5$ の指数がそれぞれ $18$ を超えていれば良い。

制約より、各要素の $2$ の指数の最大は $\log_2{10^{13}}$ 、 $5$ の指数の最大は $\log_5{10^{13}}$ とかなり小さいので、要素では無く指数の方を全探索すれば良い。

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)
• 文字列で受け取った小数を10倍しまくって整数にするやつ (Src/Utility/FloatingMarkerShift.hpp)

Code

#define PROBLEM "https://atcoder.jp/contests/agc047/tasks/agc047_a"

#include "../../Src/Template/TypeAlias.hpp"
#include "../../Src/Utility/FloatingMarkerShift.hpp"

using namespace zawa;

#include <iostream>
#include <vector>
#include <string>

int main() {
    usize N; std::cin >> N;

    constexpr usize lg2{45}, lg5{20};
    std::vector pos(lg2, std::vector<u32>(lg5));
    
    u64 ans{};
    for (u32 _{} ; _ < N ; _++) {
        std::string s; std::cin >> s;
        i64 value{FloatingMarkerShift(s, 9)};
        u32 d2{}, d5{};
        while (value % 2 == 0) {
            d2++;
            value /= 2;
        }
        while (value % 5 == 0) {
            d5++;
            value /= 5;
        }

        for (u32 i{} ; i < lg2 ; i++) for (u32 j{} ; j < lg5 ; j++) {
            if (d2 + i >= 18 and d5 + j >= 18) {
                ans += pos[i][j];
            }
        }

        pos[d2][d5]++;
    }

    std::cout << ans << std::endl;

}

#line 1 "Test/AtCoder/agc047_a.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/agc047/tasks/agc047_a"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Utility/FloatingMarkerShift.hpp"

#line 4 "Src/Utility/FloatingMarkerShift.hpp"

#include <string>
#include <cassert>
#include <limits>

namespace zawa {

i64 FloatingMarkerShift(const std::string& S, u32 shift) {
    static i64 lim10{std::numeric_limits<i64>::max() / 10};
    assert(not S.empty());
    i64 res{};
    u32 moved{};
    bool start{};
    bool minus{S[0] == '-'};
    for (u32 i{(u32)minus} ; i < S.size() ; i++) {
        if (S[i] == '.') {
            start = true;
        }
        else {
            if (start) moved++;
            assert(res < lim10);
            res = res * 10;
            assert(res < std::numeric_limits<i64>::max() - (S[i] - '0'));
            res += S[i] - '0';
        }
    }
    assert(moved <= shift);
    while (moved < shift) {
        moved++;
        assert(res < lim10);
        res = res * 10;
    }
    if (minus) res *= -1;
    return res;
}

}// namespace zawa
#line 5 "Test/AtCoder/agc047_a.test.cpp"

using namespace zawa;

#include <iostream>
#include <vector>
#line 11 "Test/AtCoder/agc047_a.test.cpp"

int main() {
    usize N; std::cin >> N;

    constexpr usize lg2{45}, lg5{20};
    std::vector pos(lg2, std::vector<u32>(lg5));
    
    u64 ans{};
    for (u32 _{} ; _ < N ; _++) {
        std::string s; std::cin >> s;
        i64 value{FloatingMarkerShift(s, 9)};
        u32 d2{}, d5{};
        while (value % 2 == 0) {
            d2++;
            value /= 2;
        }
        while (value % 5 == 0) {
            d5++;
            value /= 5;
        }

        for (u32 i{} ; i < lg2 ; i++) for (u32 j{} ; j < lg5 ; j++) {
            if (d2 + i >= 18 and d5 + j >= 18) {
                ans += pos[i][j];
            }
        }

        pos[d2][d5]++;
    }

    std::cout << ans << std::endl;

}

Back to top page