Cod sursa(job #3315993)

Utilizator Vlad_smek2307Hagimasuri Vlad Dimitri Vlad_smek2307 Data 16 octombrie 2025 18:04:30
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
std::ifstream fin("ssnd.in");
std::ofstream fout("ssnd.out");

// This outputs every prime number until a given limit
void sieve_of_E_prime(std::vector<int>& F, long limit){
    std::vector<int> P(limit+1,1);
    P[0] = P[1] = false;
    for (int p=2;p<sqrt(limit)+1; p++){
        if (P[p]) // checking if it is a "prime" number
            for (int multiple=p*p; multiple<limit+1; multiple+=p) // de-flagging all multiples of p starting from p*p
                P[multiple] = false;
    }
    for (int i=0;i<limit+1;i++)
        if (P[i])
            F.push_back(i);
}

// Returns the prime factors of x
void prime_factors(long x, std::vector<std::pair<int,int>>& decomposition){
    std::vector<int> factors;
    sieve_of_E_prime(factors,x);
    for (const auto& f: factors){// For every prime number from the decomposition
        // The pair contains the prime number and its power
        if (x % f == 0)
            decomposition.push_back({f,0});
        while (x % f == 0){
            decomposition.back().second++;// Incrementing the power of the last prime in
            x /= f;
        }
    }
}

long div_no(std::vector<std::pair<int,int>>& decomposition){
    long divno = 1;
    for (const auto& p: decomposition)
        divno *= p.second + 1;
    return divno;
}

long div_sum(std::vector<std::pair<int,int>>& decomposition){
    long divsum = 1;
    for (const auto& p: decomposition)
        // Geometrical Progression formula
        divsum *= ((pow(p.first, p.second+1) - 1)/(p.first - 1));
    return divsum;
}

int main(){
    int t; fin >> t;
    for (int i=0;i<t;i++){
        long n; fin >> n;
        if (n == 1){fout << 1 << " " << 1 << '\n'; continue;}
        // Getting prime factors and their power
        std::vector<std::pair<int,int>> decomp;
        prime_factors(n, decomp);
        // Calculating the number of divisors using the formula:
        // d(n) = (a1 + 1)*(a2 + 1)*(a3 + 1)*...*(ak + 1), where a is the power of the k prime factor
        long divno = div_no(decomp); fout << divno << " ";
        // Calculating the sum of the divisors
        long divsum = div_sum(decomp); fout << divsum  << '\n';
    }

    return 0;
}