Cod sursa(job #2951331)

Utilizator Fantastic_Mantudor voicu Fantastic_Man Data 5 decembrie 2022 23:59:11
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>

using namespace std;
const int radical = 1e6;
int ciur[radical + 1];
vector < int > primes;

void precalc ( int n = radical ) {
    for ( int i = 2; i * i <= n; i += 1 + i % 2 )
        for ( int j = i * i; j <= n; j += i )
            ciur[j] = 1;

    for ( int i = 2; i <= n; i += 1 + i % 2 )
        if ( ciur[i] == 0 )
            primes.push_back ( i );
}

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

int main() {
    int q, divisors;
    unsigned int d;
    long long n, sum;

    precalc ();

    fin >> q;
    while ( q-- ) {
        fin >> n;
        d = 0;
        divisors = sum = 1;
        while ( d < primes.size () && primes[d] * primes[d] <= n ) {
            int cnt = 0;
            long long p = 1;
            while ( n % primes[d] == 0 ) {
                cnt++;
                p *= primes[d];
                n /= primes[d];
            }
            divisors *= ( cnt + 1 );
            sum *= ( p * primes[d] - 1 ) / ( primes[d] - 1 );
            d++;
        }
        if ( n > 1 ) {
            divisors *= 2;
            sum *= ( 1 + n );
        }

        fout << divisors << ' ' << sum << '\n';
    }

    return 0;
}