F. Sum of Numerators

Who is The 19th ZUCCPC Champion

https://ac.nowcoder.com/acm/contest/31533/A

题目链接

题意

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

制约

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

解答

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

\sum_{i = 1}^N[i \% 2 = 1] \times i = \bigg\lceil\dfrac{N}{2}\bigg\rceil ^2

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

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

X = x2 ^ t,\;\mathtt{where}\;\gcd(2, x) = 1

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

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

\displaystyle\sum_{i = 1}^N[i \% 2 = 0] \times i = \bigg\lfloor\dfrac{N}{2}\bigg\rfloor \times \bigg(\bigg\lfloor\dfrac{N}{2}\bigg\rfloor + 1\bigg)

即 $\underbrace{2 + 4 + 6 + 8 + \cdots + N}_{x\;项} = 2 \times (1 + 2 + 3 + 4 + \cdots + \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';
}

全部评论

推荐最新楼层

03-24 13:24

已编辑

江西农业大学后端工程师

后端崩盘了？前端也死了？我们不是第一批这么想的人

最近或许大家都听说xxxx厂裁员，无论前端，后端，大数据，测试，运维，人人可危， “前端死了，后端也死了，JAVA崩盘了，你们这群搞大模型的真是码奸”这次AI真的会让我们无路可走吗？？？？？？？？太阳底下已经没有新鲜事了旧的生产力的消失，必然有新的生产力诞生马车夫消失 → 汽车司机、修车工、石油工业诞生，从业人数是马车夫的百倍手工纺织女工消失 → 纺织机械工程师、面料设计师诞生，纺织品产量提升百倍2007年苹果开放 App Store，"移动端开发者"这个职业压根不存在。八年后，全球应用经济规模突破 1000亿美元，凭空诞生了数百万开发者岗位。每一次"这次真的完了...

二十岁的编程男神王大...：那这个时代是什么时代呢？是全员agent的时代，是前端+AI，后端+AI的时代，AI已经融入了项目生命周期的的每一个角落，那我最近在做的东西举例，检查BUG时，我们会用codex，CC等工具的skill去check，效果好还能直接fix，测试的时候，apifox等工具已经有了AI落地的改造，CI/CD阶段，我们会根据hook去跑AI check脚本，就连不少中间件，也迎来了AI落地的改造，（AI网关，AI在MQ中的运用),都可以去了解下另外记着，这些东西不是意义，工作只是谋生的一个手段，ai是让开发提效了，但是呢，原先一周的工作流程压缩到了两天内，同时低级的都裁员了，只有高级的去维护，你看似写的大义凛然，或许那天你也会成为你文章里面拒绝往前走的人，你才大二，面对技术有热情是对的

AI求职实录

点赞评论收藏