hdu5439（找规律）的数列求和问题

The sequence is generated by the following scheme.

1. First, write down 1, 2 on a paper.
2. The 2nd number is 2, write down 2 2’s (including the one originally on the paper). The paper thus has 1, 2, 2 written on it.
3. The 3rd number is 2, write down 2 3’s. 1, 2, 2, 3, 3 is now shown on the paper.
4. The 4th number is 3, write down 3 4’s. 1, 2, 2, 3, 3, 4, 4, 4 is now shown on the paper.

5. The procedure continues indefinitely as you can imagine. 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, . . . .

所求答案为前n项i*f[i]的和&＃xff0c;f[i] 有i个&＃xff0c;所以1e9大概需要算到5e5就行&＃xff08;参考别人的思路&＃xff09;&＃xff0c;

upper_bound查找&＃xff08;好像是二分查找&＃xff09;&＃xff0c;自己按思路写的最开始用的for查找&＃xff0c;发现比别人慢很多&＃xff0c;然后才注意到这个函数&＃xff0c;以前虽然知道&＃xff0c;但并没怎么用过- -。

预处理&＃xff1a;sum存到i时数的个数&＃xff0c;g保存到i最后一个时的i*f[ i ]值。因为n找到后不一定是i的最后一个&＃xff0c;再填上多出部分即可