# Cod sursa(job #481606)

Utilizator Data 31 august 2010 22:08:26 Suma si numarul divizorilor 100 cpp done Arhiva educationala 1.01 kb
``````#include <fstream>
#include <bitset>

using namespace std;

const int MAX_N = 1000005;
const int MOD = 9973;

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

long long N;
int T, K, P[MAX_N];
bitset <MAX_N> viz;

void ciur() {
for(int i = 2; i < MAX_N; ++i) {
if(viz[i] == 0) {
P[++K] = i;

for(int j = i+i; j < MAX_N; j += i) {
viz[j] = 1;
}
}
}
}

inline int pow(int x, int p) {
int rez = 1;
x %= MOD;

for(; p; p >>= 1) {
if(p & 1) {
rez *= x;
rez %= MOD;
}

x *= x;
x %= MOD;
}

return rez;
}

void solve() {
fin >> N;

int	nd = 1, sd = 1;

for(int i = 1; i <= K && 1LL * P[i] * P[i] <= N; ++i) {
if(N % P[i]) continue;
int p = 0;

while(N % P[i] == 0) {
N /= P[i];
++p;
}

nd *= (p+1);

int p1 = (pow(P[i], p+1) - 1) % MOD;
int p2 = pow(P[i]-1, MOD-2) % MOD;

sd = (((sd * p1) % MOD) * p2) % MOD;
}

if(N > 1) {
nd *= 2;
sd = (1LL*sd*(N+1) % MOD);
}

fout << nd << " " << sd << "\n";
}

int main() {
ciur();

for(fin >> T; T; --T)
solve();
}
``````