打表+分析找规律：

规律1：数量和的规律

首先观察$$$A$$$，前几项为1, 2, 2, 3, 4, 4, 4, 5, 6, 6, ...，发现数列$$$A$$$其实是1,2,3,4,5,...依次出现，只是个数在发生变化。

定义$$$c_n$$$为$$$n$$$在$$$A$$$中出现的次数，前几项为1, 2, 1, 3, 1, 2, 1, 4, ...，发现奇数项$$$c_{2k+1}=1$$$，偶数项$$$c_{2k}=c_k+1$$$。

定义$$$s_n$$$为$$$c_n$$$的前$$$n$$$项和，则有如下规律：

$$$s_{2*k}$$$=$$$(c_1+c_3+...+c_{2k-1})+(c_2+c_4+...+c_{2*k})$$$=$$$n+(c_1+c_2+...+c_k)+n$$$=$$$2n+s_k$$$，

$$$s_{2*k+1}$$$=$$$(c_1+c_3+...+c_{2*k+1}+(c_2+c_4+...+c_{2*k}))$$$=$$$n+1+(c_1+c_2+c_k)+n$$$=$$$2n+1+s_k$$$

综上可得$$$s_n$$$=$$$s_{\lfloor \frac{n}{2}\rfloor}+n$$$

$$$s_n$$$的含义是，1~n在A中总共出现了多少次

规律2：单个n出现次数的规律

观察$$$c_n$$$发现，

1,    3,    5, ..., 1+2*k 出现1次

2,    6,  10, ..., 2+4*k 出现2次

4,  12,  20 ,..., 4+8*k 出现3次

n的出现次数符合这样的规律：从$$$2^t$$$开始，公差为$$$2^{t+1}$$$的数列中的每个数在A中出现$$$t+1$$$次。

结论1中，我们知道了1~n在A中总共出现了多少次，那么在结论2中，我们还可以对它们求和：把1~n重新组合为若干个等差数列，每个等差数列的首项一定是$$$2^t$$$，而尾项则是不超过n的最大$$$2^t+2^{t+1}*k$$$；通过遍历$$$2^t$$$不大于n的所有$$$t$$$，可以快速的求出所有1~n的和。

有了这些准备，求A当前n项和就可以这样：由于前n项并不一定包含了全部的1~$$$a_n$$$，只能直接求全部的1~$$$a_{n}-1$$$的和，再求有几个的$$$a_n$$$。

但是$$$a_n$$$是未知的，为了求$$$a_n$$$，可以利用规律1，二分查找一个x，使得$$$s_{x-1}<n<s_x$$$，那么也就意味着，A的第$$$s_{x-1}+1$$$~$$$s_{x}$$$项都是x，那么$$$a_n$$$就是x；另一方面，A的前n项中，$$$a_n$$$的数量就是n-$$$s_{x-1}$$$。

打表+分析发现，$$$n$$$和$$$s_n$$$大约为1:2的关系，也就是说在二分寻找$$$x$$$的时候，大约有2(x-1)<n<2x的关系，也就是说，搜索的范围缩小到了n/2的附近。具体长度大概估计就可以了。

#include<stdio.h>

/*

 * HDU6304 Chiaki Sequence Revisited 数学题学习

 * an为原数列从第二项开始，前几项为：1,2,2,3,4,4,4,5,6,6,...

 *

 * PART 1

 * n的数量和的规律

 * 记cn为n在{ai}中出现次数，前几项为：1,2,1,3,1,2,1,4,...

 * 打表+分析发现，c(2*k+1)=1, c(2*k)=c(k)+1

 * 设sn为cn前n项和

 * s(2*n)=n项奇数项+n项偶数项=c(1)+c(3)+...+c(2*n-1)+c(2)+c(4)+...+c(2*n)=n+c(1)+...c(n)+n=s(n)+2*n

 * 同理，s(2*n+1)=(n+1)项奇数项+n项偶数项=n+1+s(n)+n=s(n)+2*n+1

 * 综上，s(n)=s(n/2)+n;

 * 于是可以在log(N)内求出s(n)

 * s(n)的含义为1~n在{ai}中总共有多少个，也就是在{ai}中，最后一个ai=n的编号i=s(n)

 * 为了求出第i个ai，可以通过二分查找，找到s(j)<i<s(k)，那么ai就是k

 * 于是，可以用log(N)*log(N)求出第i个ai

 *

 *

 * PART 2

 * n出现次数的规律

 * 打表+分析发现

 * 1,    3,    5, ..., 1+2*k 出现1次

 * 2,    6,  10, ..., 2+4*k 出现2次

 * 4,  12,  20 ,..., 4+8*k 出现3次

 * 规律：2^t的所有倍数出现t+1次

 * 于是对于任何一个n，通过遍历t，利用等差数列和x出现次数的方法，在log(N)内求出小于n的所有ai的和

 *

 *

 * PART 3

 * {ai}前n项求和过程分为：

 * log(N)*log(N)求出an

 * log(N)求出小于an的所有ai的和

 * log(N)求出最后一个ax=an-1的编号，那么所有an的和为an*(n-ax)

 *

 */

 typedef long long ll;

const ll  mod = ;

//log(N)求cn前n项和，也就是求不大于an的一共有几项

ll sum(ll n)

{

    if (n <= )return  n;

    ll res = (sum(n >> ) + n);//注意这里不能取模

    return res;

}

//求sn大于等于key的最小an

ll bins(ll l, ll r,ll key)

{

    ll mid;

    while (l+<r)

    {

        mid = (l + r) >> ;

        if (sum(mid) >= key)

            r = mid;

        else l = mid;

    }

    return r;

}

int main()

{

    int kase;

    ll n;

    scanf("%d", &kase);

    while (kase--)

    {

        scanf("%lld", &n);

        n--;//我们考虑的an数列是从原数列的第二项开始的，相应的个数要-1

        /*

         * 打表+分析发现，i和sum(i)大约为1:2的关系

         * 也就是说an和n的关系大约为1:2

         * 缩小搜索区间到n/2附近

         */

        ll an = bins((n>>)-, (n>>)+, n);

        ll ans = ;//原数列的第一个1

        for(ll wide=,base=,t=;base<an;base=wide,wide<<=,t++)

        {

            //等差数列求和：base,base+wide,...base+k*wide

            //求k为小于an的最大情况

            ll k = (an - base-) >> t;//除wide等价于右移t位

            ll help = (k + )%mod;

            ll     temp = (((help*help)%mod)*(base%mod))%mod;

            ans = (ans + ((t%mod)*temp)%mod) % mod;

        }

        //再加上前n个数里所有的an

        ans =     (ans + ((an%mod)*((n%mod +(mod- (sum(an - )%mod)))))%mod)%mod;

        printf("%lld\n", ans);

    }

}