# Cod sursa(job #631369)

Utilizator Data 7 noiembrie 2011 21:24:23 Suma si numarul divizorilor 70 cpp done Arhiva educationala 2.49 kb
``````#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cfloat>
#include <numeric>

using namespace std;

const int    oo  = 0x3f3f3f3f;
const double eps = 1e-9;

typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;

#define sz(c) int ((c).size())
#define all(c) (c).begin(), (c).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define FORIT(i, c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define mp make_pair
#define pb push_back
#define MAX_N 1 << 20
#define MOD 9973

int p[MAX_N];
vi primes;

void sieve () {
for (int i = 2; i * i < MAX_N; ++i) if (!p[i])
for (int k = i * i; k < MAX_N; k += i) p[k] = 1;
FOR (i, 2, MAX_N) if (!p[i]) primes.pb(i);
}

ll exp_mod(ll a, ll x, ll m) {
if (x == 0) return 1;
ll res = exp_mod(a, x/2, m);
res = (res * res) % m;
return (x % 2) ? (res * a) % m : res;
}

ll inverse(ll a, ll p) {
return exp_mod(a, p-2, p);
}

vector<pii> factorize (ll n) {
vector<pii> res;

for (int i = 0; primes[i]*primes[i] <= n; ++i) {
if (n % primes[i]) continue;

res.pb(mp(primes[i], 0));
while (n % primes[i] == 0) {
res.back().second++;
n /= primes[i];
}
}
if (n > 1) res.pb(mp(n, 1));
return res;
}

ll factor (ll p, ll d) {
ll u = p;
FOR (i, 0, d) {
u *= p;
u %= MOD;
}

u = (u - 1 + MOD) % MOD;

return u * inverse(p - 1, MOD);
}

int main () {
freopen ("ssnd.in", "r", stdin);
freopen ("ssnd.out", "w", stdout);

sieve ();

int tests;
scanf ("%d", &tests);
while (tests--) {
ll n;

scanf ("%lld", &n);
vector<pii> f = factorize(n);

ll nums = 1;
FOR (i, 0, sz(f)) {
nums *= (f[i].second + 1);
nums %= MOD;
}

ll sums = 1;
FOR (i, 0, sz(f)) {
sums *= factor(f[i].first, f[i].second);
sums %= MOD;
}

printf ("%lld %lld\n", (nums + MOD) % MOD, (sums + MOD) % MOD);
}

return 0;
}
``````