问题描述
我工作的锻炼，似乎被卡住多与如何在数学上解决这个问题，而不是语法。
的思想很简单，当一个数是比较小的。如果有一个基和电源，该程序要总结的结果的数字。让我们用一个例子来解释我想做的事情。
2的基础和动力8 给定，因此 2 ^ 8 = 256 则程序要总结的答案位，因此 2 + 5 + 6 = 13 并且是整点，找到的幂碱的结果的数字的总和。
现在，这是一个简单的例子，如果我移动到一个可笑的庞大的数字，比方说2 ^ 1000，这几乎是不可能的，只是扔进任何东西，我都试过，因为我们失去了precision因为结果是巨大的，被截断。答案一定是precise。
我想也许有一种数学方法来做到这一点不同，在某种程度上将其分解成更小的chuncks但我真的想不出比其他任何关系的：
2 ^ 1000 = 2 ^ 500 * 2 ^ 500
1000日志（2）=日志（ANS）
无论哪种方式，这不会给我任何地方在附近的结果，我可以开始总结数字。
我希望我解释清楚了。
对于什么是值得的，我使用C ++（给了LUA了一枪太），也许我可以用一个库，但这个数字将有302位的地方，我应该写我的程序来处理的1000我的指数真以为我失踪了一些数学技巧在这里。
修改部分解决方案找到
我花了一点时间和Lua试图今天这个解决了，我会给它用C ++出手今晚，看看我得到不同的结果。我能找到错误的根源，但我已经找到了解决方案，适用于大多数情况下。只是没有2 ^ 1000，以及其他一些指数具有非常大的数字。
描述的解决方案工程和评论从MooseBoys。
我利用模幂的。该LUA code是如下：
- 功能用途：计算模块化指数（参见维基在评论
从MooseBoys）
-
- @参数B：基地
- @参数E：指数
- @参数M：调制
- @result C：结果
-
- 例如：2 ^ 15 = 32768
- ModPow（2,15,10）= 8
- ModPow（2,15,100）= 68
-
当地ModPow =功能（B，E，M）
本地C = 1
对于i = 1，e执行
C = C * B％M
结束
回复C
结束
- 功能用途：检查结果的唯一性，从最后一个。
- ModPow不会返回前导0，所以在壳体2 ^ 20 = 1048576
- 和结果将等于35，因为：
- ModPow（2,20,10 ^ 5）= 48576
- ModPow（2,20,10 ^ 6）= 48576
-
- 另外还有一个问题，四舍五入我的工作。当前的问题
- 有时候，结果是6.xxxxxxxxxx2e + 294
- 与领先0的结果是6.xxxxxxxxxx3e + 294
- 因此，结果没有捕获有一个前导0以来s1和s2
- 不相等
- 但是，此修复程序是给我的问题（假设模指数始终
- 长按一个数量级。10 ^（N + 1）每个周期），我认为
- 只是检查指数值是不够好
- 现在，我得到一些奇怪的结果概述打击
-
- @参数S1：从ModPow当前结果（如字符串）
- @参数S2：ModPow最后的结果（如字符串）
- 基于该号码是否有效。@result布尔要添加到的总和
本地CheckUnique =函数（S1，S2）
如果S1：找到（E）和S2：找到（E），然后--fix四舍五入？
如果（S1：分（S1：找到（E），S1：LEN（））== S2：分（S2：找到（E），S2：LEN（））），然后打印（0）返回false结束
ELSEIF（S1 = = S2），然后打印（0）返回false --fix领先0
结束
打印（S1）--test
返回true
结束
--self explanitory
当地基= 2
当地EXP = 1000
当地MOD = 10
--counters和价值持有人
当地总和= 0
当地LVAL = 0
当地VAL，丘壑= 1，'1'
当地周期= 1
--Know何时停止
当地endval =基地^ EXP
打印（endval）
而VAL〜= endval做
VAL = ModPow（基地，EXP，MOD ^周期）
瓦尔斯=的ToString（VAL）
如果（CheckUnique（丘壑，LVAL）），然后--is独特
总和=总和+ tonumber（瓦尔斯：子（1,1））--sum领先的数字
结束
LVAL =瓦尔斯
周期=周期+ 1
结束
打印（和）
问题就出结果之内。
你可以想象，打印从国防部周期的每个结果应该是这样的。
值：1048576
6
76
576
8576
48576
0
1048576
和：31
我把打印（0）在那里当检查检测前导0，否则，将c的版画价值。你可以看到，每一个数字将添加到给出正确的总和。每一个网线应包含previous线，加上新的数字，就像一个不断增长的标题基本上是这样。
不过，这个问题我解决不了，现在当我向这大一些，让我们说的解决方案，我CAM去了。 2 ^ 1000。
结果：（健康线，接近尾声）
2.6725480652012e + 288
6.2672548065201e + 289
8.6267366100831e + 290
1.8626730674387e + 291
7.186267401715e + 292
0
6.0718626734093e + 294
8.6071862673409e + 295
0
5.0860718626736e + 297
1.5086071862673e + 298
7.1508607186267e + 299
例如最后一行，是一样的，如果你列出的清单倒退的第一个数字： 7.1508607186267e + 299
7 15086071862
被激发，我找到了答案，是不正确的。我看着到线更深，发现这些不健康的行：
9.18229858679e + 069
7.5447775000848e + 070
8.8906306939456e + 069
4.1746958410049e + 072
5.0621122825342e + 073
4.1602034907325e + 074
1.9248790609684e + 075 - 没有这样的秩序454879，但有924879？
....
8.3104764719996e + 086
3.8310476472e + 087
4.6735451839797e + 088
8.0281504870817e + 089
3.0808317990698e + 090
9.0430240225156e + 091 --no这样才能938438 ...？
似乎有几个地方发生这种情况，只有在指数超过200ish ..我检查了100，这是完美的。在200注意到的错误，例如
2.9937827928353e + 018
0
2.0299378279284e + 020
2.2029937827928e + 021
7.8493010541604e + 022
5.0206666406882e + 023
0
3.384239167984e + 025
任何人有什么可能是问题的任何新的建议吗？（对不起，我的卢阿interperter可能是不同的，不知道LUA一般..我只是用一个用于游戏脚本的IDE）
好了，越来越近。我的C ++程序处理的事情一大更好，这里是code吧。仍然得到错误的答案，但至少我得到的数字相同。我似乎无法弄清楚什么是不对的了。问题是，这次军演是在网站上，我不知道正确的答案，只是我的计划是给我2 ^ 1000错误的答案。它通过其他测试情况下，我给它（那些我可以做手工，检查答案最多2 ^ 20）
的#include＆LT;的iostream＆GT;
＃包括＆LT; CMATH＆GT;
双ModPow（INT，INT，长双）;
诠释的main（）{
INT基准= 2;
INT功率= 1000;
长双MOD = 10;
长双VAL = 0;
INT I = 0;
INT总和= 0;
双ANS = POW（底座，电源）;
性病::法院＆LT;＆LT; ANS＆LT;＆LT;的std :: ENDL;
而（ANS！= VAL）{
VAL = ModPow（基地，电力，MOD）;
性病::法院＆LT;＆LT; VAL＆LT;＆LT; ;
总和+ = INT（楼（VAL /（MOD / 10）））;
MOD = MOD * 10;
我+ = 1;
如果（I％5 == 0）性病::法院＆LT;＆LT;的std :: ENDL;
}
性病::法院＆LT;＆LT;的std :: ENDL＆LT;＆LT;总之＆LT;＆LT;的std :: ENDL;
性病::法院＆LT;＆LT; I＆LT;＆LT;的std :: ENDL;
的std :: cin.ignore（）;
返回0;
}
双ModPow（INT B，INT即长双M）{
双C = 1;
的for（int i = 1; I＆LT; = E;我++）{
C = FMOD（C * B，M）;
}
返回℃;
}
在这里，我可以看到有循环仍然在奇怪的行为。从逻辑上讲，EXP应当由一个每次增加，因为我不断加入数字。我看到的行为，在E + 22，并回落至E + 21，不知道为什么。这是我的程序的完整结果（我已经做了双打长双打，并添加文件写入，但结果是一样的code以上）
6 76 376 9376 69376
69376 8.06938e + 006 6.80694e + 007 6.68069e + 008 5.66807e + 009
5.66807e + 009 2.05668e + 011 7.20567e + 012 3.72057e + 013 8.37206e + 014
6.83721e + 015 8.68372e + 016 3.86837e + 017 4.38684e + 018 2.43868e + 019
6.24387e + 020 2.62439e + 021 8.81371e + 022 7.17853e + 021 6.67056e + 024
5.66706e + 025 2.56671e + 026 6.11305e + 027 1.49872e + 026 7.84562e + 029
8.79213e + 030 5.26226e + 031 2.66375e + 032 7.26638e + 033 4.84075e + 034
3.21959e + 035 6.35788e + 036 6.73897e + 037 6.73897e + 037 6.73897e + 037
2.62589e + 038 2.98945e + 041 2.98945e + 041 6.02989e + 043 9.17698e + 044
7.16921e + 045 7.05229e + 046 6.70523e + 047 6.5113e + 048 4.65113e + 049
8.52121e + 050 3.85212e + 051 7.38521e + 052 4.19563e + 053 5.91881e + 054
4.39205e + 055 3.9345e + 056 9.04097e + 057 9.04097e + 057 3.68596e + 059
1.49612e + 060 7.7534e + 061 7.39705e + 061 4.22204e + 063 6.98596e + 063
6.92886e + 065 4.69289e + 066 8.22986e + 067 1.82299e + 068 9.1823e + 069
7.54478e + 070 1.14456e + 071 4.11446e + 072 3.62523e + 073 9.90302e + 074
1.92488e + 075 4.59175e + 076 5.88549e + 077 1.35968e + 078 6.13597e + 079
6.6136e + 080 4.66136e + 081 7.48063e + 082 6.12132e + 083 8.8392e + 084
7.86463e + 085 6.94822e + 086 6.32933e + 087 5.62433e + 088 6.56243e + 089
2.3548e + 090 5.60251e + 090 7.14338e + 091 9.90736e + 093 6.14551e + 094
5.791e + 095 2.5791e + 096 5.12015e + 097 1.81734e + 098 3.08347e + 099
4.30835e + 100 4.43083e + 101 9.44308e + 102 8.62251e + 103 4.79117e + 104
4.47912e + 105 4.70365e + 106 6.26271e + 107 9.63625e + 108 1.34535e + 109
2.5938e + 110 4.77635e + 110 7.92388e + 112 2.33449e + 113 9.38763e + 114
1.74483e + 115 4.23631e + 116 3.8324e + 117 3.10928e + 118 8.8341e + 119
9.80234e + 120 5.28235e + 121 4.52823e + 122 8.69571e + 123 7.59308e + 124
6.61087e + 123 8.34403e + 126 8.26135e + 127 3.82614e + 128 6.83699e + 128
5.48343e + 130 7.05731e + 131 2.02676e + 132 1.20268e + 133 3.72264e + 134
4.37226e + 135 5.43723e + 136 1.68563e + 137 9.63719e + 138 3.70399e + 139
1.84462e + 140 6.61036e + 141 4.66104e + 142 3.85213e + 143 2.38521e + 144
7.39926e + 145 4.95209e + 146 2.70772e + 147 1.27077e + 148 9.49987e + 149
6.39539e + 150 9.72139e + 151 5.89019e + 152 7.15679e + 153 7.15679e + 153
3.38172e + 154 5.84268e + 156 9.72579e + 157 4.87575e + 158 5.6501e + 159
1.85286e + 160 4.18529e + 161 4.60739e + 162 7.12977e + 163 5.71298e + 164
8.86201e + 165 7.8862e + 166 5.82415e + 167 4.61194e + 168 8.46119e + 169
7.95321e + 170 9.01956e + 171 7.90196e + 172 1.40488e + 173 2.38969e + 174
9.12607e + 175 8.5208e + 176 2.61635e + 177 7.26163e + 178 1.87538e + 179
6.18754e + 180 6.6906e + 181 2.05665e + 182 3.79061e + 183 4.37906e + 184
4.43791e + 185 9.87813e + 186 1.98781e + 187 7.03446e + 188 1.57091e + 189
5.7816e + 190 7.57816e + 191 2.1734e + 191 3.5815e + 193 9.77689e + 194
8.97769e + 195 1.08115e + 196 5.10812e + 197 4.6079e + 198 4.46079e + 199
5.44608e + 200 3.69583e + 201 3.36958e + 202 1.94715e + 203 9.19309e + 204
1.7556e + 205 9.45675e + 206 5.94568e + 207 6.45002e + 208 9.11561e + 209
1.17058e + 210 8.60292e + 211 7.86029e + 212 2.48236e + 213 1.2582e + 214
6.04576e + 215 9.60458e + 216 4.34447e + 217 5.43445e + 218 8.42133e + 219
9.84213e + 220 1.8562e + 221 8.38891e + 221 1.08389e + 223 7.01599e + 223
1.07016e + 225 3.10702e + 226 4.3107e + 227 1.50548e + 228 1.06711e + 229
8.65791e + 230 9.86579e + 231 8.18076e + 232 2.68057e + 232 1.85488e + 234
1.85488e + 234 2.26339e + 236 4.66336e + 237 6.27494e + 238 5.24964e + 239
3.52496e + 240 2.99353e + 240 9.96218e + 242 8.99622e + 243 4.9693e + 243
1.33007e + 245 3.78439e + 246 1.99925e + 247 8.51404e + 248 8.47445e + 249
2.95141e + 250 7.13201e + 251 1.7132e + 252 9.76862e + 253 9.36726e + 254
3.92421e + 255 6.39242e + 256 8.42555e + 256 4.87969e + 258 4.09894e + 259
2.17963e + 260 1.61217e + 261 8.27277e + 261 4.08273e + 263 4.53756e + 264
9.67271e + 265 9.67271e + 265 9.19793e + 267 1.91979e + 268 2.52109e + 267
5.12996e + 270 6.60659e + 271 9.64583e + 272 6.96458e + 273 3.07557e + 274
7.59723e + 275 4.30703e + 276 6.07449e + 277 2.87595e + 278 5.82907e + 279种
4.59589e + 279种2.07609e + 281 6.20761e + 282 9.17199e + 283 5.9172e + 284
5.9172e + 284 7.05917e + 286 6.70229e + 287 2.67023e + 288 6.26707e + 289
8.62671e + 290 1.86267e + 291 7.18627e + 292 7.18627e + 292 6.07186e + 294
8.60719e + 295 8.60719e + 295 5.08607e + 297 1.50861e + 298 7.15086e + 299
7.15086e + 299 1.07151e + 301
您想要，不直接涉及只是在做解决方案2 ** 1000 ？好了，我们可以做手工。多少位没有 2 ** 1000 有哪些？绝对至多1000。
这样：
INT sum_digits（INT E）{
的std ::矢量＆lt; INT＆GT;数字（E）;
数字[0] = 1;
INT last_digit = 1;
对于（INT功率= 0;功率P，E ++功率）{
INT携带= 0;
对于（INT IDX = 0; IDX＆LT; last_digit ++ IDX）{
INT督促=数字[IDX] * 2 +随身携带;
如果（PROD＆GT; 9）{
随身携带= 1;
PROD - = 10;
}
其他 {
随身携带= 0;
}
数字[IDX] = PROD;
}
如果（进）{
数字[last_digit ++] = 1;
}
}
//然后就总结'时间
返回的std ::累加（digits.begin（），digits.end（），0）;
}
这是pretty的快速显然是正确的。确保大哦，时间是不是很大，但对于1000，10K的权力，100k的和给coliru我答案0.4ms，28ms和2.8s。不坏的小学数学？
I am working on an exercise and seemed to be stuck more with how to approach the problem mathematically, rather than syntactically.
The idea is simple when a number is relatively small. Given a base and power, the program should sum the digits of the result. Let's use an example to explain what I want to do.
base 2 and power 8 is given and thus2^8 = 256 then the program should sum the digits of the answer so2+5+6 = 13 and that is the whole point, to find the sum of the digits of the result of a base raised to a power.
Now, this is in an easy example, if I move to a ridiculously huge number, let's say 2^1000, this is almost impossible to just throw into anything that I have tried as we lose precision because the result is huge and gets truncated. The answer must be precise.
I thought maybe there is a mathematical way to do this differently, somehow break it up into smaller chuncks but really I can't think of any relationships other than:
2^1000 = 2^500*2^500
1000 log(2) = log(ans)
Either way, this doesn't get me anywhere near digits in the result that I can start summing.
I hope that I explained it clearly.
For what it is worth, I am using C++ (and gave lua a shot too) and maybe I could use a library but this number would have 302 digit places and I should write my program to handle an exponent of 1000. I really think I am missing some mathematical trick here.
EDIT Partial Solution Found
I have spent a little time with lua trying to solve this today, and I will give it a shot with C++ tonight to see if I get different results. I can find the source of the error, but I have found a solution that works for most cases. Just not for 2^1000, and some other exponents with very large numbers.
The solution works described and the Comment from MooseBoys.
I make use of a modular exponentiation. The lua code is below:
-- Function purpose: Calculate modular exponent (see wiki in comment
from MooseBoys)
--
-- @param b: base
-- @param e: exponent
-- @param m: modulation
-- @result c: result
--
-- example: 2^15 = 32768
-- ModPow(2,15,10) = 8
-- ModPow(2,15,100) = 68
--
local ModPow = function(b,e,m)
local c = 1
for i = 1, e do
c = c*b%m
end
return c
end
-- Function purpose: Check uniqueness of result from last one.
-- ModPow will not return leading 0, so in the case 2^20 = 1048576
-- Sum result would equal 35 because:
-- ModPow(2,20,10^5) = 48576
-- ModPow(2,20,10^6) = 48576
--
-- Also there is an issue with rounding I am working on. Current Problem
-- Sometimes, result is 6.xxxxxxxxxx2e+294
-- and with leading 0 result is 6.xxxxxxxxxx3e+294
-- So the result does not catch there was a leading 0 since s1 and s2
-- are not equal
-- However, this fix is giving me problems (assuming mod exponent always
-- grows by an order of magnitude.. 10^(n+1) each cycle), I assumed
-- just checking exponent value is good enough
-- Now I get some strange results as outlined blow
--
-- @param s1: Current result from ModPow (as string)
-- @param s2: Last result of ModPow (as string)
-- @result bool based on whether or not this number is valid to add to the sum
local CheckUnique = function(s1,s2)
if s1:find('e') and s2:find('e') then --fix rounding?
if(s1:sub(s1:find('e'),s1:len())==s2:sub(s2:find('e'),s2:len())) then print(0) return false end
elseif (s1 == s2) then print(0) return false --fix leading 0
end
print(s1) --test
return true
end
--self explanitory
local base = 2
local exp = 1000
local mod = 10
--Counters and value holders
local sum = 0
local lval = 0
local val,valS = 1,'1'
local cycle = 1
--Know when to stop
local endval = base^exp
print(endval)
while val ~= endval do
val = ModPow(base,exp,mod^cycle)
valS = tostring(val)
if(CheckUnique(valS,lval)) then --is unique
sum = sum + tonumber(valS:sub(1,1)) --sum leading digit
end
lval = valS
cycle = cycle+1
end
print(sum)
The problem lies within the result.
You can imagine, printing every result from the mod cycle should be something like
Value: 1048576
6
76
576
8576
48576
0
1048576
sum: 31
I put a print(0) on there when the check detects leading 0, otherwise, prints value of c. You can see, each first digit will get added to give the correct sum. Each net line should contain the previous line plus the new digit, like a growing heading basically.
However, the problem I can't solve is now when I extend this to a large number, let's say the solution I cam going for. 2^1000..
Results: (Healthy lines, near the end)
2.6725480652012e+288
6.2672548065201e+289
8.6267366100831e+290
1.8626730674387e+291
7.186267401715e+292
0
6.0718626734093e+294
8.6071862673409e+295
0
5.0860718626736e+297
1.5086071862673e+298
7.1508607186267e+299
The last line for instance, is the same as if you list the first digits going backwards in the list:7.1508607186267e+299
7 15086071862
Being excited, I found the answer to be incorrect. I looked deeper in to the lines and found these unhealthy lines:
9.18229858679e+069
7.5447775000848e+070
8.8906306939456e+069
4.1746958410049e+072
5.0621122825342e+073
4.1602034907325e+074
1.9248790609684e+075 -- no such order 454879 but have 924879?
....
8.3104764719996e+086
3.8310476472e+087
4.6735451839797e+088
8.0281504870817e+089
3.0808317990698e+090
9.0430240225156e+091 --no such order 938438...?
There appear to be several areas where this happens, and only on exponents over 200ish.. I checked with 100 and it was perfect. noticed mistakes in 200 such as
2.9937827928353e+018
0
2.0299378279284e+020
2.2029937827928e+021
7.8493010541604e+022
5.0206666406882e+023
0
3.384239167984e+025
Anyone have any new tips on what may be the problem?(sorry, my lua interperter may be different, not sure about lua in general..I am just using an IDE that is used for game scripts)
Okay, getting closer. My C++ program handles things a big better and here is the code for it. Still getting the wrong answer, but at least I am getting the same amount of digits. I can't seem to figure out what is wrong with this now. The thing is, this exercise is on a website, I don't know the correct answer, just that my program is giving me the wrong answer for 2^1000. It passes the other test cases I give it (the ones I can do manual and check the answer up to 2^20)
#include <iostream>
#include <cmath>
double ModPow(int,int,long double);
int main() {
int base = 2;
int power = 1000;
long double mod = 10;
long double val = 0;
int i = 0;
int sum = 0;
double ans = pow(base,power);
std::cout << ans << std::endl;
while(ans != val) {
val = ModPow(base,power,mod);
std::cout<< val << " ";
sum += int(floor(val/(mod/10)));
mod = mod * 10;
i += 1;
if(i%5 == 0) std::cout << std::endl;
}
std::cout << std::endl << sum << std::endl;
std::cout << i << std::endl;
std::cin.ignore();
return 0;
}
double ModPow(int b, int e, long double m) {
double c = 1;
for(int i = 1; i <= e; i++) {
c = fmod(c*b,m);
}
return c;
}
Here, I can see that there is strange behavior during the loop still. Logically, the exp should increase by one each time as I keep adding a digit. I see behavior at e+22 and it drops back to e+21, not sure why. Here is the full result of my program (I have made the doubles long doubles, and added file writing but results are the same as code above)
6 76 376 9376 69376
69376 8.06938e+006 6.80694e+007 6.68069e+008 5.66807e+009
5.66807e+009 2.05668e+011 7.20567e+012 3.72057e+013 8.37206e+014
6.83721e+015 8.68372e+016 3.86837e+017 4.38684e+018 2.43868e+019
6.24387e+020 2.62439e+021 8.81371e+022 7.17853e+021 6.67056e+024
5.66706e+025 2.56671e+026 6.11305e+027 1.49872e+026 7.84562e+029
8.79213e+030 5.26226e+031 2.66375e+032 7.26638e+033 4.84075e+034
3.21959e+035 6.35788e+036 6.73897e+037 6.73897e+037 6.73897e+037
2.62589e+038 2.98945e+041 2.98945e+041 6.02989e+043 9.17698e+044
7.16921e+045 7.05229e+046 6.70523e+047 6.5113e+048 4.65113e+049
8.52121e+050 3.85212e+051 7.38521e+052 4.19563e+053 5.91881e+054
4.39205e+055 3.9345e+056 9.04097e+057 9.04097e+057 3.68596e+059
1.49612e+060 7.7534e+061 7.39705e+061 4.22204e+063 6.98596e+063
6.92886e+065 4.69289e+066 8.22986e+067 1.82299e+068 9.1823e+069
7.54478e+070 1.14456e+071 4.11446e+072 3.62523e+073 9.90302e+074
1.92488e+075 4.59175e+076 5.88549e+077 1.35968e+078 6.13597e+079
6.6136e+080 4.66136e+081 7.48063e+082 6.12132e+083 8.8392e+084
7.86463e+085 6.94822e+086 6.32933e+087 5.62433e+088 6.56243e+089
2.3548e+090 5.60251e+090 7.14338e+091 9.90736e+093 6.14551e+094
5.791e+095 2.5791e+096 5.12015e+097 1.81734e+098 3.08347e+099
4.30835e+100 4.43083e+101 9.44308e+102 8.62251e+103 4.79117e+104
4.47912e+105 4.70365e+106 6.26271e+107 9.63625e+108 1.34535e+109
2.5938e+110 4.77635e+110 7.92388e+112 2.33449e+113 9.38763e+114
1.74483e+115 4.23631e+116 3.8324e+117 3.10928e+118 8.8341e+119
9.80234e+120 5.28235e+121 4.52823e+122 8.69571e+123 7.59308e+124
6.61087e+123 8.34403e+126 8.26135e+127 3.82614e+128 6.83699e+128
5.48343e+130 7.05731e+131 2.02676e+132 1.20268e+133 3.72264e+134
4.37226e+135 5.43723e+136 1.68563e+137 9.63719e+138 3.70399e+139
1.84462e+140 6.61036e+141 4.66104e+142 3.85213e+143 2.38521e+144
7.39926e+145 4.95209e+146 2.70772e+147 1.27077e+148 9.49987e+149
6.39539e+150 9.72139e+151 5.89019e+152 7.15679e+153 7.15679e+153
3.38172e+154 5.84268e+156 9.72579e+157 4.87575e+158 5.6501e+159
1.85286e+160 4.18529e+161 4.60739e+162 7.12977e+163 5.71298e+164
8.86201e+165 7.8862e+166 5.82415e+167 4.61194e+168 8.46119e+169
7.95321e+170 9.01956e+171 7.90196e+172 1.40488e+173 2.38969e+174
9.12607e+175 8.5208e+176 2.61635e+177 7.26163e+178 1.87538e+179
6.18754e+180 6.6906e+181 2.05665e+182 3.79061e+183 4.37906e+184
4.43791e+185 9.87813e+186 1.98781e+187 7.03446e+188 1.57091e+189
5.7816e+190 7.57816e+191 2.1734e+191 3.5815e+193 9.77689e+194
8.97769e+195 1.08115e+196 5.10812e+197 4.6079e+198 4.46079e+199
5.44608e+200 3.69583e+201 3.36958e+202 1.94715e+203 9.19309e+204
1.7556e+205 9.45675e+206 5.94568e+207 6.45002e+208 9.11561e+209
1.17058e+210 8.60292e+211 7.86029e+212 2.48236e+213 1.2582e+214
6.04576e+215 9.60458e+216 4.34447e+217 5.43445e+218 8.42133e+219
9.84213e+220 1.8562e+221 8.38891e+221 1.08389e+223 7.01599e+223
1.07016e+225 3.10702e+226 4.3107e+227 1.50548e+228 1.06711e+229
8.65791e+230 9.86579e+231 8.18076e+232 2.68057e+232 1.85488e+234
1.85488e+234 2.26339e+236 4.66336e+237 6.27494e+238 5.24964e+239
3.52496e+240 2.99353e+240 9.96218e+242 8.99622e+243 4.9693e+243
1.33007e+245 3.78439e+246 1.99925e+247 8.51404e+248 8.47445e+249
2.95141e+250 7.13201e+251 1.7132e+252 9.76862e+253 9.36726e+254
3.92421e+255 6.39242e+256 8.42555e+256 4.87969e+258 4.09894e+259
2.17963e+260 1.61217e+261 8.27277e+261 4.08273e+263 4.53756e+264
9.67271e+265 9.67271e+265 9.19793e+267 1.91979e+268 2.52109e+267
5.12996e+270 6.60659e+271 9.64583e+272 6.96458e+273 3.07557e+274
7.59723e+275 4.30703e+276 6.07449e+277 2.87595e+278 5.82907e+279
4.59589e+279 2.07609e+281 6.20761e+282 9.17199e+283 5.9172e+284
5.9172e+284 7.05917e+286 6.70229e+287 2.67023e+288 6.26707e+289
8.62671e+290 1.86267e+291 7.18627e+292 7.18627e+292 6.07186e+294
8.60719e+295 8.60719e+295 5.08607e+297 1.50861e+298 7.15086e+299
7.15086e+299 1.07151e+301
You want a solution that doesn't directly involve just doing 2**1000? Well, we can do it manually. How many digits does 2**1000 have? Definitely at most 1,000.
Thus:
int sum_digits(int e) {
std::vector<int> digits(e);
digits[0] = 1;
int last_digit = 1;
for (int power = 0; power < e; ++power) {
int carry = 0;
for (int idx = 0; idx < last_digit; ++idx) {
int prod = digits[idx] * 2 + carry;
if (prod > 9) {
carry = 1;
prod -= 10;
}
else {
carry = 0;
}
digits[idx] = prod;
}
if (carry) {
digits[last_digit++] = 1;
}
}
// then just sum 'em
return std::accumulate(digits.begin(), digits.end(), 0);
}
That's pretty quick and obviously correct. Sure the big-Oh time isn't great, but for powers of 1000, 10k, and 100k coliru gives me the answer 0.4ms, 28ms, and 2.8s. Not bad for grade school math?
这篇关于总和所造成的指数位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！