Cod sursa(job #2791164)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 30 octombrie 2021 10:22:45
Problema Suma si numarul divizorilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
#define nmax 1000005
#define int int64_t
using namespace std;
string prob="ssnd";
ifstream in(prob+".in");
ofstream out(prob+".out");
vector<int> prime;
bool ciur[nmax];
int powow(int n,int p){
    if(p==0)return 1;
    if(p==1)return n;
    int pp=powow(n,p>>1);
    return pp*pp*powow(n,p&1);
}
void doCiur(){
    prime.push_back(2);
    for(int i=3;i<=nmax;i++){
        if(!ciur[i]){
            prime.push_back(i);
            for(int j=i;j*i<=nmax;j+=2)ciur[i*j];
        }
    }
}
vector<pair<int,int>> fact(int n){
    vector<pair<int,int>> v;
    for(auto i:prime){
        int ind=0;
        while(n%i==0){
            n/=i;
            ind++;
        }
        if(ind)v.push_back({i,ind});
    }
    if(n!=1)v.push_back({n,1});
    return v;
}
void solve(){
    int n;
    in>>n;
    vector<pair<int,int>> tmp=fact(n);
    int nr,sum;
    nr=sum=1;
    for(auto i:tmp){
        nr*=i.second+1;
        sum*=(powow(i.first,i.second+1)-1)/(i.first-1);
    }
    out<<nr<<' '<<sum<<'\n';
}
int32_t main(){
    doCiur();
    int t;
    in>>t;
    while(t--)solve();
}