#663740 (C++14) No.1529 Constant Lcm

提出ソース

結果

問題	No.1529 Constant Lcm
ユーザー	あんこ
提出日時	2021-06-04 22:11:28
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	9,884 bytes
コンパイル時間	1,718 ms
コンパイル使用メモリ	173,280 KB
実行使用メモリ	25,332 KB
最終ジャッジ日時	2024-11-19 15:03:28
合計ジャッジ時間	63,247 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 13,632 KB
testcase_01	AC	9 ms 17,716 KB
testcase_02	AC	2 ms 13,132 KB
testcase_03	AC	2 ms 13,136 KB
testcase_04	AC	2 ms 16,608 KB
testcase_05	AC	2 ms 13,632 KB
testcase_06	AC	2 ms 13,640 KB
testcase_07	AC	2 ms 14,288 KB
testcase_08	AC	2 ms 13,632 KB
testcase_09	AC	2 ms 14,500 KB
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	AC	484 ms 11,812 KB
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	TLE	-
testcase_21	TLE	-
testcase_22	TLE	-
testcase_23	TLE	-
testcase_24	TLE	-
testcase_25	TLE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

#define fi first
#define se second
#define rng(a) a.begin(), a.end()
#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))
// #define popcount __builtin_popcountll
// #define uni(x) x.erase(unique(rng(x)),x.end())
// #define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define vec vector
#define pque priority_queue
#define removeerase(x) x.erase(remove(rng(x), 0), x.end());
#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)

const double PI = 3.14159265358979323846;
const double EPS = 1e-14;
const int IINF = 0x1fffffff;
const ll INF = 0x1fffffffffffffff; // or 0x7fffffffffff
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;

#ifdef LOCAL
#define debug(...)                                                             \
  std::cerr << "LINE: " << __LINE__ << "  [" << #__VA_ARGS__ << "]:",          \
      debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << std::endl; }

template <typename Head, typename... Tail> void debug_out(Head h, Tail... t) {
  std::cerr << " " << h;
  if (sizeof...(t) > 0)
    std::cout << " :";
  debug_out(t...);
}

long long gcd(long long a, long long b) {
  if (b)
    return gcd(b, a % b);
  return a;
}
long long lcm(long long a, long long b) { return a * b / gcd(a, b); }
long long extgcd(long long a, long long b, long long &x, long long &y) {
  long long g = a;
  x = 1;
  y = 0;
  if (b) {
    g = extgcd(b, a % b, y, x);
    y -= a / b * x;
  }
  return g;
}
long long invmod(long long a, long long mod) {
  long long x, y;
  extgcd(a, mod, x, y);
  x %= mod;
  if (x < 0)
    x += mod;
  return x;
}
// 2のとき大きすぎるとビットが移動して0になってしまう
long long powmod(long long e, long long x, long long mod) {
  long long prod = 1;
  long long cur = e;
  while (x > 0) {
    if (x & 1)
      prod = prod * cur % mod;
    cur = cur * cur % mod;
    x >>= 1;
  }
  return prod;
}

vector<ll> eratosthenes(long long n) {
  vec<ll> primes(n);
  for (long long i = 2; i < n; ++i)
    primes[i] = i;
  for (long long i = 2; i * i < n; ++i) {
    if (primes[i])
      for (long long j = i * i; j < n; j += i)
        primes[j] = 0;
  }
  auto p = remove(primes.begin(), primes.end(), 0);
  primes.erase(p, primes.end());
  return primes;
}
long long fac(long long n, long long mod) {
  if (n >= mod)
    return 0;
  if (n)
    return (n * fac(n - 1, mod)) % mod;
  return 1;
}
vector<long long> facmod;
vector<long long> facinvmod;
long long combination(long long n, long long k, long long mod) {
  // 階乗やその逆元をメモ化すると速い
  // でかいやつはnCk/2^Nをパスカルの三角形で作る
  long long res = fac(n, mod);
  res = (res * invmod(fac(k, mod), mod)) % mod;
  res = (res * invmod(fac(n - k, mod), mod)) % mod;
  return res;
}
// x % m[i] = r[i] % m[i] を満たす正で最小の x を返す
// i!=j に対して gcd(m[i], m[j])=1 であると仮定
// とりあえず解の存在判定は保留
long long garner(vector<long long> r, vector<long long> m) {
  int n = r.size();
  long long m_prod = 1;      // m_prod には m[i] の積を入れていく
  long long x = r[0] % m[0]; // 最初の条件を満たすような x の初期値
  for (int i = 1; i < n; i++) {
    // cout << r[i-1] << " " << m[i-1] << " " << x << endl;
    m_prod *= m[i - 1]; // m の累積積を更新
    long long t = ((r[i] - x) * invmod(m_prod, m[i])) % m[i];
    if (t < 0)
      t += m[i];
    x += t * m_prod; // x を更新
  }
  return x;
}
// false: composite, true: probably prime
// bool MillarRabin_sub(ll n, ll random) {
// 	ll d = n-1;
// 	while(d % 2 == 0) {
// // 		d /= 2;
// 		cout << random << " " << powmod(random, d, n) << endl;
// 		if (powmod(random, d, n) == n-1) {
// 			return true;
// 		}
// 	}
// 	if (powmod(random, d, n) == 1) return true;
// 	return false;
// }
// bool MillarRabin(ll n) {
// 	random_device rd{};
// 	vector<uint32_t> vec(20);
// 	generate(vec.begin(), vec.end(), ref(rd));
// 	mt19937 mt(seed_seq(vec.begin(), vec.end()));
// 	bool ret = true;
// 	rep(i,0,20) {
// 		vec[i] %= n; if (vec[i] == 0) continue;
// 		cout << MillarRabin_sub(n, random) << endl;
// 		if (!MillarRabin_sub(n, random)) return false;
// 	}
// 	return true;
// }

// vector<int> a = {1, 14, 32, 51, 51, 51, 243, 419, 750, 910};

// // index が条件を満たすかどうか
// bool isOK(int index, int key) {
//     if (a[index] >= key) return true;
//     else return false;
// }
// // 汎用的な二分探索のテンプレ
// int binary_search(int key) {
//     int ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
//     int ok = (int)a.size(); // 「index =
//     a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

//     /* ok と ng のどちらが大きいかわからないことを考慮 */
//     while (abs(ok - ng) > 1) {
//         int mid = (ok + ng) / 2;

//         if (isOK(mid, key)) ok = mid;
//         else ng = mid;
//     }
//     return ok;
// }

template <class T0, class T1> class SegmentTree {
  void eval(int k, int len) {
    // 定数倍高速化
    if (lazy[k] == u1)
      return;
    // len個分のlazy[k]を評価
    node[k] = g(node[k], p(lazy[k], len));
    if (k < N - 1) {
      // 最下段でなければ下のlazyに伝搬
      lazy[2 * k + 1] = f1(lazy[2 * k + 1], lazy[k]);
      lazy[2 * k + 2] = f1(lazy[2 * k + 1], lazy[k]);
    }
    lazy[k] = u1;
  }

  // k番目のノード[l, r)について、[a, b)の範囲にxを作用
  void update(int a, int b, T1 x, int k, int l, int r) {
    eval(k, r - l);
    if (b <= l || r <= a)
      return;
    if (a <= l && r <= b) {
      lazy[k] = f1(lazy[k], x);
      eval(k, r - l);
      return;
    }
    update(a, b, x, 2 * k + 1, l, (l + r) / 2);
    update(a, b, x, 2 * k + 2, (l + r) / 2, r);
    node[k] = f0(node[2 * k + 1], node[2 * k + 2]);
  }

  // k番目のノード[l, r)について、[a, b)のクエリを求める
  T0 query(int a, int b, int k, int l, int r) {
    eval(k, r - l);
    if (b <= l || r <= a)
      return u0;
    if (a <= l && r <= b)
      return node[k];
    T0 vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
    T0 vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
    return f0(vl, vr);
  }

public:
  int sz, N;
  vector<T0> node;
  vector<T1> lazy;
  // T0上の演算、単位元
  using F0 = function<T0(T0, T0)>;
  F0 f0;
  T0 u0;
  // T1上の演算、単位元
  using F1 = function<T1(T1, T1)>;
  F1 f1;
  T1 u1;
  // 作用
  using G = function<T0(T0, T1)>;
  G g;
  // 多数のt1(T1)にするf1の合成 つまりt1^len
  using P = function<T1(T1, int)>;
  P p;

  SegmentTree(const vector<T0> &a, F0 f0, T0 u0, F1 f1, T1 u1, G g, P p)
      : sz(a.size()), f0(f0), u0(u0), f1(f1), u1(u1), g(g), p(p) {
    for (N = 1; N < sz; N *= 2)
      ;
    node.resize(2 * N - 1);
    lazy.resize(2 * N - 1, u1);
    for (int i = 0; i < sz; i++)
      node[N - 1 + i] = a[i];
    for (int i = N - 2; i >= 0; i--)
      node[i] = f0(node[2 * i + 1], node[2 * i + 2]);
  }

  // [a, b)にxを作用
  void update(int a, int b, T1 x) {
    assert(0 <= a && a < b && b <= sz);
    update(a, b, x, 0, 0, N);
  }

  void update(int a, T1 x) { update(a, a + 1, x); }

  // [a, b)
  T0 query(int a, int b) { return query(a, b, 0, 0, N); }

  T0 query(int a) { return query(a, a + 1); }
};

// 逆順になる reverse(rng(ans));
// vector<ll> G[100000];
// cout << fixed << setprecision(15) << y << endl;
// cout << bitset<20>(i) << endl;
// fill(distance[0], distance[row], INF);
// __builtin_popcount()
// stoi(S[j], 0, 2)
// for (ll i = 0;i < (ll)s.size() - k;i++)
// ll dp[桁数][未満フラグ][条件を満たしているか]
// stoi stoll
// bit全探索 n進数全探索
// while (t > 0) cc += t % 9, t /= 9;
// priority_queue<ll> que; que.push(3); que.top(); que.pop();
// rep(i,C)rep(j,C) if(i != j) rep(k,C) if(i != k && j != k)
// 始点終点をデータに含ませる
// memory restriction RE -> CE
// forr 逆順ループsnippet
// 座標 上下の回数さえ分かれば組合せ問題
// set 順序付き集合 distance(set.begin(), itr)でオフセットがわかる
// set s : for(int x : s) for(int y : s) for(int z : s)
// const int di[4] = {-1, 0, 1, 0};
// const int dj[4] = {0, -1, 0, 1};
// const string let = "ULDR";
// 逆順ソートsort(cand.rbegin(), cand.rend());
// int ok = 0, ng = 1e9+1;
// auto check = [&](int x) -> bool {
// 	set<int> s;
// 	rep(i,0,N) {
// 		int tmp = 0;
// 		rep(j,0,5) {
// 			if (A[i][j] >= x) tmp |= 1 << j;
// 		}
// 		s.insert(tmp);
// 	}
// 	for (int x : s) for (int y : s) for (int z : s) {
// 		if ((x | y | z) == 31) return true;
// 	}
// 	return false;
// };

// while(abs(ok - ng) > 1) {
// 	int mid = (ok + ng) / 2;
// 	if (check(mid)) ok = mid;
// 	else ng = mid;
// }
// cout << ok << endl;
// dp[500][500] はllではなくintにすること
// chmin/chmaxは型をあわせないといけない
// priority_queue 最上位以外アクセス許可していない
// priority_queue<l_l, vector<l_l>, greater<l_l>>
// multiset イテレータ書き込み出来ない

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll N;
  cin >> N;
  vec<ll> primes = eratosthenes(N);
  vec<ll> num(primes.size(), 0);
  for (ll i = 1; i < N; i++) {
    ll tmp = i * (N - i);
    // cout << tmp << " ";
    rep(j, 0, primes.size()) {
      ll cnt = 0;
      while (tmp % primes[j] == 0) {
        tmp /= primes[j];
        cnt++;
      }
      chmax(num[j], cnt);
      // cout << cnt << " ";
    }
    // cout << endl;
  }
  ll ans = 1;
  rep(i, 0, primes.size()) {
    ans = (ans * powmod(primes[i], num[i], MOD2)) % MOD2;
  }
  cout << ans << endl;

  return 0;
}

yukicoder

結果

テストケース

ソースコード