题目56：对于形如a的b次方的数字，找出最大的各位和
Powerful digit sum
A googolis a massive number: one followed by one-hundred zeros;is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
Considering natural numbers of the form, , where a, b < 100, what is the maximum digital sum?
题目：
一个 googol 是一个巨大的数字：1 后面跟着 100 个 0；几乎是不可想象的大：1 后面跟着 200 个 0。它们虽然很大，但是它们的各位数之和却只有 1。
考虑形如的数, 其中 a, b < 100，最大的各位和是多少？
最大的是99的95次方 各位数的和是972
int getResult(string &str)
{
//将str各位加起来
int re=0;
for (int n =0;n<str.size();n++)
re+=str-'0';
return re;
}
int main()
{
int max=0;
//记录下指数和底数
int zhi,di;
for (int z=2;z<=100;z++)
{
for (int k=2;k<=100;k++)
{
//底数是z指数是k
char buf;
itoa(z,buf,10);
strcat(buf,".0");
string result;
result = BigNum_factorial(buf,k); //大数幂
int n=getResult(result);
if(n>max)
{
zhi=k;
di=z;
max=n;
}
}
}
std::cout<<max<<endl<<di<<endl<<zhi<<endl;
return 0;
} 最大各位和是99的95次方得到的972
'''求a**b 的各位和最大值'''
maxi,maxa,maxb = 0,0,0
for a in range(99,1,-1):
for b in range(99,1,-1):
summ = 0
test = str(a**b)
for each in test:
summ += int(each)
if maxi < summ:
maxi,maxa,maxb = summ,a,b
print ('最大各位和是%d的%d次方得到的%d' % (maxa,maxb,maxi)) def Figure(a,b):
temp = a**b
count = 0
for each in str(temp):
count +=int(each)
return count
temp = 0
for i in range(1,100):
for j in range(1,100):
sum1 = Figure(i,j)
if sum1 > temp:
temp = sum1
print(temp)
结果：972 # encoding:utf-8
# a,b<100,计算a**b各位数之和最大的
from time import time
def euler056(N=1000000):
maxsum = 0
a, b = 0, 0
for i in range(1, 100):
for j in range(1, 100):
t = sum(int(x) for x in str(i ** j))
if t > maxsum:
maxsum = t
a, b = i, j
print(maxsum, a, b)
if __name__ == '__main__':
start = time()
euler056()
print('cost %.6f sec' % (time() - start))
本帖最后由 飘飞的白杨 于 2017-1-23 16:28 编辑
y = 0
for i in range(1,101):
for j in range(1,101):
x = sum()
y = max(x, y)
print(y) 本帖最后由 渡风 于 2017-6-18 11:53 编辑
在此吐槽MATLAB vpa的大数计算精度。算法没错。结果错了
此代码使用matlab和Python编程
Problem56所用时间为： 1.1116秒
Problem56的答案为： 972
% 最后编辑时间：17-06-18 12：15
% 0 <a,b<100 a^b 所有位数相加起来最大的那个数是？
% 解决要点，使用Python 和 MATLAB 联合编程
% Problem56所用时间为： 2.2817秒
% Problem56的答案为： 972
function Output = Problem56()
tic
Output = 0;
bottom = 0;
power = 0;
for a = 99:-1:1
for b = 99:-1:1
Score = py.Fun56.PowTotal(int32(a),int32(b));%调用Python函数
if Score > Output
Output = Score ;
disp(Output)
bottom = a;
power = b;
end
end
end
disp(bottom)
disp(power)
toc
disp('此代码使用matlab和Python编程')
disp(['Problem56所用时间为： ',num2str(toc),'秒'])
disp(['Problem56的答案为： ',char(Output)])
end
Python 文件
#输入a , b 判断 a** b的所有位数的和
def PowTotal(a,b):
Num = str(a**b)
Vec =
Sum = sum(Vec)
return Sum
#end
用的matlab计算
结果是
972
时间已过 4.927415 秒。
>> 972
def digital_sum(num):
sum = 0
for each in str(num):
sum += int(each)
return sum
sum = 1
for i in range(1, 100):
for j in range(1,100):
if digital_sum(pow(i, j)) > sum:
sum = digital_sum(pow(i, j))
print(sum)
最大a的b次方的数字各位和是：972
用时：0.4212027 秒import time
result = []
for a in range(2, 100):
for b in range(1, 100):
result.append(sum())
print("最大a的b次方的数字各位和是：{}\n用时：{} 秒".format(max(result), time.process_time())) 本帖最后由 永恒的蓝色梦想 于 2020-8-19 11:02 编辑
print(max(sum(map(int, str(a ** b))) for a in range(100) for b in range(100))) 972
Process returned 0 (0x0) execution time : 0.942 s
Press any key to continue.
高精度乘法
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int M = 100;
int pw;
void ini_pw(){
memset(pw,0,sizeof(pw));
pw = 1;
}
int mult(int x){
for (int i = 0;i < 200;i++){
pw *= x;
}
for (int i = 0;i < 200;i++){
pw += pw / 10;
pw %= 10;
}
int res = 0;
for (int i = 0;i < 200;i++){
res += pw;
}
return res;
}
int main(){
int ans = 0;
for (int a = 2;a < M;a++){
for (int b = 2;b < M;b++){
ini_pw();
for (int i = 0;i < b;i++){
ans = max(mult(a),ans);
}
}
}
cout << ans << endl;
return 0;
}
99的95次方最大，各位和为972def he(n):
return sum(int(i) for i in str(n))
max1 = 0
for a in range(1,100):
for b in range(1,100):
if he(a**b) > max1:
a1 = a
b1 = b
max1 = he(a**b)
print('%d的%d次方最大，各位和为%d' % (a1,b1,max1))
直接调用大数库mpir.
/*
欧拉问题56
答案：972
耗时：0.005703秒（单核）
0.001556秒（6核）
*/
#include <cstdio>
#include <mpir.h>
#include <omp.h>
#include <cstring>
int main(void)
{
int k = omp_get_max_threads();
mpz_t* mb = new mpz_t;
int nMSum = 0;
#pragma omp parallel reduction(max:nMSum) shared(mb)
{
int k = omp_get_thread_num();
mpz_init(mb);
#pragma omp for collapse(2)
for (int b = 2; b < 100; ++b)
{
for (int a = 2; a < 100; ++a)
{
int p = omp_get_thread_num();
mpz_ui_pow_ui(mb, b, a);
char str;
memset(str, 0, sizeof(str));
mpz_get_str(str, 10, mb);
int lSum = 0;
for (int i = 0; i < (int)strlen(str); ++i)
lSum += int(str - 48);
nMSum = (nMSum > lSum) ? nMSum : lSum;
}
}
mpz_clear(mb);
}
delete[] mb;
printf_s("%d\n", nMSum);
return 0;
}
use rayon::prelude::*;
use num::bigint::ToBigUint;
use num::bigint::BigUint;
use std::time::Instant;
fn main() {
let now = Instant::now();
let num: u32 = (1..101u32)
.into_par_iter()
.map(|x| {
let a = x.to_biguint().unwrap();
(1..101u32)
.into_par_iter()
.map(|b| s(a.pow(b)))
.max()
.unwrap()
})
.max()
.unwrap();
println!("cost {}ms.", now.elapsed().as_millis());
println!("{:?}", num)
}
fn s(num: BigUint) -> u32 {
num
.to_string()
.bytes()
.map(|x| (x - 48) as u32)
.sum()
}
cost 4ms.
972
页:
[1]