Pagini recente » Cod sursa (job #541580) | Cod sursa (job #49219) | Cod sursa (job #659254) | Cod sursa (job #212522) | Cod sursa (job #3124615)
#include <fstream>
#include <vector>
#define int long long
using namespace std;
ifstream cin("ssnd.in");
ofstream cout("ssnd.out");
const int VALMAX = 1e6;
const int MOD = 9973;
int t;
char c[VALMAX + 1];
vector<int> prime;
int SubstractMOD(int a, int b)
{
int ans = ((a % MOD) - (b % MOD)) % MOD;
if(ans < 0)
ans += MOD;
return ans;
}
int ProductMOD(int a, int b)
{
return ((a % MOD) * (b % MOD)) % MOD;
}
int Power(int a, int b)
{
int rez = 1;
while(b)
{
if(b % 2 == 1)
rez = (rez * a) % MOD;
a = (a * a) % MOD;
b /= 2;
}
return rez;
}
void Eratostene()
{
c[0] = c[1] = 1;
for(int i = 2; i * i <= VALMAX; i++)
if(!c[i])
for(int j = 2; i * j <= VALMAX; j++)
c[i * j] = 1;
for(int i = 2; i <= VALMAX; i++)
if(!c[i])
prime.push_back(i);
}
void test_case()
{
int n;
cin >> n;
int ind = 0;
int d = prime[ind];
int nrdiv = 1;
int sumdiv = 1;
while(n > 1)
{
int p = 0;
while(n % d == 0)
n /= d, p++;
if(p)
{
nrdiv *= (p + 1);
sumdiv = ProductMOD(sumdiv, ProductMOD(SubstractMOD(Power(d, p + 1), 1), Power(d - 1, MOD - 2)));
}
d = prime[++ind];
if(d * d > n)
d = n;
}
cout << nrdiv << ' ' << sumdiv << '\n';
}
signed main()
{
Eratostene();
cin >> t;
while(t--)
test_case();
return 0;
}