Widzę że się poddałeś, więc co mi tam, ja nic nie tracę, masz gotowca (znalezione gdzieś na dysku, nie pisane teraz).
Jakby co to nie mam pojęcia dlaczego, kiedy, jak, dla kogo i po co to kiedyś pisałem, ale prawdopodobnie to robiłem pijany o 4 w nocy patrząc na kod który jest lekkim WTF (szczególnie define i komentarz na początku - tak było w oryginale O_o)...
Tak czy inaczej, być może Ci w czymś pomoże, chociaż wątpię żeby otrzymanie gotowego kodu w czymkolwiek pomagało...
Kopiuj
using namespace std;
#define private public
#include <iostream>
#include <stdint.h>
typedef uint32_t chunk_t;
typedef uint64_t chunk_dbl_t;
class bigNum
{
private:
static const chunk_t THRESHOLD = 1000;
chunk_t *chunks;
size_t used_chunks;
size_t allocated_chunks;
public:
bigNum(int);
bigNum(chunk_t *, int);
bigNum operator*(const bigNum &);
size_t estimateProductSize(const bigNum &, const bigNum &);
};
bigNum::bigNum(int value)
{
this->chunks = new chunk_t[1];
this->chunks[0] = value;
this->used_chunks = 1;
this->allocated_chunks = 1;
}
bigNum::bigNum(chunk_t *chunks, int numChunks)
{
this->chunks = chunks;
this->used_chunks = numChunks;
this->allocated_chunks = numChunks;
while(!this->chunks[this->used_chunks - 1])
{ this->used_chunks--; }
}
size_t bigNum::estimateProductSize(const bigNum &n1, const bigNum &n2)
{
return n1.used_chunks + n2.used_chunks;
}
bigNum bigNum::operator*(const bigNum &other)
{
size_t newSize = bigNum::estimateProductSize(*this, other);
chunk_t *newChunks = new chunk_t[newSize];
memset(newChunks, 0, newSize * sizeof(chunk_t));
for(size_t i = 0; i < this->used_chunks; i++)
{
chunk_dbl_t carry = 0;
for(size_t j = 0; j < other.used_chunks; j++)
{
chunk_dbl_t product = this->chunks[i] * other.chunks[j];
product += newChunks[i + j] + carry;
newChunks[i + j] = product % THRESHOLD;
carry = product / THRESHOLD;
}
newChunks[i + other.used_chunks] = carry;
}
return bigNum(newChunks, newSize);
}
bigNum naivePow(int num, uint32_t pow)
{
bigNum value = num;
bigNum result = 1;
for(uint32_t i = 0; i < pow; i++)
{
result = result * value;
}
return result;
}
bigNum basicFastPow(bigNum num, uint32_t pow)
{
if (pow == 0) { return 1; }
if (pow % 2 == 0)
{
bigNum tmp = basicFastPow(num, pow / 2);
return tmp * tmp;
}
else
{
bigNum tmp = basicFastPow(num, (pow - 1) / 2);
return num * tmp * tmp;
}
}
int countOnes(const bigNum &n)
{
int ct = 0;
for(size_t i = 0; i < n.used_chunks; i++)
{
chunk_t chk = n.chunks[i];
while(chk)
{
if (chk % 10 == 1) { ct++; }
chk /= 10;
}
}
return ct;
}
int main()
{
int n;
cin >> n;
bigNum n1 = basicFastPow(11, n);
cout << countOnes(n1) << endl;
}
