#MX101. 求和

求和

题目描述

记 f(k)f(k)(其中 kk 是正整数)表示所有 22 的正整数次幂数中能被 kk 整除的最大的数,例如 f(10k)=2kf(10^k)=2^k。

给定 nn,求

∑i=n+12nif(i) \sum\limits_{i=n+1}^{2n}\dfrac{i}{f(i)}

输入格式

仅一行一个整数 nn。

输出格式

仅一行一个数,表示答案。

样例 1 输入

2

样例 1 输出

4

样例 1 说明

f(3)=1f(3)=1,f(4)=4f(4)=4。

因此,3f(3)+4f(4)=3+1=4\dfrac{3}{f(3)}+\dfrac{4}{f(4)}=3+1=4。

样例 2 输入

77777

样例 2 输出

6049261729

数据规模与约定

  • 测试点 1∼31\sim3:n≤103n\le 10^3。
  • 测试点 4∼64\sim6:n≤105n\le 10^5。
  • 测试点 7∼107\sim10:无特殊限制。

对于 100%100\% 的数据:1≤n≤1091\le n\le 10^9。