题目链接

题意

给定 $N,KN,\; K$，求解将序列 $\{{\displaystyle \frac{i}{2^K}}\}\backslash \{\backslash dfrac\{i\}\{2^K\}\backslash \}$ 中元素全部约分后的分子和，其中 $ii$ 遍历 $1\sim N1\; \backslash sim\; N$。

制约

$N\in [1,10^9],K\in [0,10^9]N\; \backslash in\; [1,\; 10^9],\; K\; \backslash in\; [0,\; 10\; ^\; 9]$

解答

首先注意到 $\gcd (2^K,\mathrm{o}\mathrm{d}\mathrm{d})=1\backslash gcd(2^K,\; \backslash mathrm\{odd\})\; =\; 1$，于是我们先将所有奇数和算入答案，我们知道：

即 $\underset{x\mathrm{项}}{\underbrace{1+3+5+7+\cdots +N}}=x^2\backslash underbrace\{1\; +\; 3\; +\; 5\; +\; 7\; +\; \backslash cdots\; +\; N\}\_\{x\backslash ;项\}\; =\; x^2$

接下来考虑偶数与 $2^{K}2\; ^\; K$ 约分的过程，对于每一个偶数，都可写作

于是 $2^{K}2\; ^\; K$ 将会约分所有 $t\le Kt\; \backslash le\; K$ 的部分，使得其变为一段奇数和，使用上述算式求解即可。

最后再加上没有被约分的偶数和即可，即

即 $\underset{x\mathrm{项}}{\underbrace{2+4+6+8+\cdots +N}}=2\times (1+2+3+4+\cdots +{\displaystyle \frac{N}{2}})\backslash underbrace\{2\; +\; 4\; +\; 6\; +\; 8\; +\; \backslash cdots\; +\; N\}\_\{x\backslash ;项\}\; =\; 2\; \backslash times\; (1\; +\; 2\; +\; 3\; +\; 4\; +\; \backslash cdots\; +\; \backslash dfrac\{N\}\{2\})$

参考代码

using i64 = long long;

void solve() {
    int n, k;
    std::cin >> n >> k;
 
    i64 ans = 0;
    for (k += 1; k -- && n; n -= (n + 1) / 2) {
        ans += 1LL * ((n + 1) / 2) * ((n + 1) / 2);
        (!k) && (ans += 1LL * (n / 2) * (n / 2 + 1));
    }
     
    std::cout << ans << '\n';
}