ค้นหาผลรวมของซีรีส์ที่มีเทอมที่ n เป็น n^2 - (n-1)^2 ใน C++

ในปัญหานี้ เราได้รับค่าจำนวนเต็ม N งานของเราคือ ค้นหาผลรวมของอนุกรม n^2 - (n-1)^2 ไม่เกิน n เงื่อนไข .

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

Input : N = 3
Output : 6

คำอธิบาย −

[12 - (0)2] + [22 - (1)2] + [32 - (2)2] = 1 - 0 + 4 - 1 + 9 - 2 = 9

แนวทางการแก้ปัญหา

วิธีง่ายๆ ในการแก้ปัญหาคือการหาเทอมทั่วไปของอนุกรมแล้วหาผลรวมจนถึง n เทอม และการคำนวณผลรวมโดยใช้สูตรจะลดเวลาลงเหลือ O(1) นอกจากนี้ ผลลัพธ์อาจมีขนาดใหญ่มาก ดังนั้นต้องหาโมดูลัสของค่า

มาหาสูตรสำหรับเทอมที่ n ของอนุกรมกัน

$T_{n}\:=\:\mathrm{n^2-(n-1)^2}$

ในการแก้โดยใช้สูตร a2 - b2

$T_{n}\:=\:\mathrm{(n+n-1)*(n-n+1)}$

$=\:\mathrm{(2*n-1)*(1)}$

$=\:\mathrm{2*n-1}$

เมื่อใช้สิ่งนี้ เราสามารถหาผลรวมจนถึงเงื่อนไข n ของอนุกรมนั้นได้

$\mathrm{sum}\:=\:\sum(2*n-1)$

$\mathrm{sum}\:=\:2*\sum{n}\:-\:\sum{1}$

$\mathrm{sum}\:=\:2*(n*(n+1))/2-n$

$\mathrm{sum}\:=\:n*(n+1)-n\:=\:n^2\:+\:n\:-\:n\:=\:n^2$

ผลรวมของซีรีส์คือ n ² ซึ่งมีจำนวนมากจึงจะทำการดัดแปลง

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include<iostream>
using namespace std;
#define mod 1000000007
long long calcSumNTerms(long long n) {
   return ((n%mod)*(n%mod))%mod;
}
int main() {
   long long n = 4325353;
   cout<<"The sum of series upto n terms is "<<calcSumNTerms(n); return 0; 
}

ผลลัพธ์

The sum of series upto n terms is 678443653