結果
| 問題 |
No.1330 Multiply or Divide
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:59:19 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,351 bytes |
| コンパイル時間 | 951 ms |
| コンパイル使用メモリ | 95,252 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:00:28 |
| 合計ジャッジ時間 | 5,926 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 1 TLE * 1 -- * 44 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <utility>
#include <algorithm>
// Function to calculate v_P(n), the exponent of prime P in the factorization of n.
// v_P(n) counts how many times n is divisible by P.
long long vp(long long n, long long p) {
// Base cases and edge cases
if (n == 0) return 1e18; // A large number to represent practically infinite factors for 0
if (p <= 1) return 0; // P must be a prime > 1. Division by 1 is trivial.
long long count = 0;
// Keep dividing n by p as long as it's divisible
while (n > 0 && n % p == 0) {
count++;
n /= p;
}
return count;
}
// Use a large value for infinity for costs.
// The maximum possible cost is likely bounded, but use a sufficiently large value.
// Given constraints, paths are unlikely to exceed cost that fits in long long.
// 4e18 is close to max long long / 2, safe for additions.
const long long INF = 4e18;
int main() {
// Use faster I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Number of elements in sequence A
long long M; // Threshold value
long long P; // Prime number P
std::cin >> N >> M >> P;
// Use a map to store the minimum cost C_k required to achieve multiplication by B_k.
// B_k is defined as A_i / P^{v_P(A_i)}.
// Key: B_k value, Value: minimum cost C_k = 1 + v_P(A_i).
std::map<long long, long long> min_cost_for_B;
for (int i = 0; i < N; ++i) {
long long current_A;
std::cin >> current_A;
// Problem constraints state A_i >= 1. Skip if non-positive for robustness.
if (current_A <= 0) continue;
// Calculate exponent of P in current_A's factorization
long long e_i = vp(current_A, P);
// Calculate B_i = A_i / P^{e_i} using repeated division to avoid large powers/floating point issues.
long long B_i = current_A;
for(long long k = 0; k < e_i; ++k) {
// This check should not be necessary if A_i >= 1 and P >= 2.
if (B_i == 0) break;
B_i /= P;
}
// The total cost for choosing A_i is 1 (for multiplication) + e_i (for divisions by P).
long long cost = 1 + e_i;
// Check if this B_i value is already in the map.
if (min_cost_for_B.count(B_i)) {
// If yes, update the cost if the current A_i provides a cheaper way to get this B_i.
min_cost_for_B[B_i] = std::min(min_cost_for_B[B_i], cost);
} else {
// If no, insert this new B_i and its associated cost into the map.
min_cost_for_B[B_i] = cost;
}
}
// Store the unique (B_k, C_k) pairs from the map into a vector for efficient iteration during Dijkstra.
std::vector<std::pair<long long, long long>> transitions;
for (auto const& [b_val, cost_val] : min_cost_for_B) {
transitions.push_back({b_val, cost_val});
}
// Priority queue for Dijkstra algorithm. Stores {cost, state} pairs.
// Uses std::greater to make it a min-priority queue based on cost.
std::priority_queue<std::pair<long long, long long>, std::vector<std::pair<long long, long long>>, std::greater<std::pair<long long, long long>>> pq;
// Map to store the minimum distance (cost) found so far to reach each state `x`.
std::map<long long, long long> dist;
// Initial state: x=1, cost=0.
// Check if the initial state 1 already exceeds M. M >= 1, so this is not possible.
// The problem implies operations continue *while* x <= M.
// Set distance to initial state 1 as 0 and push it to the priority queue.
dist[1] = 0;
pq.push({0, 1});
// Variable to store the minimum total cost found to reach any state > M. Initialize to infinity.
long long min_total_cost = INF;
// Dijkstra algorithm main loop
while (!pq.empty()) {
// Extract the state `u` with the minimum cost `current_cost` from the priority queue.
auto [current_cost, u] = pq.top();
pq.pop();
// Check if we have already found a shorter path to `u`.
// Need to use `dist.count(u)` because map access `dist[u]` creates entry with value 0 if key `u` doesn't exist.
// `dist.count(u) == 0` means distance is effectively infinity.
// If `current_cost > dist[u]`, this queue entry is outdated, skip it.
if (dist.count(u) == 0 || current_cost > dist[u]) {
continue;
}
// Optimization: If the current path's cost is already not better than the best cost found so far
// to reach the goal region (x > M), then exploring further from this state `u` cannot lead to
// a better overall solution. Prune this path.
if (current_cost >= min_total_cost) {
continue;
}
// Iterate through all possible transitions defined by the unique (B_k, C_k) pairs.
for (const auto& transition : transitions) {
long long B_k = transition.first;
long long C_k = transition.second;
// Since A_i >= 1, B_k = A_i / P^{e_i} must be >= 1. Safety check.
if (B_k <= 0) continue;
// Check if multiplying state `u` by `B_k` will result in a value exceeding `M`.
bool exceeds_M = false;
// To avoid overflow when calculating u * B_k, use property of integer division:
// For positive integers u, B_k, M: u * B_k > M is equivalent to u > M / B_k.
// This check works correctly even if u * B_k would overflow standard 64-bit integer types.
// Need to handle B_k = 0? No, B_k >= 1 guaranteed.
// If B_k > M, then for u >= 1, u * B_k will always be > M.
if (B_k > M && u >= 1) {
exceeds_M = true;
}
// Check only if B_k <= M and u > 0.
// If u = 0, result is 0, which is <= M. But u starts at 1 and is multiplied by B_k >= 1, so u >= 1 always.
else if (u > 0 && B_k > 0) {
// Calculate M / B_k using integer division.
long long M_div_Bk = M / B_k;
// If u > M / B_k, then u * B_k > M.
if (u > M_div_Bk) {
exceeds_M = true;
}
}
if (exceeds_M) {
// If the resulting value v = u * B_k exceeds M, this path reaches the goal region.
// Update the overall minimum cost found so far if this path is cheaper.
min_total_cost = std::min(min_total_cost, current_cost + C_k);
} else {
// If the resulting value v = u * B_k does not exceed M.
// Calculate the next state value `v` and the total cost `next_cost` to reach it.
long long v = u * B_k; // This multiplication is safe if check passed, v <= M potentially.
long long next_cost = current_cost + C_k;
// Check if this path to `v` is shorter than any previously found path to `v`.
// `!dist.count(v)` means `v` has not been reached before (distance is effectively INF).
if (!dist.count(v) || next_cost < dist[v]) {
// Optimization: Only explore this path if its cost `next_cost` is potentially better
// than the current best cost `min_total_cost` found to reach the goal region.
if (next_cost < min_total_cost) {
// Update the minimum distance to `v` and add/update `v` in the priority queue.
dist[v] = next_cost;
pq.push({next_cost, v});
}
}
}
}
}
// After Dijkstra algorithm finishes:
// If `min_total_cost` still holds the initial INF value, it means no path could reach a state > M.
// This corresponds to the condition where the process might repeat infinitely without exceeding M.
if (min_total_cost == INF) {
std::cout << -1 << std::endl;
} else {
// Otherwise, output the minimum total cost found.
std::cout << min_total_cost << std::endl;
}
return 0;
}