Cod sursa(job #2417482)

Utilizator vladm98Munteanu Vlad vladm98 Data 29 aprilie 2019 22:34:39
Problema Suma si numarul divizorilor Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;

vector <int> ciur;
bitset<1000001> frequence;

void buildCiur () {
    for (int i = 2; i <= 1000000; ++i) {
        if (frequence[i]) {
            continue;
        }
        ciur.push_back(i);
        for (int j = i + i; j <= 1000000; j += i) {
            frequence[j] = 1;
        }
    }
}

int main() {
    ifstream fin ("ssnd.in");
    ofstream fout ("ssnd.out");
//    ifstream fin ("input");
//    ofstream fout ("output");
    buildCiur();
    int n;
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        long long x;
        long long sum = 1;
        int divisors = 1;
        fin >> x;
        for (auto prime : ciur) {
            if (1LL * prime * prime > x) {
                break;
            }
            long long power = 1;
            int exponent = 0;
            while (x % prime == 0) {
                x /= prime;
                power *= prime;
                exponent += 1;
            }
            divisors *= (1 + exponent);
            sum *= (power * prime - 1) / (prime - 1);
        }
        if (x > 1) {
            divisors <<= 1;
            sum *= (x + 1);
        }
        fout << divisors << ' ' << sum % 9973 << '\n';
    }
    return 0;
}