Project Euler 题解 #16 Power digit sum

本文主要是介绍Project Euler 题解 #16 Power digit sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：Power digit sum

这个题目在于大数乘法以及减枝。

数学描述

首先有个结论，如下：

那么，N = 2¹⁰⁰⁰时，C(N)=302。

首先设计函数GetLastMDigit(int N, int M, int* A)，将2^N的后面M位输出到数组A中，

然后对数组A求和。

代码实现

//https://projecteuler.net/problem=16
//Power digit sum
#include <iostream>
#include <cmath>
#include <Windows.h>
using namespace std;
//get last M digits of 2N
void GetLastMDigit(int N, int M, int* A)
{
if (M <=0 )
{
return;
}
for (int k = 0; k < M-1; ++k)
{
A[k] = 0;
}
A[M-1] = 1;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
int remain = (A[j]<<1)%10; //余数
int carry  = (A[j]<<1)/10; //进位
if (j != 0)
{
A[j-1] += carry;
}
A[j] = remain;
}
}
return;
}
int main()
{
int N = 1000;
int M = int(N*log10(2.0)) + 1; //2N的10进制有M个数字
int* A = new int[M];
DWORD dwTime = GetTickCount();
GetLastMDigit(N, M, A);
dwTime = GetTickCount() - dwTime;
cout<<"The last "<<M<<" digits of 2^"<<N<<" is:";
int sum = 0;
for (int i = 0; i < M; ++i)
{
cout<<A[i];
sum += A[i];
}
cout<<endl;
cout<<"sum = "<<sum<<endl;
cout<<"avr = "<<1.0*sum/M<<endl;
cout<<"cost time: "<<dwTime<<"ms"<<endl;
delete[] A;
system("pause");
return 0;
}

输入：N = 1000

输出：

这篇关于Project Euler 题解 #16 Power digit sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---