题目链接：
题目描述：
刚开始给一个1，序列a是由a[i]个i组成，最后1就变成了1,2,2,3,3,4,4,4,5,5,5.......，最后问a[i]出现n次(i最大)时候，i最后一次出现的下标是多少？
解题思路：
问题可以转化为求a[i] == n (i最大)，数列前i项的和为多少。
index： 1 2 3 4 5 6 7 8 9 10
a: 1 2 2 3 3 4 4 4 5 5
可以观察出：ans[1] = 1, ans[i] = ans[i-1] + a[i]*i;
但是n<=1e9,打不了这个庞大的表。进一步观察，可以发现a数组里面有很多的重复元素，辣么就可以对a数组里面的元素进行压缩存进b数组里面(出现次数为i的最后一个元素为b[i])：
index： 1 2 3 4 5 6 7 8 9 10
a: 1 2 2 3 3 4 4 4 5 5
b: 1 3 5 8 11 15 19 23 28 33
ans: 1 11 38 122 272 596 1086
1到出现次数为i的最后一个元素的区间和为ans[i]，由a[]可以看出ans[i] = ans[i-1] + (b[i] + b[i-1] + 1) * (b[i] - b[i-1]) / 2 * i;
每次查询的时候如果n不在b[i]里面，可以找到一个最接近n并且小于n的b[i]，然后再套用一次等差数列求和即可。
还有就是等差数列求和的时候，除以2要用到逆元处理一下。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef __int64 LL;
const int INF = 0x3f3f3f3f;
const int maxn = ;
const int mod = ;
LL a[maxn], b[maxn], ans[maxn], num; LL quick_mod(LL x, LL n)
{
LL res = ; while (n)
{
if (n % )
res = (res * x) % mod; x = (x * x) % mod;
n /= ;
}
return res % mod;
}
void init ()
{
LL res = , j = , nu; a[] = b[] = ;
a[] = b[] = ;
a[] = num = ;
b[] = ; while (b[num] <= 1e9)
{
if (res <= num)
{
j ++;
res += a[j];
} while (res > num)
{
num ++;
a[num] = j;
b[num] = b[num-] + a[num];
} } //printf ("%I64d %I64d\n", num, b[num]); ans[] = ;
ans[] = ; for (int i=; i<=num; i++)
ans [i] = (ans[i-] + (b[i] + b[i-] + ) % mod * a[i] % mod * i % mod * quick_mod(, mod-) % mod) % mod; } int main ()
{
LL t, n;
init ();
scanf ("%I64d", &t); while (t --)
{
scanf ("%I64d", &n);
LL pos = lower_bound (b, b+num, n) - b; if (b[pos] == n)
{
printf ("%I64d\n", ans[pos]);
continue;
} LL res = (ans[pos-] + (b[pos-] + n + ) % mod * (n - b[pos-]) % mod * pos % mod * quick_mod(, mod-) % mod) % mod; printf ("%I64d\n", res);
}
return ;
}