网站的二维码怎么做的,访问WordPress速度,微信自媒体怎么赚钱,网络公司的推广来源#xff1a;牛客网 文章目录题目描述题解#xff1a;代码#xff1a;时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 131072K#xff0c;其他语言262144K
64bit IO Format: %lld题目描述 定义S(n) 12 22 … n2#xff0c;输出S(n) …来源牛客网
文章目录题目描述题解代码时间限制C/C 1秒其他语言2秒
空间限制C/C 131072K其他语言262144K
64bit IO Format: %lld题目描述 定义S(n) 12 22 … n2输出S(n) % 1000000007。 注意1 n 1e18。 输入描述: 多组输入输入直到遇到EOF为止 第一行输入一个正整数n。 输出描述: 输出S(n) % 1000000007的结果。 示例1 输入
1
2
1000输出
1
5
333833500题解
平方和公式122232…n2n(n1)(2n1)/6 建议补一补高中的一些公式我也没想起来 注意题目是要mod的 模运算 (a b) % p (a % p b % p) % p (a - b) % p (a % p - b % p) % p (a * b) % p (a % p * b % p) % p a b % p ((a % p)b) % p 我们可以发现唯独没有除法的模运算但是公式中有个 /6 需要处理那我们可以用逆元的方式将除法变成乘法 逆元整数a,b满足a * b 1mod m那么称b是a的模m乘法逆元 比如A/B%C我们可以写成A * 1 / B% C这样就是AX%C的形式如何求X和上面的逆元结合起来就OK了 这样/6%mod我就可以写成 inv6%mod 求逆元的方法这里就不详细介绍了
代码
#includeiostream
#includecstdio
using namespace std;
typedef long long ll;
const ll mod1000000007;
ll exgcd(ll a,ll b,ll x,ll y)//扩展欧几里得算法
{if(b0){x1;y0;return a; //到达递归边界开始向上一层返回}ll gcdexgcd(b,a%b,x,y);ll y1y; //把x y变成上一层的ll x1x;yx1-(a/b)*y1;xy1;return gcd; //得到a b的最大公因数
}
ll inv(ll a,ll mod){ll x,y;ll gcdexgcd(a,mod,x,y);if(gcd!1)return -1;else return (xmod)%mod;
}
int main()
{ll n;while(cinn){ll ans0;ans(((n%mod)*((n1)%mod)%mod*((2*n1)%mod))%mod);ll inv6inv(6,mod);ans(ans%mod*inv6%mod)%mod;coutansendl;}return 0;
}
