Product of divisors - need help

general
, , , ,
1

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

2

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

3

@atualshanbhag, there is no need of getting outputs like 0000 for 10000. See my nave accepted solution at CodeChef: Practical coding for everyone .

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: