题目159：因子的数根之和
Digital root sums of factorisationsA composite number can be factored many different ways. For instance, not including multiplication by one, 24 can be factored in 7 distinct ways:
24 = 2x2x2x3
24 = 2x3x4
24 = 2x2x6
24 = 4x6
24 = 3x8
24 = 2x12
24 = 24
Recall that the digital root of a number, in base 10, is found by adding together the digits of that number, and repeating that process until a number is arrived at that is less than 10. Thus the digital root of 467 is 8.
We shall call a Digital Root Sum (DRS) the sum of the digital roots of the individual factors of our number.
The chart below demonstrates all of the DRS values for 24.
The maximum Digital Root Sum of 24 is 11.
The function mdrs(n) gives the maximum Digital Root Sum of n. So mdrs(24)=11.
Find ∑mdrs(n) for 1 < n < 1,000,000.
题目：
一个合数能有很多种因子分解方式。比如说，在不包括 1 的乘积，24 可以有七种不同的分解方式如下：
24 = 2x2x2x3
24 = 2x3x4
24 = 2x2x6
24 = 4x6
24 = 3x8
24 = 2x12
24 = 24
回想下，一个 10 进制数字的数根，是把它各个位的数字相加，并重复这个过程，直到这个数字小于 10。
我们把DRS叫做数字独立因子的数根之和。下表展示了 24 的所有 DRS 值。
24 的 DRS 值中，最大的是 11。
定义 mdrs(n) 为 n 的最大 DRS 值，因此，mdrs(24) = 11
对于 1 < n < 1,000,000，求∑mdrs(n)。
本帖最后由 永恒的蓝色梦想 于 2020-7-15 22:27 编辑
def getDigitalRoot(n):
if n < 10: return n
r = 0
while n >= 10:
r += n%10
n //= 10
r += n
return getDigitalRoot(r)
#maximum Digital Root Sum
mdrs1M = #2-4s
mdrs1M = 7 # 10=2*5,2+5=7=>now is correct
x = 10
while True:#求:
m = min(10**6, 2*x)
# print(x+1,"-",2*x," i=")
for i in range(2, int(m**0.5)+1):
# if x <=20: print("i=",i,"j=",max(i,(x+1)//i), (m//i))
for j in range(max(i,(x+1)//i), (m//i)+1):
mdrs1M = max(mdrs1M, mdrs1M + mdrs1M)
x *= 2
if m == 1000000:
break
print("1000=",mdrs1M)
print("24=",mdrs1M)
# 1 < n <1000,000
print(sum(mdrs1M)) #14489159 gunjang 发表于 2020-7-15 20:32
欢迎答题！{:10_298:}
你没有加代码格式，我帮你加了一下{:10_248:} 本帖最后由 guosl 于 2020-12-2 06:37 编辑
对于一个整数n，其数字根有一个计算公式：drs(n) =(n-1) % 9+1
对于一个整数n的最大数字根可以通过递归式：mdrs(n) = max(mdrs(a)+mdrs(b)) 对所有 a*b=n)
故本题可以应用类似筛法的方法，通过不停修改mdrs(n)的值来得到。
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000000;
int mdrs;
int main(void)
{
for (int i = 2; i < N; ++i)
mdrs =(i - 1) % 9 + 1; //初值
for (int i = 2; i < N; ++i) //通过类似筛法的方法不停修改mdrs
for (int j = 2, k; (k = i*j) < N; ++j)
mdrs = max(mdrs, mdrs + mdrs);//获得更大的值
int nSum = 0;
for (int i = 2; i < N; ++i)
nSum += mdrs;
printf("%d\n", nSum);
return 0;
}
页:
[1]