Here is my code for the problem here.
#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;
const ll N = 500000;
const ll M = 10000;
// globally defining vector of primes up to N
vector<ll> primes;
// contains all primes up to N
void sieve(vector<ll> &primes) {
vector<ll> check(N + 1, 1);
check[0] = check[1] = 0;
ll size = check.size();
for (size_t i = 2; i <= (size - 1) / 2; i++) {
for (size_t j = 2; j <= (size - 1) / i; j++) {
check[i * j] = 0;
}
}
for (size_t i = 1; i < size; i++) {
if (check[i] == 1) {
primes.push_back(i);
}
}
}
// globally defining vector of perfect squares up to N
vector<ll> squares;
// globally defining vector of square roots of perfect squares up to N
vector<ll> sqroots;
// contains all squares up to N and their corresponding square roots
void square_roots(vector<ll> &squares, vector<ll> &sqroots) {
for (ll i = 0; i * i < N; i++) {
squares.push_back(i * i);
sqroots.push_back(i);
}
}
// counts number of divisors of number
ll numOfDiv(ll num, vector<ll> primes) {
ll ans = 1;
for (size_t i = 0; i < primes.size(); i++) {
if (primes[i] > num) {
break;
}
else {
if (num % primes[i] == 0) {
ll count = 0;
ll temp = num;
while (temp % primes[i] == 0) {
temp /= primes[i];
count++;
}
ans *= (1 + count);
}
else {
continue;
}
}
}
return ans;
}
// power by squaring
ll power(ll base, ll exp) {
if(exp == 0) {
return 1;
}
if(exp == 1) {
return base;
}
if(exp % 2 == 0) {
return power(base*base,exp/2);
}
if(exp % 2 == 1) {
return base * power(base*base, (exp-1)/2);
}
}
// finds square root of perfect square
ll root(ll num) {
ll i = 1;
ll count = 0;
while(num > 0) {
num -= i;
i+=2;
count++;
}
if(num == 0) {
return count;
}
return 0;
}
int main(int argc, char **argv) {
sieve(primes);
square_roots(squares, sqroots);
ll t;
cin >> t;
while (t--) {
ll num;
cin >> num;
ll d = numOfDiv(num, primes);
ll ans = 0;
ll sq = root(num);
if(squares[sq] == sqroots[num]) {
ans = power(sq,d-2);
}
else {
ans = power(num,(d-2)/2);
}
if(ans >= M) {
ll temp = ans;
ll str[4];
for(int i = 0;i < 4;i++) {
str[i] = temp%10;
temp /= 10;
}
for(int i = 3;i >= 0;i--) {
cout << str[i] << flush;
}
cout << endl;
}
else {
cout << ans << endl;
}
}
return 0;
}
Can someone help me in the output.. I'm not able to get the outputs like 0000 for 10000
asked
29 Jul '15, 19:39
4★atulshanbhag
226●2●9
accept rate:
9%