math/sum_of_geometric_sequence.cpp

• View this file on GitHub
• Last update: 2021-08-08 16:43:28+09:00

Verified with

• test/yukicoder/2520.test.cpp

Code

#ifndef call_from_test
#include <bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
// first: sum_{i=0}^{n-1} r^i
// second: r^n
template<typename T>
pair<T, T> sum_of_geometric_sequence_impl(T r,long long n){
  if(n==1) return {T(1),r};
  auto p=sum_of_geometric_sequence_impl(r,n/2);
  T sum=p.first*(T(1)+p.second);
  T pow=p.second*p.second;
  if(n&1) sum+=pow,pow*=r;
  return {sum,pow};
}
// sum_{i=0}^{n-1} r^i
template<typename T>
T sum_of_geometric_sequence(T r,long long n){
  return sum_of_geometric_sequence_impl(r,n).first;
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

#line 1 "math/sum_of_geometric_sequence.cpp"

#include <bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
// first: sum_{i=0}^{n-1} r^i
// second: r^n
template<typename T>
pair<T, T> sum_of_geometric_sequence_impl(T r,long long n){
  if(n==1) return {T(1),r};
  auto p=sum_of_geometric_sequence_impl(r,n/2);
  T sum=p.first*(T(1)+p.second);
  T pow=p.second*p.second;
  if(n&1) sum+=pow,pow*=r;
  return {sum,pow};
}
// sum_{i=0}^{n-1} r^i
template<typename T>
T sum_of_geometric_sequence(T r,long long n){
  return sum_of_geometric_sequence_impl(r,n).first;
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

Back to top page