Cod sursa(job #2685250)

Utilizator SochuDarabaneanu Liviu Eugen Sochu Data 16 decembrie 2020 13:57:43
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define FILES freopen("ssnd.in" , "r" , stdin) , freopen("ssnd.out" , "w" , stdout)

using namespace std;

const int N = 1e6;

int x;
bitset < N / 2 + 10> ciur;
vector < int > pr;

void prec()
{
    int i , j;

    for(i = 1 ; ((i * i) << 1) + (i << 1) <= N ; i++)
        if(!ciur[i])
            for(j = ((i * i) << 1) + (i << 1) ; (j << 1) + 1 <= N ; j += (i << 1) + 1)
                ciur[j] = 1;

    pr.push_back(2);

    for(i = 1 ; (i << 1) + 1 <= N ; i++)
        if(ciur[i] == 0)
            pr.push_back(i * 2 + 1);
}

pair < int , int > solve(int x)
{
    int e , pw , i;
    int card = 1;
    int sum = 1;

    for(i = 0 ; i < pr.size() && pr[i] <= x ; i++)
        if(x % pr[i] == 0)
        {
           e = 0;
           pw = 1;

            while(x % pr[i] == 0)
                ++e , pw *= pr[i] , x /= pr[i];

            card *= e + 1;
            sum *= (pw * pr[i] - 1) / (pr[i] - 1);
        }

    if(x > 1)
        card *= 2 , sum *= (x * x - 1) / (x - 1);

    return {card , sum};
}

signed main()
{
	#ifndef ONLINE_JUDGE
		FastIO , FILES;
	#endif

    prec();

    int q; cin >> q;
    while(q--)
    {
        cin >> x;
        pair < int , int > s = solve(x);
        cout << s.first << ' ' << s.second << '\n';
    }

    return 0;
}