有关公式
  • 板块灌水区
  • 楼主lucy2012
  • 当前回复12
  • 已保存回复12
  • 发布时间2024/8/12 17:03
  • 上次更新2024/8/12 18:15:45
查看原帖
有关公式
1252442
lucy2012楼主2024/8/12 17:03

看到这题题解区说用平方和,立方和作,那公式是如何推出的?但某个题解真的有点【数据删除】。

题目:

小核桃近期遇到了一道经典问题——《翻纸牌》。

小核桃拥有 nn 张纸牌,其编号依次为 1、2、3……nn,且每张纸牌初始状态均为背面朝上。

接下来,小核桃要进行 nn 轮操作。在第 ii 轮操作时,她会将所有编号是 ii 的倍数的纸牌进行正反翻面。

现在,小核桃很想知道,当完成这 nn 轮操作之后,所有正面朝上的纸牌的编号总和是多少?

由于结果的数字可能会很大,所以请您将答案对 109+710^9 + 7 取模。

输入格式

输入一个整数 nn,代表纸牌的数量。

输出格式

输出一个整数,表示正面朝上的纸牌编号总和,并对 109+710^9 + 7 取模。

示例输入 1

20

示例输出 1

30

数据规模与约定

对于 30% 的数据:1≤n≤1061\leq n\leq 10^6 。 对于 60% 的数据:1≤n≤10141\leq n\leq 10^{14} 。 对于 100% 的数据:1≤n≤10181\leq n\leq 10^{18} 。

题解1(好【数据删除】): 一定要翻到最底下看看!

O(1)出答案的感觉真爽!

上公式即可!

AC 代码:

#include <bits/stdc++.h>
using namespace std;
long long n, mod = 1e9 + 7, t, ans;
int main()
{
    freopen("card.in", "r", stdin);
    freopen("card.out", "w", stdout);
    cin >> n;
    t = sqrt(n);
    ans = t * (t + 1) / 2;
    if (ans % 3 == 0)
        ans = ans / 3 % mod * (2 * t + 1) % mod;
    else
        ans = ans % mod * ((2 * t + 1) / 3) % mod;
    cout << ans << endl;
    return 0;
}

PS:看到 AC 代码后的正确交易流程:

  1. 看到 AC 代码

  2. 点赞!!!!!!!

  3. 愉快的 Ctrl + c

  4. 愉快的 Ctrl + v

  5. AC 啦!!!

题解2: 平方和公式:

∑i=1ni2=n×(n+1)×(2n+1)6\sum_{i=1}^{n}i^2 = \frac{n×(n + 1)×(2n + 1)}{6}

立方和公式:

∑i=1ni3=(n×(n+1)2)2\sum_{i=1}^{n}i^3 = (\frac{n×(n + 1)}{2})^2

题目+题解格式都是自己打的!很不容易呐!

2024/8/12 17:03
加载中...