mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

等比数列の総和
(math/geometric_series_sum.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "math/geometric_series_sum.hpp"

等比数列の総和

使い方

• ll geometric_series_sum(ll a, ll n, ll m) : 初項 $1$, 公比 $a$, 項数 $n$ の等比数列の総和を $m$ で割ったあまりを返す。 $O(\log{N})$

Depends on

• math/power.hpp

Code

#pragma once

#include "../math/power.hpp"

long long geometric_series_sum(long long a, long long n, long long m){
	if(n == 0)return 0;
	if(n & 1){
		return (geometric_series_sum(a, n-1, m) + power(a, n-1, m)) % m;
	}
	return (geometric_series_sum(a, n/2, m) * (1LL + power(a, n/2, m))) % m;
}

#line 2 "math/geometric_series_sum.hpp"

#line 2 "math/power.hpp"

#include <type_traits>

template<typename T>
concept NotPrimitiveInt =
	!(std::is_same_v<T, int> ||
		std::is_same_v<T, long> ||
		std::is_same_v<T, long long> ||
		std::is_same_v<T, unsigned> ||
		std::is_same_v<T, unsigned long> ||
		std::is_same_v<T, unsigned long long>);

template<NotPrimitiveInt T>
T power(T n, long long k) {
	T ret = 1;
	while(k > 0) {
		if(k & 1)ret *= n;
		n = n*n;
		k >>= 1;
	}
	return ret;
}

long long power(long long n, long long k, long long p) {
	long long ret = 1;
	while(k > 0){
		if(k & 1)ret = ret*n % p;
		n = n*n % p;
		k >>= 1;
	}
	return ret;
}
#line 4 "math/geometric_series_sum.hpp"

long long geometric_series_sum(long long a, long long n, long long m){
	if(n == 0)return 0;
	if(n & 1){
		return (geometric_series_sum(a, n-1, m) + power(a, n-1, m)) % m;
	}
	return (geometric_series_sum(a, n/2, m) * (1LL + power(a, n/2, m))) % m;
}

Back to top page