BestCoder Round #64 (div.2)
Array
问题描述
Vicky是个热爱数学的魔法师，拥有复制创造的能力。
一开始他拥有一个数列{1}。每过一天，他将他当天的数列复制一遍，放在数列尾，并在两个数列间用0隔开。Vicky想做些改变，于是他将当天新产生的所有数字（包括0）全加1。Vicky现在想考考你，经过100天后，这个数列的前M项和是多少？。
输入描述
输入有多组数据。
第一行包含一个整数T，表示数据组数。T. \left( 1 \leq T \leq 2 * {10}^{3} \right)(1≤T≤2∗103)
每组数据第一行包含一个整数M. \left( 1\leq M \leq {10}^{16} \right)(1≤M≤1016)
输出描述
对于每组数据输出一行答案.
输入样例
3
1
3
5
输出样例
1
4
7
Hint
第一项永远为数字11，因此样例1输出11
第二天先复制一次，用0隔开，得到{1,0,1}，再把产生的数字加1，得到{1,1,2}，因此样例2输出前3项和1+1+2=41+1+2=4.
第三天先得到{1,1,2,0,1,1,2}，然后得到{1,1,2,1,2,2,3}，因此样例3输出前5项和1+1+2+1+2=71+1+2+1+2=7
#include<stdio.h>
#include<string.h> #define N 110000
#define oo 0xfffff long long sum[], a[]; long long Find(long long n, int nn)
{
if(nn<=)
return ; if(n<a[nn])
return Find(n, nn-);
else if(n==a[nn])
return sum[nn];
else
return sum[nn] + Find(n-a[nn]-, nn) + n - a[nn];
} int main()
{
int i, nn;
long long w = 1e17;
sum[] = , a[] = ; for(i=; i<; i++)
{
a[i] = a[i-]* + ;
sum[i] = sum[i-]* + a[i-] + ; if(a[i]>w)
{
nn = i;
break;
}
} int T;
scanf("%d", &T);
while(T--)
{
long long n, ans; scanf("%I64d", &n); ans = Find(n, nn); printf("%I64d\n", ans);
}
return ;
}