#872740 (C++17) No.2318 Phys Bone Maker

提出ソース

結果

問題	No.2318 Phys Bone Maker
ユーザー	7iz6
提出日時	2023-05-26 22:55:36
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	9,711 bytes
コンパイル時間	1,840 ms
コンパイル使用メモリ	161,476 KB
実行使用メモリ	12,308 KB
最終ジャッジ日時	2023-08-26 13:15:28
合計ジャッジ時間	6,638 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 7,228 KB
testcase_01	AC	5 ms 7,060 KB
testcase_02	TLE	-
testcase_03	--	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-

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

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <set>
#include <tuple>
#include <bitset>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <limits>
#include <iomanip>
#include <cassert>
#include <sstream>
#include <random>
#include <memory>

// #include <boost/container/flat_set.hpp> // insert: O(log N), erase: O(1)
// using namespace boost::container

// #include <atcoder/all>
// using namespace atcoder;
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define ll long long
#define pii std::pair<int, int>
#define pll std::pair<ll, ll>
#define vi std::vector<int>
#define vii std::vector<std::pair<int, int>>
#define vll std::vector<std::pair<ll, ll>>
#define vvi std::vector<std::vector<int>>
#define vvl std::vector<std::vector<ll>>
#define ALL(v) (v).begin(), (v).end()
#define OUT(v) for(int i = 0, n = (v).size(); i < n; i++) cout << v[i] << " \n"[i+1==n]

// const int MOD = 1e9 + 7;
const int MOD = 998244353;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double eps = 1e-6;
constexpr double PI = std::acos(-1);
const int di[4] = {0, 1, 0, -1};
const int dj[4] = {1, 0, -1, 0};
const int di8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dj8[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<typename T, typename U>
bool operator==(const pair<T, U>& lhs, const pair<T, U>& rhs) {
  return (lhs.first == rhs.first && lhs.second == rhs.second);
}

bool is_out(int i, int j, int n) {
  return (i < 0 || j < 0 || i >= n || j >= n);
}

bool is_out(int i, int j, int h, int w) {
  return (i < 0 || j < 0 || i >= h || j >= w);
}

template <typename T>
bool PN(T x){if(x <= 1)return false;if(x == 2)return true;for(ll i = 2; i * i <= x; i++)if(x % i == 0)return false; return true;}
ll Comb(int n, int i){ll ans=1;if(i>n||i<0)return 0;if(i==0||i==n)return 1;else{for(int j=1;j<=i;++j){ans*=(n+1-j);ans/=j;ans%=MOD;}}return ans;}
template <typename T>T gcd(T a, T b){if (a < b)std::swap(a,b);return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){if(b>a)std::swap(a,b);T g=gcd(a,b);return a/g*b;}
template <typename T> void chmax(T& a, T b) {a=b>a?b:a;}
template <typename T> void chmin(T& a, T b) {a=b<a?b:a;}

// 約数列挙
template<typename T> vector<T> divisor(T n) {
	vector<T> res;
	for (long long  i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			res.push_back(i);
			if (i != n / i) {
					res.push_back(n / i);
			}
		}
	}
	sort(res.begin(), res.end());
	return res;
}


template <class T>
T modpow(T a, T b, T mod) {
	// a^b mod m を求める
	long long p=1,q=a;
	for(int i = 0; i < 30; i++) {
		if((b & (1LL << i)) != 0) p*=q, p%=mod;
		q*=q; q%=mod;
	}
	return p;
}

template <class T>
T Div(T a, T b, T m) {
	return (a * modpow(b, m - 2, m)) % m;
}

// 区間更新遅延評価セグ木(葉の値を別の値に更新)
// 区間の最大値を返す(RMQ)。
namespace seg_update
{
	using S = ll;
	using F = ll;
	const ll ID = 1e18 + 1;
	const int N_SEG = 1e5 + 5;
	S op(S l, S r) { return max(l, r); }
	S e() { return 0; }
	S mapping(F l, S r) { return l; }
	F composition(F f, F g) { return (f == ID) ? g : f; }
	F id() { return ID; }
	// atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(N_SEG);
}

// 区間加算遅延評価セグ木(葉の値を定数倍+定数加算) ai <- ai * a + b;
// 区間の和を返す。
namespace seg_add{
	struct S {
		ll a;
		int size;
	};
	struct F {
		ll a, b;
	};
	S op(S l, S r) { return S{l.a + r.a, l.size + r.size}; }
	S e() { return S{0, 0}; }
	S mapping(F l, S r) { return S{r.a * l.a + r.size * l.b, r.size}; }
	F composition(F f, F g) { return F{g.a * f.a, g.b * f.a + f.b}; }
	F id() { return {1, 0}; }
}


/// @brief 重み付き Union-Find 木
/// @tparam Type 重みの表現に使う型
/// @note 1.1 シンプルな実装
/// @see https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/weighted-union-find
template <class Type>
class WeightedUnionFind
{
public:

	WeightedUnionFind() = default;

	/// @brief 重み付き Union-Find 木を構築します。
	/// @param n 要素数
	explicit WeightedUnionFind(size_t n)
		: m_parents(n)
		, m_sizes(n, 1)
		, m_diffWeights(n)
	{
		std::iota(m_parents.begin(), m_parents.end(), 0);
	}

	/// @brief 頂点 i の root のインデックスを返します。
	/// @param i 調べる頂点のインデックス
	/// @return 頂点 i の root のインデックス
	int find(int i)
	{
		if (m_parents[i] == i)
		{
			return i;
		}

		const int root = find(m_parents[i]);

		m_diffWeights[i] += m_diffWeights[m_parents[i]];

		// 経路圧縮
		return (m_parents[i] = root);
	}

	/// @brief a のグループと b のグループを統合します。
	/// @param a 一方のインデックス
	/// @param b 他方のインデックス
	/// @param w (b の重み) - (a の重み)
	void merge(int a, int b, Type w)
	{
		w += weight(a);
		w -= weight(b);

		a = find(a);
		b = find(b);

		if (a != b)
		{
			// union by size (小さいほうが子になる）
			if (m_sizes[a] < m_sizes[b])
			{
				std::swap(a, b);
				w = -w;
			}

			m_sizes[a] += m_sizes[b];
			m_parents[b] = a;
			m_diffWeights[b] = w;
		}
	}

	/// @brief (b の重み) - (a の重み) を返します。
	/// @param a 一方のインデックス
	/// @param b 他方のインデックス
	/// @remark a と b が同じグループに属さない場合の結果は不定です。
	/// @return (b の重み) - (a の重み)
	Type diff(int a, int b)
	{
		return (weight(b) - weight(a));
	}

	/// @brief a と b が同じグループに属すかを返します。
	/// @param a 一方のインデックス
	/// @param b 他方のインデックス
	/// @return a と b が同じグループに属す場合 true, それ以外の場合は false
	bool connected(int a, int b)
	{
		return (find(a) == find(b));
	}

	/// @brief i が属するグループの要素数を返します。
	/// @param i インデックス
	/// @return i が属するグループの要素数
	int size(int i)
	{
		return m_sizes[find(i)];
	}

private:

	// m_parents[i] は i の 親,
	// root の場合は自身が親
	std::vector<int> m_parents;

	// グループの要素数 (root 用)
	// i が root のときのみ, m_sizes[i] はそのグループに属する要素数を表す
	std::vector<int> m_sizes;

	// 重み
	std::vector<Type> m_diffWeights;

	Type weight(int i)
	{
		find(i); // 経路圧縮
		return m_diffWeights[i];
	}
};

template<typename T>
size_t LIS(const std::vector<T>& v) {
  size_t sz = v.size();
  std::vector<T> ret;
  for(const T& val: v) {
    auto it = std::lower_bound(ret.begin(), ret.end(), val);
    if(it == ret.end()) {
      ret.push_back(val);
    } else {
      *it = val;
    }
  }
  return ret.size();
}

struct UndirectedGraph {
  std::vector<std::vector<pair<int, long long>>> G;
  std::vector<int> u, v;
  std::vector<long long> w;
  int n;
  int m;

  UndirectedGraph(int _n, int _m) {
    n = _n;
    m = _m;
    u.resize(n);
    v.resize(n);
    w.resize(n, 1);
    G.resize(n + 10);
  }

  void read_uv() {
    for(int i = 0; i < m; i++) {
      cin >> u[i] >> v[i];
      u[i]--;
      v[i]--;
      G[u[i]].push_back({v[i], 1});
      G[v[i]].push_back({u[i], 1});
    }
  }

  void read_uvw() {
    for(int i = 0; i < m; i++) {
      cin >> u[i] >> v[i] >> w[i];
      u[i]--;
      v[i]--;
      G[u[i]].push_back({v[i], w[i]});
      G[v[i]].push_back({u[i], w[i]});
    }
  }

  // return distance and pre points
  std::pair<std::vector<long long>, std::vector<int>> dijkstra(int s) {
    typedef std::pair<long long, pair<int,int> > Edge;
    std::vector<long long> dist(n, LINF);
    std::vector<int> pre(n, -1);
    dist[s] = 0;
    pre[s] = s;
    std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge> > pq;
    pq.push(Edge{0, {s, -1}});

    while(!pq.empty()) {
      Edge e = pq.top(); pq.pop();
      int from = e.second.first;
      long long cost = e.first;

      if(dist[from] < cost) continue;

      for(auto[nx, weight]: G[from]) {
        if(dist[nx] > dist[from] + weight) {
          dist[nx] = dist[from] + weight;
          pq.push(Edge{dist[nx], {nx, from}});
          pre[nx] = from;
        }
      }
    }

    return {dist, pre};
  }
};


void solve(){
  long long n;
  cin >> n;
  long long n2 = n;
  vector<long long> div = divisor(n);
  vector<int> cnt(1000001, 0);
  for(long long i = 2; i * i <= n; i++) {
    for(long long j = i; j * j <= n; j += i) {
      cnt[j]++;
    }
  }
  vector<int> primes;
  for(int i = 2; i <= 1000000; i++) {
    if(cnt[i] == 1) primes.push_back(i);
  }
  map<long long, long long> dp;
  dp[1] = 1;
  vector<pair<long long, int>> v;
  for(int p: primes) {
    int cnt = 0;
    while(n2%p==0) {
      cnt++;
      n2/=p;
    }
    if(cnt>0) v.push_back({p, cnt});
  }
   if(n2 != 0) v.push_back({n2, 1});
  vector<long long> muls;
  muls.push_back(1);
  for(auto p: v) {
    int msize = muls.size();
    long long val = 1;
    for(int i = 0; i < p.second; i++) {
      val *= (ll)p.first;
      for(int j = 0; j < msize; j++) muls.push_back((ll)muls[j] * val);
    }
  }
  sort(muls.begin(), muls.end());
  muls.erase(unique(muls.begin(), muls.end()), muls.end());
  for(auto val: muls) cerr << val << " ";
  cerr << endl;
  cerr << muls.size() << " " << div.size() << endl;
  for(long long d: div) {
    for(long long mul: muls) {
      if(long long l = lcm(d, mul); l > d) {
        dp[l] += dp[d];
        dp[l] %= MOD;
      }
    }
  }
  cout << dp[n] << endl;
}

int main(void){
	
	solve();
	return 0;
}

yukicoder

結果

テストケース

ソースコード