一点一点前进...

0%

欧拉项目 | 第80题 | 计算无理平方根小数部分的各位和

发表于 分类于 ， Disqus：

题目链接

众所周知，如果一个自然数的平方根不是整数，那么就是无理数。这样的平方根的小数部分是无限并且没有任何重复模式的。
2的平方根是 1.41421356237309504880…, 小数部分的前一百位和是475。

对于前一百个自然数，找出其中无理平方根的小数部分前一百位的总和。

这个题的难度在于精确的计算出小数点后99位。首先想到的是，肯定要模拟手算来开平方，具体的方法请参考Wiki百科里面的长除式算法。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private static string GetSqrt(int n)
{
	StringBuilder result = new StringBuilder();
	int integerPart = (int)Math.Sqrt(n);
	result.Append(integerPart);

	BigInteger a = new BigInteger(integerPart);
	BigInteger remainder = new BigInteger(n - integerPart * integerPart);
	for (int i = 0; i < 99; i++)
	{
		remainder *= 100;
		int b = 1;
		while ((a * 20 + b) * b < remainder)
		{
			b++;
		}

		b--;

		remainder = remainder - (a * 20 + b) * b;
		a = a * 10 + b;
		result.Append(b);
	}

	return result.ToString();
}

根据算法，a和余数会越来越大，a的长度会趋于100位，余数的长度会趋于200位，所以我使用了BigInteger来存储。for循环做了99次，因为题目要求100个数字，个位数已经占了一位了。
有了这个函数就可以求得给定整数开平方后的前一百位数字了。现在，只要写一个简单的循环就能得到最后的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int sum = 0;
for (int i = 2; i < 100; i++)
{
	int sqrt = (int)Math.Sqrt(i);
	if (sqrt * sqrt == i)
	{
		continue;
	}

	string decimalPart = GetSqrt(i);
	sum += decimalPart.Select(c => int.Parse(c.ToString())).Sum();
}

return sum;

在循环中，我排除了完全平方数，根据题意，它们是不计算到最后的和里面的。
值得一提的是，如果向GetSqrt里面传入完全平方数，在进入循环之前，余数是0，计算得到的b也就是0，循环不变，余数一直是0，b也一直是0，最后返回的数是平方根后面跟着99个0。