結果
| 問題 | No.3607 Sum of Powers of GCDs |
| コンテスト | |
| ユーザー |
 ぽえ
|
| 提出日時 | 2026-07-31 02:22:24 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 471 ms / 2,500 ms |
| + 803µs | |
| コード長 | 6,974 bytes |
| 記録 | |
| コンパイル時間 | 2,105 ms |
| コンパイル使用メモリ | 345,608 KB |
| 実行使用メモリ | 46,208 KB |
| 最終ジャッジ日時 | 2026-07-31 20:54:12 |
| 合計ジャッジ時間 | 6,375 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 11 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#line 2 "math/enumerate-quotient.hpp"
#line 2 "math/isqrt.hpp"
#include <cmath>
using namespace std;
// floor(sqrt(n)) を返す (ただし n が負の場合は 0 を返す)
long long isqrt(long long n) {
if (n <= 0) return 0;
long long x = sqrt(n);
while ((x + 1) * (x + 1) <= n) x++;
while (x * x > n) x--;
return x;
}
#line 4 "math/enumerate-quotient.hpp"
namespace EnumerateQuotientImpl {
long long fast_div(long long a, long long b) { return 1.0 * a / b; };
long long slow_div(long long a, long long b) { return a / b; };
} // namespace EnumerateQuotientImpl
// { (q, l, r) : forall x in (l,r], floor(N/x) = q }
// を引数に取る関数f(q, l, r)を渡す。範囲が左に半開なのに注意
// 商は小さい方から走査する
template <typename T, typename F>
void enumerate_quotient(T N, const F& f) {
T sq = isqrt(N);
#define FUNC(d) \
T upper = N, quo = 0; \
while (upper > sq) { \
T thres = d(N, (++quo + 1)); \
f(quo, thres, upper); \
upper = thres; \
} \
while (upper > 0) { \
f(d(N, upper), upper - 1, upper); \
upper--; \
}
if (N <= 1e12) {
FUNC(EnumerateQuotientImpl::fast_div);
} else {
FUNC(EnumerateQuotientImpl::slow_div);
}
#undef FUNC
}
/**
* @brief 商の列挙
*/
#line 2 "modint/modint.hpp"
template <int mod>
struct ModInt {
int x;
ModInt() : x(0) {}
ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
ModInt &operator+=(const ModInt &p) {
if ((x += p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator-=(const ModInt &p) {
if ((x += mod - p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator*=(const ModInt &p) {
x = (int)(1LL * x * p.x % mod);
return *this;
}
ModInt &operator/=(const ModInt &p) {
*this *= p.inverse();
return *this;
}
ModInt operator-() const { return ModInt(-x); }
ModInt operator+() const { return ModInt(*this); }
ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
bool operator==(const ModInt &p) const { return x == p.x; }
bool operator!=(const ModInt &p) const { return x != p.x; }
ModInt inverse() const {
int a = x, b = mod, u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return ModInt(u);
}
ModInt pow(int64_t n) const {
ModInt ret(1), mul(x);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; }
friend istream &operator>>(istream &is, ModInt &a) {
int64_t t;
is >> t;
a = ModInt<mod>(t);
return (is);
}
int get() const { return x; }
static constexpr int get_mod() { return mod; }
};
/**
* @brief modint
*/
#line 2 "multiplicative-function/divisor-multiple-transform.hpp"
#include <map>
#include <vector>
using namespace std;
#line 2 "prime/prime-enumerate.hpp"
// Prime Sieve {2, 3, 5, 7, 11, 13, 17, ...}
vector<int> prime_enumerate(int N) {
vector<bool> sieve(N / 3 + 1, 1);
for (int p = 5, d = 4, i = 1, sqn = sqrt(N); p <= sqn; p += d = 6 - d, i++) {
if (!sieve[i]) continue;
for (int q = p * p / 3, r = d * p / 3 + (d * p % 3 == 2), s = 2 * p,
qe = sieve.size();
q < qe; q += r = s - r)
sieve[q] = 0;
}
vector<int> ret{2, 3};
for (int p = 5, d = 4, i = 1; p <= N; p += d = 6 - d, i++)
if (sieve[i]) ret.push_back(p);
while (!ret.empty() && ret.back() > N) ret.pop_back();
return ret;
}
#line 8 "multiplicative-function/divisor-multiple-transform.hpp"
struct divisor_transform {
template <typename T>
static void zeta_transform(vector<T> &a) {
int N = a.size() - 1;
auto sieve = prime_enumerate(N);
for (auto &p : sieve)
for (int k = 1; k * p <= N; ++k) a[k * p] += a[k];
}
template <typename T>
static void mobius_transform(vector<T> &a) {
int N = a.size() - 1;
auto sieve = prime_enumerate(N);
for (auto &p : sieve)
for (int k = N / p; k > 0; --k) a[k * p] -= a[k];
}
template <typename I, typename T>
static void zeta_transform(map<I, T> &a) {
for (auto p = rbegin(a); p != rend(a); p++)
for (auto &x : a) {
if (p->first == x.first) break;
if (p->first % x.first == 0) p->second += x.second;
}
}
template <typename I, typename T>
static void mobius_transform(map<I, T> &a) {
for (auto &x : a) {
for (auto p = rbegin(a); p != rend(a); p++) {
if (x.first == p->first) break;
if (p->first % x.first == 0) p->second -= x.second;
}
}
}
};
struct multiple_transform {
template <typename T>
static void zeta_transform(vector<T> &a) {
int N = a.size() - 1;
auto sieve = prime_enumerate(N);
for (auto &p : sieve)
for (int k = N / p; k > 0; --k) a[k] += a[k * p];
}
template <typename T>
static void mobius_transform(vector<T> &a) {
int N = a.size() - 1;
auto sieve = prime_enumerate(N);
for (auto &p : sieve)
for (int k = 1; k * p <= N; ++k) a[k] -= a[k * p];
}
template <typename I, typename T>
static void zeta_transform(map<I, T> &a) {
for (auto &x : a)
for (auto p = rbegin(a); p->first != x.first; p++)
if (p->first % x.first == 0) x.second += p->second;
}
template <typename I, typename T>
static void mobius_transform(map<I, T> &a) {
for (auto p1 = rbegin(a); p1 != rend(a); p1++)
for (auto p2 = rbegin(a); p2 != p1; p2++)
if (p2->first % p1->first == 0) p1->second -= p2->second;
}
};
/**
* @brief 倍数変換・約数変換
* @docs docs/multiplicative-function/divisor-multiple-transform.md
*/
using mint = ModInt<998244353>;
struct query { int n, m, k; };
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
vector<query> queries(T);
int M = 0;
for (int i=0; i<T; i++) {
cin >> queries[i].n >> queries[i].m >> queries[i].k;
M = max(M, queries[i].m);
}
vector<vector<mint>> pref(10, vector<mint>(M+10));
for (int i=1; i<=M; i++) {
mint pow = 1;
for (int j=0; j<10; j++) {
pow *= i;
pref[j][i] = pow;
}
}
for (int i=0; i<10 ;i++) {
divisor_transform::mobius_transform(pref[i]);
for (int j=1; j<=M; j++) pref[i][j] += pref[i][j-1];
}
for (int i=0; i<T; i++) {
auto [n, m, k] = queries[i];
mint ans = 0;
enumerate_quotient(m, [&](long long q, long long l, long long r) { ans+= (pref[k-1][r]-pref[k-1][l])*mint(q).pow(n);});
cout << ans << '\n';
}
}