Cod sursa(job #2941560)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 17 noiembrie 2022 21:18:38
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <bitset>
#include <map>
#include <cstring>
#include <algorithm>
#define NMAX 1000003
#define MOD 98999

using namespace std;

vector<int>prime;
int ciur[NMAX];

ifstream fin("ssnd.in");
ofstream fout("ssnd.out");

int n;

void erat()
{
	ciur[0] = 1;
	ciur[1] = 1;
	for (int i = 2; i <= NMAX; i++)
	{
		if (ciur[i] == 0)
		{
			//e prim
			prime.push_back(i);
			for (int j = 2; i * j <= NMAX; j++)
			{
				ciur[i * j] = 1;
			}
		}
	}
}

void solve(long long int x)
{
	int suma = 1, nrDiv = 1;
	//n=p1^d1 * p2^d2*...
	//nrDiv= (d1+1)*(d2+1)*...
	//sumaDiv= [p1^(d1+1)-1]/(p1-1)*[p2^(d2+1)-1]/(p2-1)*...
	int k = 0;
	while (x > 1)
	{
		if (x % prime[k] == 0)
		{
			//e divizor
			int d = 0;
			long long int pr = 1;
			while (x % prime[k] == 0)
			{
				d++;
				pr *= prime[k];
				x /=  prime[k];
			}
			nrDiv *= (d + 1);
			pr=pr* prime[k] - 1;
			pr /= (prime[k] - 1);
			suma *= pr;
		}
		k++;
	}

	fout << nrDiv << " " << suma << "\n";
	
}

int main()
{
	erat();
	fin >> n;
	for (int i = 1; i <= n; i++)
	{
		long long int x;
		fin >> x;
		solve(x);
	}
	
	return 0;
}