Product of divisors - need help

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

refer this solution, this is coded in java. But you will be able to understand the logic.
https://www.codechef.com/viewsolution/8978652

@atualshanbhag, there is no need of getting outputs like 0000 for 10000. See my nave accepted solution at https://www.codechef.com/viewsolution/7269691 .

For getting formatted output like 03, 0003 instead of 3 etc. you can do it in 3 ways in c++

  1. Use if-else, switch-case statements, with condition regarding the length of output.
  2. Better method, use scanf and printf in your code. For formatted output you can use %0xd where x can be any digit 1 to 9 indicating the length of the number be printted, if the word length is less it is padded with zeros. For example printf("%04d", n) will give output as 0301 if n=301 and 1245 when n=1245 and 0003 when n=3.
  3. Using cin and cout, use setprecision and setfixed flags in iomanip library. If do not know much about it, but you can google it to get further help.

Happy coding :slight_smile: