提出 #46440363

---

ソースコード 拡げる

/*
Author : Hocky Yudhiono
Sel 10 Okt 2023 10:17:32
*/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long long LL;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef pair<ll, ll> PLL;
typedef pair<ll, ll> pll;
typedef long double ld;

#define rep(i, a, b) for(LL i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define popf pop_front
#define pf push_front
#define popb pop_back
#define pb push_back
#define fi first
#define se second

const double EPS = 1e-9;
const int INFMEM = 63;

// Do dir^1 to get reverse direction
const int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
const int dy[8] = {1, -1, 0, 0, 1, -1, -1, 1};
const char dch[4] = {'R', 'L', 'D', 'U'};

// Do (dir + 2)%4 to get reverse direction
// const int dx[8] = {-1,0,1,0,-1,1,1,-1};
// const int dy[8] = {0,1,0,-1,1,1,-1,-1};
// const char dch[4] = {'U','R','D','L'};
const double PI = 3.141592653589793;

inline void fasterios() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
}
#define endl '\n'
const int MOD = 998244353;

template<int MOD>
class ModInt {
 public:
  int v;

  ModInt() : v(0) {}
  ModInt(long long _v) {
    v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
    if (v < 0) v += MOD;
  }

  friend bool operator==(const ModInt &a, const ModInt &b) { return a.v == b.v; }
  friend bool operator!=(const ModInt &a, const ModInt &b) { return a.v != b.v; }
  friend bool operator<(const ModInt &a, const ModInt &b) { return a.v < b.v; }
  friend bool operator<=(const ModInt &a, const ModInt &b) { return a.v <= b.v; }
  friend bool operator>(const ModInt &a, const ModInt &b) { return a.v > b.v; }
  friend bool operator>=(const ModInt &a, const ModInt &b) { return a.v >= b.v; }

  ModInt& operator+=(const ModInt &a) {
    if ((v += a.v) >= MOD) v -= MOD;
    return *this;
  }
  ModInt& operator-=(const ModInt &a) {
    if ((v -= a.v) < 0) v += MOD;
    return *this;
  }
  ModInt& operator*=(const ModInt &a) {
    v = 1ll * v * a.v % MOD;
    return *this;
  }
  ModInt& operator/=(const ModInt &a) {
    return (*this) *= inverse(a);
  }

  friend ModInt pow(ModInt a, long long x) {
    ModInt res = 1; assert(x >= 0);
    for (; x; x /= 2, a *= a) if (x & 1) res *= a;
    return res;
  }
  friend ModInt inverse(ModInt a) {
    assert(a.v != 0);
    return pow(a, MOD - 2);
  }

  ModInt operator+() const { return ModInt(v); }
  ModInt operator-() const { return ModInt(-v); }
  ModInt operator++() const { return *this += 1; }
  ModInt operator--() const { return *this -= 1; }

  friend ModInt operator+(ModInt a, const ModInt &b) { return a += b; }
  friend ModInt operator-(ModInt a, const ModInt &b) { return a -= b; }
  friend ModInt operator*(ModInt a, const ModInt &b) { return a *= b; }
  friend ModInt operator/(ModInt a, const ModInt &b) { return a /= b; }

  friend istream& operator>>(istream &is, ModInt &v) { is >> v.v; return is; }
  friend ostream& operator<<(ostream &os, const ModInt &v) { os << v.v; return os; }
};

using Mint = ModInt<MOD>;

LL n;

LL expo(LL a, LL b, LL MODULO = (1LL << 63)) {
  // a %= MOD; // USE THIS WHEN N IS REALLY BIG!
  LL ret = 1;
  while (b > 0) {
    if (b & 1) ret = (ret * a) % MODULO;
    a = (a * a) % MODULO; b >>= 1;
  }
  return ret;
}

Mint dfs2(LL pos, LL rem, LL a, LL b) {
  int until = min(min(9LL, a - 1), b - 1);
  if (pos == 0) {
    if (rem != 0) return 0;
    return until + 1;
  }
  LL selisih = expo(a, pos) - expo(b, pos);
  Mint ret = 0;
  for (LL i = 0; i <= until; i++) {
    if (rem < i * selisih) break;
    ret += dfs2(pos - 1, rem - i * selisih, a, b);
  }
  // cout << pos << " " << rem << " " << a << " " << b << endl;
  // cout << "Return dfs2 " << ret << endl;
  return ret;
}

Mint dfs(LL pos, LL rem) {
  Mint ret = 0;
  for (LL a = 3; a <= n; a++) {
    if (expo(a, pos) - expo(a - 1, pos) > rem) break;
    for (LL b = a - 1; b >= 2; b--) {
      LL selisih = expo(a, pos) - expo(b, pos);
      if (selisih > rem) break;
      LL until = min(min(9LL, a - 1), b - 1);
      // cout << a << " " << b << " " << rem << " " << pos << " " << selisih << " " << until << endl;
      for (LL i = 1; i <= until; i++) {
        if (rem < i * selisih) break;
        ret += dfs2(pos - 1, rem - i * selisih, a, b);
      }
    }
  }
  // cout << "Return " << ret << endl;
  return ret;
}

int main() {
  fasterios();
  LL x; cin >> n >> x;
  // Cari yang satu pair
  // k = 1
  Mint ans = 0;
  // cari faktor dari x
  for (int i = 1; i < 10; i++) {
    if (x % i) continue;
    LL selisih = x / i;
    // cout << selisih << endl;
    const LL LIM = 200100;
    LL curans = 0;
    for (int a = 2; a <= min(LIM, n); a++) {
      int b = a - selisih;
      if (a <= 0) continue;
      if (i >= b || i >= a || i >= n) continue;
      curans += min(min(a, b), 10);
    }
    ans += curans;
    LL kiri = LIM + 1;
    LL kanan = n;
    if (kiri <= kanan) {
      ans += Mint((kanan - kiri + 1) * 10);
    }
  }
  // cout << ans << endl;
  // return 0;
  // cout << "k = 1 " << ans << endl;
  // ans = 0;
  // Cari yang dua pangkat
  for (int i = 2; i <= 12; i++) {
    ans += dfs(i, x);
    // cout << "k = i " << i << " " << ans << endl;
  }
  cout << ans << endl;
}

提出情報

ジャッジ結果