Pagini recente » Cod sursa (job #730468) | Cod sursa (job #2011704) | Cod sursa (job #3330563) | Cod sursa (job #1250001) | Cod sursa (job #3315993)
#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;
}