看到这题题解区说用平方和,立方和作,那公式是如何推出的?但某个题解真的有点【数据删除】。
题目:
小核桃近期遇到了一道经典问题——《翻纸牌》。
小核桃拥有 n 张纸牌,其编号依次为 1、2、3……n,且每张纸牌初始状态均为背面朝上。
接下来,小核桃要进行 n 轮操作。在第 i 轮操作时,她会将所有编号是 i 的倍数的纸牌进行正反翻面。
现在,小核桃很想知道,当完成这 n 轮操作之后,所有正面朝上的纸牌的编号总和是多少?
由于结果的数字可能会很大,所以请您将答案对 109+7 取模。
输入格式
输入一个整数 n,代表纸牌的数量。
输出格式
输出一个整数,表示正面朝上的纸牌编号总和,并对 109+7 取模。
示例输入 1
20
示例输出 1
30
数据规模与约定
对于 30% 的数据:1≤n≤106 。 对于 60% 的数据:1≤n≤1014 。 对于 100% 的数据:1≤n≤1018 。
题解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 代码后的正确交易流程:
看到 AC 代码
点赞!!!!!!!
愉快的 Ctrl + c
愉快的 Ctrl + v
AC 啦!!!
题解2: 平方和公式:
∑i=1ni2=6n×(n+1)×(2n+1)
立方和公式:
∑i=1ni3=(2n×(n+1))2
题目+题解格式都是自己打的!很不容易呐!