Cod sursa(job #2628569)

Utilizator etohirseCristi Cretu etohirse Data 16 iunie 2020 13:46:15
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;

#define ll unsigned long long 
#define fisier 1
const int mxA = 1e6;
const int MOD = 1e9 + 7;
int lpf[mxA + 1];
vector < int> pfs;
ll lgput(ll x, ll p) {
	ll rez = 1;
	x %= MOD;
	for(; p; p >>= 1) {
		if(p & 1) {
			rez *= x;
			rez %= MOD;
		}
		x *= x;
		x %= MOD;
	}
	return rez;
}

int32_t main(){
	#ifdef fisier
        ifstream cin("ssnd.in");
        ofstream cout("ssnd.out");
    #endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	for (int i = 2; i <= mxA; ++i){
		if (!lpf[i]){
			pfs.push_back(i);
			lpf[i] = i;
		}
		for (unsigned j = 0; j < pfs.size() && pfs[j] <= lpf[i] && i * pfs[j] <= mxA; ++j)
			lpf[i*pfs[j]] = pfs[j];
	}
	int t;
	cin >> t;
	while (t--){
		map < int, int > mp;
		ll x;
		cin >> x;
		int y = 1;
		while (x > 1){
			mp[lpf[x]]++;
			x/=lpf[x];
			y *= lpf[x];
		}
		ll exp = 1, s = 1;
		for (auto p : mp){
			exp *= (p.second + 1);
			s  *= (lgput(p.first,p.second+1) - 1) / (p.first - 1);
		}
		cout << exp << " " << s << "\n";
	}
}