Test/AtCoder/abc429_g.test.cpp

• View this file on GitHub
• Last update: 2025-10-27 16:11:27+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc429/tasks/abc429_g

Depends on

• Mod of Linear をsqrt(M)個の等差数列に分割する (Src/Number/SqrtHeuristicArithmetic.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

// #define PROBLEM "https://atcoder.jp/contests/abc429/tasks/abc429_g"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../../Src/Number/SqrtHeuristicArithmetic.hpp"
#include "atcoder/modint"
using mint = atcoder::modint;

#include <iostream>
using namespace std;
mint f(long long a, long long b, long long x, long long n) {
    mint res = 0, pw = mint{x}.pow(a), sum = 1;
    while (n) {
        if (n & 1)
            res = res * pw + sum;
        sum += sum * pw;
        pw *= pw;
        n >>= 1;
    }
    return res * mint{x}.pow(b);
}
mint naive(long long N, long long M, long long A, long long B, long long X, long long R) {
    mint res = 0;
    for (long long i = 0 ; i < N ; i++) {
        res += mint{X}.pow((A * i + B) % M);
    }
    return res;
}
void solve() {
    long long N, M, A, B, X, R;
    cin >> N >> M >> A >> B >> X >> R;
    mint::set_mod(R);
    long long g = gcd(A, M);
    A /= g;
    long long BB = B % g;
    B /= g;
    M /= g;
    mint ans = 0; 
    if (N >= M) {
        mint kiyo = f(g, 0, X, M);
        ans += (N / M) * kiyo;
        N %= M;
    }
    for (const auto data : zawa::SqrtHeuristicArithmetic(A, B, M, N)) {
        if (X == 1)
            ans += mint{data.n};
        else {
            long long ar = data.a * g;
            assert(ar != 0);
            if (ar > 0)
                ans += f(ar, data(0)*g, X, data.n);
            else 
                ans += f(-ar, data(data.n - 1)*g, X, data.n);
        }
    }
    ans *= mint{X}.pow(BB);
    cout << ans.val() << '\n';
}
int main() {
#ifdef ATCODER
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--)
        solve();
#else
    cout << "Hello World\n";
#endif
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.13/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.13/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.13/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.13/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/modint: line -1: no such header

Back to top page