Cod sursa(job #2875415)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 21 martie 2022 17:02:06
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define SQR 1000000
#define ULL unsigned long long
#define MOD 9973

using namespace std;

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

vector<ULL> prime;
void generare() {
    bitset<SQR + 1> ciur;
    ciur[0] = ciur[1] = 1;
    for (ULL d = 4; d <= SQR; d += 2)
        ciur[d] = 1;
    for (ULL i = 3; i * i <= SQR; i += 2)
        if (!ciur[i])
            for (ULL d = i * i; d <= SQR; d += 2 * i)
                ciur[d] = 1;
    for (ULL i = 2; i <= SQR; i++)
        if (!ciur[i])
            prime.push_back(i);
}

int main() {
    generare();
    int t;
    fin >> t;
    for (int i = 0; i < t; i++) {
        ULL x, nrDiv = 1, sumDiv = 1;
        fin >> x;
        if (x % 2 == 0) {
            ULL p = 0, pw = 2;
            while (x % 2 == 0)
                p++, pw <<= 1, x /= 2;
            nrDiv *= p + 1, sumDiv *= pw - 1;
        }
        for (auto &prim: prime) {
            if (prim * prim > x)
                break;
            else if (x % prim)
                continue;
            ULL p = 0, pw = prim;
            while (x % prim == 0)
                p++, pw *= prim, x /= prim;
            nrDiv *= p + 1, sumDiv *= (pw - 1) / (prim - 1);
        }
        if (x > 1)
            nrDiv *= 2, sumDiv *= (x * x - 1) / (x - 1);
        fout << nrDiv << ' ' << sumDiv << '\n';
    }
    return 0;
}