要求根据自然数列的前 N 项和求 N 值

admin - 2008-7-10 10:52:00

To check the speed of JCN Corporation new supercomputer it was decided to figure out the sum of first N (N<10600)positive integers. Unfortunately, by the time the calculation wasfinished the Chief Programmer forgot the value of N he entered.Your task is to write the program (for personal computer), which woulddetermine the value of N by the result calculated on supercomputer.

Note:
JCN Corporation manufactures only reliable computers, and its programmers write only correctly working programs.

InputOne line containing number M - the result of calculations on supercomputer.

OutputOne line, containing N - number, entered by Chef Programmer.

Sample

input	output
28	7

Problem Author: Eugene Bryzgalov
Problem Source: Ural Collegiate Programming Contest, April 2001, Perm, English Tour答案如下：

[复制到剪贴板]

CODE:

1 using System;

2 using System.Globalization;

3

4 namespace Skyiv.Ben.Timus

5 {

6 // [url]http://acm.timus.ru/problem.aspx?space=1&num=1153[/url]

7 sealed class T1153

8 {

9 static void Main()

10 {

11 BigInteger m = BigInteger.Parse(Console.ReadLine());

12 Console.WriteLine(BigInteger.Sqrt(m + m));

13 }

14 }

15

16 sealed class BigInteger : IComparable<BigInteger>

17 {

18 int[] digits = new int[601];

19

20 public BigInteger(int n)

21 {

22 digits[0] = n;

23 if (digits[0] > 9) Format();

24 }

25

26 public BigInteger(BigInteger x)

27 {

28 Array.Copy(x.digits, digits, digits.Length);

29 }

30

31 public static BigInteger Parse(string s)

32 {

33 BigInteger x = new BigInteger(0);

34 for (int i = s.Length - 1; i >= 0; i--) x.digits[s.Length - 1 - i] = s[i] - '0';

35 return x;

36 }

37

38 public int CompareTo(BigInteger x)

39 {

40 for (int i = digits.Length - 1; i >= 0; i--)

41 {

42 if (digits[i] > x.digits[i]) return 1;

43 else if (digits[i] < x.digits[i]) return -1;

44 }

45 return 0;

46 }

47

48 public static BigInteger Sqrt(BigInteger x)

49 {

50 BigInteger low, high;

51 GetLowAndHigh(x, out low, out high);

52 BigInteger mid = low;

53 int cmp = 0;

54 while (low.CompareTo(high) <= 0)

55 {

56 mid = (low + high) / 2;

57 cmp = (mid * mid).CompareTo(x);

58 if (cmp < 0) low = mid + 1;

59 else if (cmp > 0) high = mid + (-1);

60 else return mid;

61 }

62 if (cmp > 0) mid = mid + (-1);

63 return mid;

64 }

65

66 static void GetLowAndHigh(BigInteger x, out BigInteger low, out BigInteger high)

67 {

68 int xmax = x.digits.Length - 1;

69 while (xmax >= 0 && x.digits[xmax] == 0) xmax--;

70 const int doublePrecison = 15;

71 if (xmax < doublePrecison)

72 {

73 low = high = new BigInteger((int)Math.Sqrt(GetPrefix(x, xmax, doublePrecison)));

74 return;

75 }

76 int zeros = xmax - doublePrecison + 1;

77 if (zeros % 2 != 0) zeros++;

78 string[] ss = Math.Sqrt(GetPrefix(x, xmax, xmax - zeros + 1)).ToString("F8", CultureInfo.InvariantCulture).Split('.');

79 low = new BigInteger(0);

80 zeros /= 2;

81 int j = 1;

82 for (int i = 0; i < ss[0].Length; i++) low.digits[i + zeros] = ss[0][ss[0].Length - 1 - i] - '0';

83 for (int i = 0; i < ss[1].Length - 2 && j <= zeros; i++, j++) low.digits[zeros - j] = ss[1][i] - '0';

84 high = new BigInteger(low);

85 if (++high.digits[zeros - j + 1] > 9) high.Format();

86 }

87

88 static long GetPrefix(BigInteger x, int start, int length)

89 {

90 long v = 0;

91 for (int i = start; i >= 0 && length > 0; i--, length--) v = v * 10 + x.digits[i];

92 return v;

93 }

94

95 public static BigInteger operator +(BigInteger x, int y)

96 {

97 BigInteger z = new BigInteger(x);

98 z.digits[0] += y;

99 if (z.digits[0] > 9 || z.digits[0] < 0) z.Format();

100 return z;

101 }

102

103 public static BigInteger operator +(BigInteger x, BigInteger y)

104 {

105 BigInteger z = new BigInteger(x);

106 for (int i = x.digits.Length - 1; i >= 0; i--) z.digits[i] = x.digits[i] + y.digits[i];

107 z.Format();

108 return z;

109 }

110

111 public static BigInteger operator *(BigInteger x, BigInteger y)

112 {

113 BigInteger z = new BigInteger(0);

114 int xmax = x.digits.Length - 1;

115 int ymax = y.digits.Length - 1;

116 while (xmax >= 0 && x.digits[xmax] == 0) xmax--;

117 while (ymax >= 0 && y.digits[ymax] == 0) ymax--;

118 for (int xi = xmax; xi >= 0; xi--)

119 for (int yi = ymax; yi >= 0; yi--)

120 z.digits[xi + yi] += x.digits[xi] * y.digits[yi];

121 z.Format();

122 return z;

123 }

124

125 public static BigInteger operator /(BigInteger x, int y)

126 {

127 BigInteger z = new BigInteger(0);

128 int xmax = x.digits.Length - 1;

129 while (xmax >= 0 && x.digits[xmax] == 0) xmax--;

130 for (int remainder = 0, i = xmax; i >= 0; i--)

131 {

132 int quotient = 10 * remainder + x.digits[i];

133 remainder = quotient % y;

134 z.digits[i] = quotient / y;

135 }

136 return z;

137 }

138

139 void Format()

140 {

141 for (int quotient = 0, i = 0; i < digits.Length; i++)

142 {

143 int numerator = digits[i] + quotient;

144 quotient = numerator / 10;

145 int remainder = numerator % 10;

146 if (remainder < 0)

147 {

148 remainder += 10;

149 quotient--;

150 }

151 digits[i] = remainder;

152 }

153 }

154

155 public override string ToString()

156 {

157 int n = digits.Length - 1;

158 while (n >= 0 && digits[n] == 0) n--;

159 if (n < 0) return "0";

160 char[] cs = new char[n + 1];

161 for (int i = n; i >= 0; i--) cs[i] = (char)(digits[n - i] + '0');

162 return new string(cs);

163 }

164 }

165 }

我们知道，自然数列的前 N 项和 M = N * ( N + 1 ) / 2 ≈ N2 / 2。所以 N = [ sqrt( 2 * M ) ]。这里 [x] 表示对 x 进行下取整。

这个程序的关键就是求 BigInteger 的平方根。本程序中第 66 到 86 行的 GetLowAndHigh() 方法估算出平方根的范围，然后在第 48 到 64 行的 Sqrt() 方法中用二分查找法找出所求的平方根。

星辰.Net技术社区论坛