CADDi 2018 for Beginners

Submission #3864543

Source codeソースコード

#include <iostream>
#include <cstdint>
#include <vector>
#include <cmath>
#include <numeric>
struct unique_factorization_element {
    std::uint32_t prime;
    std::uint8_t pow;
};
//std::ostream& operator<< (std::ostream& os, const unique_factorization_element& e)
//{
//    os << e.prime << '^' << std::uint16_t(e.pow);
//    return os;
//}
std::vector<unique_factorization_element> unique_factorization(std::uint64_t n)
{
    std::vector<unique_factorization_element> re;
    re.reserve(20);
    const std::uint32_t lim = std::sqrt(n);
    auto calc_pow = [&n](std::uint32_t prime){
        std::uint8_t re = 0;
        while(!(n % prime)){
            n /= prime;
            ++re;
        }
        return re;
    };
    if(const auto pow = calc_pow(2)) re.push_back({std::uint32_t(2), pow});
    for(std::uint32_t i = 3; i < lim; i += 2){
        if(const auto pow = calc_pow(i)) re.push_back({i, pow});
    }
    re.shrink_to_fit();
    return re;
}
template <class Container, class T, class BinaryOperation>
T accumulate(Container&& c, T init, BinaryOperation&& binary_op)
{
    return std::accumulate(std::begin(c), std::end(c), init, std::forward<BinaryOperation>(binary_op));
}
int main()
{
    std::uint64_t N, P;
    std::cin >> N >> P;
    if(1 == N){
        std::cout << P << std::endl;
        return 0;
    } else if(1 == P){
        std::cout << '1' << std::endl;
        return 0;
    }
    const auto unique_factorization_elements = unique_factorization(P);
    const auto re = accumulate(unique_factorization_elements, std::uint64_t(1), [N](auto prev, const auto& e){
        const std::uint8_t new_pow = e.pow / N;
        for(std::uint8_t i = 0; i < new_pow; ++i) prev *= e.prime;
        return prev;
    });
    std::cout << re << std::endl;
}

Submission

Task問題 C - Product and GCD
User nameユーザ名 yumetodo
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 300
Source lengthソースコード長 1826 Byte
File nameファイル名
Exec time実行時間 6 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample1.txt,sample2.txt,sample3.txt,sample4.txt
All 300 / 300 sample1.txt,sample2.txt,sample3.txt,sample4.txt,1.txt,10.txt,11.txt,12.txt,13.txt,14.txt,15.txt,16.txt,17.txt,18.txt,19.txt,2.txt,20.txt,21.txt,22.txt,23.txt,24.txt,25.txt,26.txt,3.txt,4.txt,5.txt,6.txt,7.txt,8.txt,9.txt,sample1.txt,sample2.txt,sample3.txt,sample4.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
1.txt AC 4 ms 256 KB
10.txt AC 2 ms 256 KB
11.txt AC 2 ms 256 KB
12.txt AC 6 ms 256 KB
13.txt AC 4 ms 256 KB
14.txt AC 5 ms 256 KB
15.txt AC 3 ms 256 KB
16.txt AC 5 ms 256 KB
17.txt AC 5 ms 256 KB
18.txt AC 5 ms 256 KB
19.txt AC 6 ms 256 KB
2.txt AC 4 ms 256 KB
20.txt AC 6 ms 256 KB
21.txt AC 1 ms 256 KB
22.txt AC 1 ms 256 KB
23.txt AC 1 ms 256 KB
24.txt AC 1 ms 256 KB
25.txt AC 6 ms 256 KB
26.txt AC 5 ms 256 KB
3.txt AC 5 ms 256 KB
4.txt AC 5 ms 256 KB
5.txt AC 6 ms 256 KB
6.txt AC 5 ms 256 KB
7.txt AC 6 ms 256 KB
8.txt AC 6 ms 256 KB
9.txt AC 5 ms 256 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB
sample3.txt AC 1 ms 256 KB
sample4.txt AC 6 ms 256 KB