Cod sursa(job #2831190)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 10 ianuarie 2022 22:03:17
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <bitset>
#include <vector>
#define LL long long

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

const LL LIM = 1e6;
std::bitset <LIM+5> frq;
std::vector <LL> p;

LL gauss(LL k){
    return k * (k + 1) / 2;
}

LL sumdiv(LL number){
    LL result = 0;

    for(LL i=1; i<=number/i; i++){
        result += i * (number / i - i + 1);
        result += gauss(number/i) - gauss(i);
    }

    return result;
}

signed main (){
    frq[0] = frq[1] = true;
    for(LL i=4; i<=LIM; i+=2)
        frq[i] = true;
    for(LL i=3; i<=LIM/i; i+=2)
        for(LL j=i*i; j<=LIM; j+=i)
            frq[j] = true;

    p.push_back(2);
    for(LL i=3; i<=LIM; i+=2)
        if(frq[i] != true)
            p.push_back(i);

    LL q, x;
    fin>>q;
    while(q--){
        fin>>x;

        LL div=1, sol=sumdiv(x) - sumdiv(x-1);
        for(LL i=0; i < (LL)p.size() && p[i] <= x / p[i]; i++){
            LL pow = 0;
            while(x % p[i] == 0){
                pow++;
                x /= p[i];
            }
            div *= (pow+1);
        }
        if(x != 1)
            div *= 2;

        fout<<div<<' '<<sol<<'\n';
    }
    return 0;
}