LCP SUM

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

long long ans = 0;
for(int i = 1; i <= n; i ++)
     ans += lcp(i - 1,i)

给出n,求ans

lcp(i - 1,i)指的是两个数字的最长公共前缀,比如lcp(2,3) = 0,lcp(10,11) = 1,lcp(12345,12346) = 1234

Input

多组数据,每组数据一个n (1 <= n <= 10^9)

Output

对于每个n,输出一行,求得的ans

Sample Input

10
11
12
22
100

Sample Output

0
1
2
13
405

Hint

数据组数<=50000

Source

dream

Manager

Information
Solved Number194
Submit Number543
Problem Tags
dp
math
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel