Cod sursa(job #2017243)

Utilizator Alex18maiAlex Enache Alex18mai Data 31 august 2017 17:07:05
Problema Suma si numarul divizorilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e6 + 15;

bool ciur [MAX + 100];
vector <int> elemciur;
vector <pair<long long , int>> fact;

void CIUR (){
    ciur[1] = 1;
    for (int i=2; i<= MAX; i++){
        if (ciur[i] == 0){
            elemciur.push_back(i);
            for (int j=i * 2; j<=MAX; j+= i){
                ciur[j] = 1;
            }
        }
    }
}

int main() {
    freopen ("ssnd.in" , "r" , stdin);
    freopen ("ssnd.out" , "w" , stdout);

    CIUR();
    int t;
    cin>>t;
    while(t--){
        fact.clear();
        long long n;
        cin>>n;
        int cont = -1;
        for (auto x : elemciur){
            //cout<<x<<" ";
            if (x * x > n){
                break;
            }
            if (n % x == 0){
                //cout<<"gasesc "<<x<<'\n';
                fact.push_back(make_pair(x , 0));
                cont++;
            }
            while ( n % x == 0){
                //cout<<"adaug "<<x<<'\n';
                fact[cont].second++;
                n /= x;
            }
        }
        if (n != 1){
            fact.push_back(make_pair(n , 1));
            cont++;
        }
        long long nrdiv = 1;
        long long sumadiv = 1;
        for (auto x : fact){
            sumadiv *= 1LL * (pow(x.first , x.second + 1) - 1) / (x.first - 1);
            nrdiv *= x.second + 1;
        }
        cout<<nrdiv<<" "<<sumadiv<<'\n';
    }
    return 0;
}