Cod sursa(job #3361783)

Utilizator realflaemStefan Andrei realflaem Data 28 iulie 2026 14:15:37
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> factorize(int x, const vector<int>& spf)
{
    vector<pair<int, int>> factors;

    while (x > 1)
    {
        int p = spf[x];
        int exponent = 0;

        while (x % p == 0)
        {
            x /= p;
            ++exponent;
        }

        factors.push_back({p, exponent});
    }

    return factors;
}
int MAX_N = 1000005;
int main()
{
    ifstream fin("ssnd.in");
    ofstream fout("ssnd.out");
    int N;
    fin>>N;
    vector<int> spf(MAX_N + 1);

    for (int p = 2; p <= MAX_N; ++p)
    {
        if (spf[p] == 0)
        {
            spf[p] = p;

            if (1LL * p * p <= MAX_N)
            {
                for (long long multiple = 1LL * p * p; multiple <= MAX_N; multiple += p)
                {
                    if (spf[multiple] == 0)
                    {
                        spf[multiple] = p;
                    }
                }
            }
        }
    }

    while(N--)
    {
        int t;
        fin>>t;
        int nd = 1, sd = 1;
        auto divizori = factorize(t, spf);
        for (auto div : divizori)
        {
            nd *= div.second + 1;

            long long sumaFactor = 1;
            long long putere = 1;

            for (int i = 1; i <= div.second; i++)
            {
                putere *= div.first;
                sumaFactor += putere;
            }

            sd *= sumaFactor;
        }
        fout<<nd<<" "<<sd<<endl;
    }

    return 0;
}