Pagini recente » Cod sursa (job #983479) | Profil Halatse10b | Cod sursa (job #1378907)
#include <stdio.h>
#define PMAX 1000000
#define PN_MAX 100000
#define MOD 9973
char ciur[PMAX + 1];
long long compact[PN_MAX], sp;
void Erathostenes()
{
for (int i = 2; i <= PMAX; ++i) {
if (!ciur[i]) {
for (int j = 2 * i; j <+ PMAX; j += i) {
ciur[j] = 1;
}
}
}
}
void MakeCompact()
{
for (int i = 2; i <= PMAX; ++i) {
if (!ciur[i]) {
compact[++sp] = i;
}
}
}
int pwr(int a, int b, int m)
{
if (b) {
int par = pwr(a, b / 2, m);
par = (par * par) % m;
return b % 2 ? (par * a) % m : par;
} else {
return 1;
}
}
int main()
{
FILE *fin, *fout;
fin = fopen("ssnd.in", "r");
fout = fopen("ssnd.out", "w");
Erathostenes();
MakeCompact();
int t;
fscanf(fin, "%d", &t);
int i;
for (i = 0; i < t; ++i) {
long long n;
fscanf(fin, "%lld", &n);
long long numdiv = 1, sumdiv = 1, p = 1;
while (p <= sp && compact[p]*compact[p] <= n) {
long long alpha = 0;
while (n % compact[p] == 0) {
n /= compact[p];
++alpha;
}
if (alpha) {
numdiv = (numdiv * (alpha + 1)) % MOD;
sumdiv = (sumdiv * (pwr(compact[p] % MOD, alpha + 1, MOD) + MOD - 1) * pwr(compact[p] - 1, MOD - 2, MOD)) % MOD;
}
++p;
}
if (n > 1) {
numdiv = (numdiv * 2) % MOD;
sumdiv = (sumdiv * ((n + 1) % MOD)) % MOD;
}
fprintf(fout, "%lld %lld\n", numdiv, sumdiv);
}
fclose(fin);
fclose(fout);
return 0;
}