Project Euler Problem 16

Cre: stephan-brumme

Lưu ý:

for (auto& i : power) : Access thẳng vào giá trị của power vector nên nếu i thay đổi thì vector chứa i đã thay đổi luôn

cache.push_back(power); Đẩy power vector vào trong vector cache, còn đẩy giá trị carry vào trong power

Mô phỏng phép nhân 2 bằng tay

Ví dụ: 16 x 2 =32 : 16 được lưu trong vector power và cho chạy i = 6 thì 6x2=12, lúc này i =2 và carry =1, tiếp theo i = 1 thì i=1*2+1 =3

Lúc này 32 được lưu vào power và power được đẩy vào cache ttheo thứ tự ngược tứ là 2.Lần lặp tiếp theo tương tự 32*2 thì i lại = bằng 2 sau đó i =3 ( lưu trong vector power là 23)

```

#include <vector>
	#include <iostream>
	// store single digits in an array, lowest digit come first
	typedef std::vector<unsigned int> Digits;
	int main()
	{
	// memoize powers of two
	std::vector<Digits> cache;
	// add 2^0 = 1
	cache.push_back({ 1 });
	unsigned int tests;
	std::cin >> tests;
	while (tests--)
	{
	unsigned int exponent;
	std::cin >> exponent;
	// and compute the remaining exponents
	for (unsigned int current = cache.size(); current <= exponent; current++)
	{
	auto power = cache.back();
	unsigned int carry = 0;
	for (auto& i : power)
	{
	// times two ...
	i = 2 * i + carry;
	// handle overflow
	if (i >= 10)
	{
	i -= 10;
	carry = 1;
	}
	else
	{
	carry = 0;
	}
	}
	// still some carry left ?
	if (carry != 0)
	power.push_back(carry);
	// memoize result
	cache.push_back(power);
	}
	// sum of all digits
	unsigned int sum = 0;
	for (auto i : cache[exponent])
	sum += i;
	std::cout << sum << std::endl;
	}
	return 0;
	}

 ```