test/Math/prime_factorize/aoj-NTL_1_A.test.cpp

• View this file on GitHub
• Last update: 2024-09-30 18:16:55+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_A

Depends on

• 素因数分解 (Math/prime_factorize.hpp)

Code

// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_A

#include "Math/prime_factorize.hpp"
#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long n;
    cin >> n;

    vector<pair<long long, long long>> factors = prime_factorize(n);

    string ans = to_string(n) + ": ";
    for (auto [factor, count] : factors)
    {
        for (int i = 0; i < count; i++)
        {
            ans += to_string(factor) + " ";
        }
    }
    ans.pop_back();
    cout << ans << endl;

    return 0;
}

#line 1 "test/Math/prime_factorize/aoj-NTL_1_A.test.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_A

#line 1 "Math/prime_factorize.hpp"
#include <bits/stdc++.h>
using namespace std;

vector<pair<long long, long long>> prime_factorize(long long N)
{
    assert(0 < N);

    long long tempN = N;
    vector<pair<long long, long long>> dst;
    for (long long i = 2; i * i <= tempN; i++)
    {
        if (N % i == 0)
        {
            dst.push_back(make_pair(i, 0));
            while (N % i == 0)
            {
                dst.back().second++;
                N /= i;
            }
        }
    }
    if (N != 1)
        dst.push_back(make_pair(N, 1));
    return dst;
}
#line 5 "test/Math/prime_factorize/aoj-NTL_1_A.test.cpp"

using namespace std;

int main()
{
    long long n;
    cin >> n;

    vector<pair<long long, long long>> factors = prime_factorize(n);

    string ans = to_string(n) + ": ";
    for (auto [factor, count] : factors)
    {
        for (int i = 0; i < count; i++)
        {
            ans += to_string(factor) + " ";
        }
    }
    ans.pop_back();
    cout << ans << endl;

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_small_00.in	AC	5 ms	3 MB
g++	00_small_01.in	AC	5 ms	3 MB
g++	00_small_02.in	AC	4 ms	3 MB
g++	00_small_03.in	AC	4 ms	3 MB
g++	01_medium_00.in	AC	4 ms	3 MB
g++	01_medium_01.in	AC	4 ms	3 MB
g++	01_medium_02.in	AC	4 ms	3 MB
g++	01_medium_03.in	AC	4 ms	3 MB
g++	01_medium_04.in	AC	4 ms	3 MB
g++	01_medium_05.in	AC	4 ms	3 MB
g++	02_large_00.in	AC	4 ms	3 MB
g++	02_large_01.in	AC	4 ms	3 MB
g++	02_large_02.in	AC	4 ms	3 MB
g++	02_large_03.in	AC	4 ms	3 MB
g++	02_large_04.in	AC	5 ms	3 MB
g++	02_large_05.in	AC	4 ms	3 MB
g++	02_large_06.in	AC	4 ms	3 MB
g++	02_large_07.in	AC	4 ms	3 MB
g++	03_critical_00.in	AC	4 ms	3 MB
g++	03_critical_01.in	AC	4 ms	3 MB
g++	03_critical_02.in	AC	4 ms	3 MB
g++	03_critical_03.in	AC	4 ms	3 MB
g++	03_critical_04.in	AC	5 ms	3 MB
g++	03_critical_05.in	AC	4 ms	3 MB

Back to top page