來源：牛客網(wǎng)

文章目錄

• • 題目描述
  • 題解：
  • 代碼：

時(shí)間限制：C/C++ 1秒，其他語(yǔ)言2秒 空間限制：C/C++ 131072K，其他語(yǔ)言262144K 64bit IO Format: %lld

題目描述

定義S(n) = 12 + 22 + … + n2，輸出S(n) % 1000000007。

注意：1 < n < 1e18。

輸入描述:

多組輸入，輸入直到遇到EOF為止；

第一行輸入一個(gè)正整數(shù)n。

輸出描述:

輸出S(n) % 1000000007的結(jié)果。

示例1
輸入

1 2 1000

輸出

1 5 333833500

題解：

平方和公式：1²+2²+3²+…+n²=n(n+1)(2n+1)/6
（建議補(bǔ)一補(bǔ)高中的一些公式，我也沒想起來 ）
注意題目是要mod的
模運(yùn)算：
(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
我們可以發(fā)現(xiàn)唯獨(dú)沒有除法的模運(yùn)算，但是公式中有個(gè) /6 需要處理，那我們可以用逆元的方式將除法變成乘法
逆元：整數(shù)a,b，滿足a * b = 1（mod m），那么稱b是a的模m乘法逆元
比如：A/B%C我們可以寫成A * （1 / B）% C，這樣就是AX%C的形式，如何求X？和上面的逆元結(jié)合起來就OK了
這樣/6%mod，我就可以寫成 inv（6）%mod
求逆元的方法這里就不詳細(xì)介紹了

代碼：

#include<iostream> #include<cstdio> using namespace std; typedef long long ll; const ll mod=1000000007; ll exgcd(ll a,ll b,ll &x,ll &y)//擴(kuò)展歐幾里得算法 {if(b==0){x=1;y=0;return a; //到達(dá)遞歸邊界開始向上一層返回}ll gcd=exgcd(b,a%b,x,y);ll y1=y; //把x y變成上一層的ll x1=x;y=x1-(a/b)*y1;x=y1;return gcd; //得到a b的最大公因數(shù) } ll inv(ll a,ll mod){ll x,y;ll gcd=exgcd(a,mod,x,y);if(gcd!=1)return -1;else return (x+mod)%mod; } int main() {ll n;while(cin>>n){ll ans=0;ans=(((n%mod)*((n+1)%mod)%mod*((2*n+1)%mod))%mod);ll inv6=inv(6,mod);ans=(ans%mod*inv6%mod)%mod;cout<<ans<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的序列求和的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。