test/Math/mod_sum_of_geometric_sequence/abc293-e.test.cpp

View this file on GitHub
Last update: 2025-03-23 20:36:27+09:00
Problem: https://atcoder.jp/contests/abc293/tasks/abc293_e

Depends on

等比数列の総和 (mod) (Math/mod_sum_of_geometric_sequence.hpp)

Code

// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc293/tasks/abc293_e
// competitive-verifier: IGNORE
// AtCoder's test cases are now private.

#include "Math/mod_sum_of_geometric_sequence.hpp"
#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long A, X, M;
    cin >> A >> X >> M;

    atcoder::modint::set_mod(M);
    atcoder::modint ans = sum_of_geometric_sequence<atcoder::modint>(1, A, X);

    cout << ans.val() << endl;

    return 0;
}

#line 1 "test/Math/mod_sum_of_geometric_sequence/abc293-e.test.cpp"
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc293/tasks/abc293_e
// competitive-verifier: IGNORE
// AtCoder's test cases are now private.

#line 1 "Math/mod_sum_of_geometric_sequence.hpp"
#include <bits/stdc++.h>
using namespace std;

template <class mint>
mint sum_of_geometric_sequence(mint a, mint r, long long n)
{
    assert(0 < n);

    if (n == 1)
    {
        return a;
    }

    mint x = sum_of_geometric_sequence(a, r, n / 2);

    mint ret = x + r.pow(n / 2) * x;
    if (n & 1)
    {
        ret = (a + r * ret);
    }

    return ret;
};
#line 6 "test/Math/mod_sum_of_geometric_sequence/abc293-e.test.cpp"
#include <atcoder/modint>
#line 8 "test/Math/mod_sum_of_geometric_sequence/abc293-e.test.cpp"

using namespace std;

int main()
{
    long long A, X, M;
    cin >> A >> X >> M;

    atcoder::modint::set_mod(M);
    atcoder::modint ans = sum_of_geometric_sequence<atcoder::modint>(1, A, X);

    cout << ans.val() << endl;

    return 0;
}