Product Path You are given two integers N N and ...
बनाया गया: 26 मार्च 2025
प्रश्न
Product Path
You are given two integers
N
N and
M
M.
Consider two infinite arrays
A
A and
B
B, where
A
i
max
(
i
,
N
i
)
A
i
=max(i,
i
N
) if
i
i divides
N
N; and
A
i
0
A
i
=0 otherwise.
B
i
max
(
i
,
M
i
)
B
i
=max(i,
i
M
) if
i
i divides
M
M; and
B
i
0
B
i
=0 otherwise.
For example, if
N
6
N=6, then
A
[
6
,
3
,
3
,
0
,
0
,
6
,
0
,
0
,
0
,
…
]
A=[6,3,3,0,0,6,0,0,0,…]
You are standing on the 2D plane, at point
(
1
,
1
)
(1,1).
In one move, you can move in any of the four directions, as long as both coordinates remain positive. That is, from point
(
x
,
y
)
(x,y), you can move to
(
x
−
1
,
y
)
,
(
x
+
1
,
y
)
,
(
x
,
y
−
1
)
,
(x−1,y),(x+1,y),(x,y−1), or
(
x
,
y
+
1
)
(x,y+1), as long as both coordinates of the destination cell are positive.
The cost of point
(
x
,
y
)
(x,y) is defined to be
A
x
×
B
y
A
x
×B
y
.
Find the minimum total cost of moving from
(
1
,
1
)
(1,1) to
(
P
,
Q
)
(P,Q), where the total cost of a path is the sum of costs of all points visited along the way (including the initial and final points).
Input Format
The first line of input will contain a single integer
T
T, denoting the number of test cases.
Each test case consists of a single line of input, containing four space-separated integers
N
,
M
,
P
,
N,M,P, and
Q
Q as described in the statement.
Output Format
For each test case, output on a new line the answer: the minimum cost to reach
(
P
,
Q
)
(P,Q).
Constraints
1
≤
T
≤
1
0
3
1≤T≤10
3
1
≤
N
,
M
,
P
,
Q
≤
1
0
8
1≤N,M,P,Q≤10
8
Sample 1:
Input
Output
4
2 2 2 2
1 4 3 10
6 10 2 5
720720 123456 210 35
12
4
105
181661800320
Explanation:
Test case
1
1: The arrays
A
A and
B
B are both
[
2
,
2
,
0
,
0
,
0
,
…
]
[2,2,0,0,0,…].
This is because, since
N
2
N=2, we have
A
1
max
(
1
,
2
1
)
2
A
1
=max(1,
1
2
)=2 and
A
2
max
(
2
,
2
2
)
2
A
2
=max(2,
2
2
)=2 while all following elements are
0
0. The same applies to array
B
B.
One optimal path to reach
(
2
,
2
)
(2,2) is
(
1
,
1
)
→
(
1
,
2
)
→
(
2
,
2
)
(1,1)→(1,2)→(2,2), which has a cost of
2
×
2
+
2
×
2
+
2
×
2
12
2×2+2×2+2×2=12.
Test case
2
2: Every path from
(
1
,
1
)
(1,1) to
(
3
,
10
)
(3,10) has a cost of
4
4.
accepted
Accepted
2
total-Submissions
Submissions
5
accuracy
Accuracy
40
Did you like the problem statement?
More Info
Time limit2 secs
Memory limit1.5 GB
Source Limit50000 Bytes
import java.util.;
import java.lang.;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
}
}
write a java solution
उत्तर
javaimport java.util.*; import java.io.*; /* ───────────────────────────────────────────────────────────────────────────── PRODUCT PATH (Java solution) We have two infinite arrays A and B: A[i] = 0 unless i divides N, in which case A[i] = max(i, N/i). B[i] = 0 unless i divides M, in which case B[i] = max(i, M/i). The "cost" of a grid‐cell (x,y) is A[x]*B[y]. We start at (1,1) and want to reach (P,Q) by moves up/down/left/right (staying in positive coords). The total path‐cost is the sum of A[x]*B[y] over every visited cell, including start and end. Key insight: • A[x]*B[y] is nonzero exactly when x divides N and y divides M. Call X = all divisors of N, Y = all divisors of M. • Hence most of the infinite grid has cost=0. Only points (x,y) with x in X and y in Y have a positive cost. • We can “walk for free” in any region where either x ∉ X or y ∉ Y, since then A[x]=0 or B[y]=0. • The only time we pay cost is when we step on a cell (x,y) with x ∈ X and y ∈ Y. We call that set X×Y the “expensive” cells. Because we can move outside X×Y at will (and that movement costs 0), the problem reduces to figuring out: (1) How much it costs to “escape” from (1,1) (if (1,1)∈X×Y) out to the region outside X×Y, (2) How much it costs to “re‐enter” X×Y to get to (P,Q) (if (P,Q)∈X×Y), (3) Possibly also the cost of staying entirely inside one connected component of X×Y if (1,1) and (P,Q) are in the same one. In more detail: • Build the set of divisors X of N, and Y of M. • Each connected component of X×Y is determined by adjacency: (x,y) ~ (x+1,y) if both x,x+1 ∈ X and y ∈ Y (x,y) ~ (x,y+1) if both y,y+1 ∈ Y and x ∈ X (and similarly for −1 moves). Typically there are “gaps” between divisors, so X×Y splits into disjoint components. • A move that would take x outside X (or y outside Y) is effectively stepping into the cost=0 region. Such a node (x,y) with an adjacent step outside is called a “boundary node” in that component. • We do a Dijkstra (or BFS if costs were uniform) on each relevant component with vertex‐cost = A[x]*B[y]. Distances are sums of “node‐costs,” including the start node. • From (1,1) we find its component compA (if (1,1) ∈ X×Y), run Dijkstra to get distA(·). The cost to escape is min over boundary b of distA(b). Also distA(P,Q) is the cost of going inside the same component if (P,Q) is also in compA. • If (P,Q) ∈ X×Y, find its component compB and (by a boundary‐multi‐source Dijkstra) get distB(·). Then re‐entry cost from boundary b′ is distB(b′). • Total minimal cost is computed by combining: – If compA == compB, we can either stay inside (cost = distA(P,Q)), or exit+re‐enter: cost_out_in = min over b in boundary of [ distA(b) + distB(b) − cost(b) ]. Then take min of those two. – If compA != compB, or if (P,Q) ∉ X×Y, we do: cost_exitA = min over b in boundaryA of distA(b), cost_reentryB = min over b′ in boundaryB of distB(b′) (or 0 if (P,Q) ∉ X×Y), total = cost_exitA + cost_reentryB. • Note that (1,1) always divides N and M, so (1,1) is always in X×Y. But (P,Q) might not be, in which case cost(P,Q)=0 automatically. Complexity: • |X|,|Y| up to about 10^3 in the worst case for N,M ≤10^8 (since max #divisors of a 10^8‐sized integer is a few hundred to ~1000). • Then X×Y could be up to ~10^6 cells in the worst case. We can afford a Dijkstra with O(1e6 log(1e6)) = ~2e7 operations once or twice per test in C++ if implemented carefully. In Java it is tight but may still pass if optimized (and if the test data isn’t all worst‐case). • We must do this up to T=1000 testcases, so careful implementation is required. (In practice, typical inputs are smaller or not all near worst‐case.) Below is a reasonably optimized Java implementation of this plan. ───────────────────────────────────────────────────────────────────────────── */ class Codechef { static FastReader in = new FastReader(); static PrintWriter out = new PrintWriter(System.out,false); // --------------------------------------------------------------- // MAIN SOLVE // --------------------------------------------------------------- public static void main(String[] args) { int T = in.nextInt(); // Pre‐allocate data structures once if needed: // (We will create them anew for each test, since each test has separate Nx,Ny.) while(T-->0){ long N = in.nextLong(); long M = in.nextLong(); long P = in.nextLong(); long Q = in.nextLong(); // 1) Collect divisors of N => X, divisors of M => Y. // Make sure they are sorted. ArrayList<Long> divN = getDivisorsSorted(N); ArrayList<Long> divM = getDivisorsSorted(M); // Map from divisor -> index in divN / divM: // We'll do a binary search to find indices. // We know (1,1) is always in X×Y, so that is guaranteed to exist in divN,divM. // 2) Build subcomponent for (1,1). // (1,1) => find i1, j1 in the arrays: int i1 = Collections.binarySearch(divN, 1L); int j1 = Collections.binarySearch(divM, 1L); // create visited array for N*M grid in the divisor‐index sense // but we do not want to build adjacency for all; instead we BFS from (i1,j1). // We'll store them in compA array (list of nodes in that subcomponent). // Then we do a Dijkstra to compute distA. // We'll need a map from (i,j) -> compIndex. We'll fill it as we BFS. Map<LongPair,Integer> compMapA = new HashMap<>(); ArrayList<LongPair> compNodesA = new ArrayList<>(); // BFS to find all connected nodes in the subcomponent of (i1,j1). buildSubcomponent(i1, j1, divN, divM, compMapA, compNodesA); // Now we have compA = all nodes in subcomponent. Let boundaryA = all boundary nodes. // We'll find boundary as those that can step outside X×Y in at least one direction. ArrayList<Integer> boundaryA = new ArrayList<>(); for(int idx=0; idx<compNodesA.size(); idx++){ LongPair p = compNodesA.get(idx); long xval = p.x, yval = p.y; if( isBoundary(xval,yval,divN,divM) ){ boundaryA.add(idx); } } // Next, run a Dijkstra from (i1,j1) to find distA[...]. long[] distA = runDijkstraSingleSource(divN, divM, compNodesA, compMapA, /*startIndex=*/0); // cost to exit from subcomponent A: long costExitA = Long.MAX_VALUE; for(int b : boundaryA){ if(b==0) continue; // that is the start node itself, but it's also boundary if x=1 or y=1 with no neighbor. if(distA[b]<costExitA){ costExitA = distA[b]; } } // If the start node itself is boundary, then costExitA can be distA[0] as well, // though "exiting immediately" is still paying cost(1,1). So let's allow that: costExitA = Math.min(costExitA, distA[0]); // 3) Now see if (P,Q) is in X×Y. If not, cost(P,Q)=0 and we can reach it from outside with 0 extra cost. boolean pInX = (Collections.binarySearch(divN, P)>=0); boolean qInY = (Collections.binarySearch(divM, Q)>=0); long answer = 0; if(!pInX || !qInY){ // Then (P,Q) is outside X×Y => cost there is 0 => we just do costExitA. answer = costExitA; } else { // (P,Q) is in X×Y => we find its subcomponent compB. int iP = Collections.binarySearch(divN, P); int jP = Collections.binarySearch(divM, Q); // Check if it is in the same subcomponent as (1,1). If so, compMapA contains it. LongPair pq = new LongPair(P, Q); Integer compIdxP = compMapA.get(pq); if(compIdxP!=null){ // same subcomponent int idxP = compIdxP; long costStay = distA[idxP]; // direct inside path // Next we do a multi‐source Dijkstra from boundaryA to get distB(...) to (P,Q). // But in the same subcomponent, "distB(...)" is just another Dijkstra. We can do // runDijkstraMultiSource(...) starting from boundaryA. Or simpler: we can // re‐use runDijkstraSingleSource if we create a virtual node or do a small trick. // Let’s implement a separate routine. long[] distFromBoundA = runDijkstraMultiSource(divN, divM, compNodesA, compMapA, boundaryA); long costOutIn = distFromBoundA[idxP]; // But we have double‐counted the boundary node cost if we do // distA(b) + distFromBoundA(b). The multi‐source approach sets // distFromBoundA(b) = cost(b). Meanwhile distA(b) also includes cost(b). // The formula for exit+re‐enter via boundary b is: // distA(b) + distB(b) - cost(b). // So we must incorporate that by adjusting after the fact: // We'll do costOutIn = min over b in boundaryA [ distA(b) + distFromBoundA(b) - cost(b) ] long best = Long.MAX_VALUE; for(int b : boundaryA){ long val = distA[b] + distFromBoundA[b] - costOf(compNodesA.get(b).x, compNodesA.get(b).y); if(val<best) best=val; } long finalCost = Math.min(costStay, best); answer = finalCost; } else { // Different subcomponent => we must build compB for (P,Q). Map<LongPair,Integer> compMapB = new HashMap<>(); ArrayList<LongPair> compNodesB = new ArrayList<>(); buildSubcomponent(iP, jP, divN, divM, compMapB, compNodesB); // boundaryB: ArrayList<Integer> boundaryB = new ArrayList<>(); for(int idx=0; idx<compNodesB.size(); idx++){ LongPair p2 = compNodesB.get(idx); if(isBoundary(p2.x, p2.y, divN, divM)){ boundaryB.add(idx); } } // Dijkstra multi‐source from boundaryB to get distB( (P,Q) ). // The index of (P,Q) in compNodesB is presumably 0 if we add it first, // but let's be sure. We built it by BFS from (iP, jP), so index=0 there: long[] distB = runDijkstraMultiSource(divN, divM, compNodesB, compMapB, boundaryB); // the index of (P,Q) is 0 in compNodesB (since we started BFS from it), // so distB( (P,Q) ) = distB[0]. long bestB = distB[0]; // cost to get from boundary to (P,Q) // total = costExitA + bestB answer = costExitA + bestB; } } out.println(answer); } out.flush(); } // ---------------------------------------------------------------- // Return all positive divisors of n in ascending order. // ---------------------------------------------------------------- static ArrayList<Long> getDivisorsSorted(long n){ // Typical method: collect divisors up to sqrt(n), then mirror. // Then sort. ArrayList<Long> small = new ArrayList<>(); for(long x=1; x*x<=n; x++){ if(n%x==0){ small.add(x); if(x*x!=n){ small.add(n/x); } } } HashSet<Long> set = new HashSet<>(small); ArrayList<Long> ans = new ArrayList<>(set); Collections.sort(ans); return ans; } // ---------------------------------------------------------------- // BFS to find the connected subcomponent (in X×Y) containing (i0,j0). // // We consider adjacency in index‐space: // (i,j) -> (i±1, j) if X[i±1] == X[i]±1 and j is same // (i,j) -> (i, j±1) if Y[j±1] == Y[j]±1 and i is same // Then we store the actual (xVal, yVal) in compNodes, and also // populate compMap from (xVal,yVal)-> indexInThisComponent. // ---------------------------------------------------------------- static void buildSubcomponent(int i0, int j0, ArrayList<Long> divN, ArrayList<Long> divM, Map<LongPair,Integer> compMap, ArrayList<LongPair> compNodes) { // We'll do a queue BFS in (i,j) space Queue<int[]> queue = new ArrayDeque<>(); queue.add(new int[]{i0, j0}); LongPair startPair = new LongPair(divN.get(i0), divM.get(j0)); compMap.put(startPair, 0); compNodes.add(startPair); while(!queue.isEmpty()){ int[] cur = queue.poll(); int ix = cur[0], iy = cur[1]; long xVal = divN.get(ix), yVal = divM.get(iy); // check neighbors in x dimension: // check ix-1, ix+1 if in range and if divN[ix±1]==xVal±1 // move left: if(ix>0){ long xValLeft = divN.get(ix-1); if(xValLeft==xVal-1){ // so we have adjacency LongPair np = new LongPair(xValLeft,yVal); if(!compMap.containsKey(np)){ int newIdx = compNodes.size(); compMap.put(np,newIdx); compNodes.add(np); queue.add(new int[]{ix-1, iy}); } } } // move right: if(ix+1 < divN.size()){ long xValRight = divN.get(ix+1); if(xValRight==xVal+1){ LongPair np = new LongPair(xValRight,yVal); if(!compMap.containsKey(np)){ int newIdx = compNodes.size(); compMap.put(np,newIdx); compNodes.add(np); queue.add(new int[]{ix+1, iy}); } } } // check neighbors in y dimension: // move down: if(iy>0){ long yValDown = divM.get(iy-1); if(yValDown==yVal-1){ LongPair np = new LongPair(xVal,yValDown); if(!compMap.containsKey(np)){ int newIdx = compNodes.size(); compMap.put(np,newIdx); compNodes.add(np); queue.add(new int[]{ix, iy-1}); } } } // move up: if(iy+1 < divM.size()){ long yValUp = divM.get(iy+1); if(yValUp==yVal+1){ LongPair np = new LongPair(xVal,yValUp); if(!compMap.containsKey(np)){ int newIdx = compNodes.size(); compMap.put(np,newIdx); compNodes.add(np); queue.add(new int[]{ix, iy+1}); } } } } } // ---------------------------------------------------------------- // Check if (xVal,yVal) in X×Y is a boundary node, meaning we can step // out of X×Y by x±1 or y±1. That is, at least one of x±1 ∉ X or y±1 ∉ Y. // We only need to check if x±1 is in the sorted list divN or y±1 is in divM. // If x+1 not in X or x-1 not in X or similarly in y, it's boundary. // We'll do a quick membership check with a binary search. // ---------------------------------------------------------------- static boolean isBoundary(long xVal, long yVal, ArrayList<Long> divN, ArrayList<Long> divM) { // check x+1 not in X or x-1 not in X: // i.e. binarySearch(divN, xVal+1) <0 or xVal+1 would lead us out if(Collections.binarySearch(divN, xVal+1)<0) return true; if(xVal>1 && Collections.binarySearch(divN, xVal-1)<0) return true; // check y+1 or y-1: if(Collections.binarySearch(divM, yVal+1)<0) return true; if(yVal>1 && Collections.binarySearch(divM, yVal-1)<0) return true; return false; } // ---------------------------------------------------------------- // The cost of a node (x,y) in X×Y is A[x]*B[y] = max(x,N/x)*max(y,M/y). // But from the problem statement’s examples, we can see that "A[x] = max(x, N/x)" // and similarly "B[y] = max(y, M/y)". We just compute it directly. // ---------------------------------------------------------------- static long costOf(long x, long y){ // The problem’s formula is: A[x] = max(x,N/x) if x|N, but we only // ever call this if x|N. Similarly for y. So we can assume that’s valid. // We do not actually need N or M themselves because N/x = "integer division" // but we do not have N stored here. Actually we DO need N and M if we’re // to compute them exactly. But we stored them? The code above does not // store them globally. So we either store them or note we only call costOf // in the BFS with known x,y that are divisors. We have to do max(x, N/x). // That N is not in scope here. A quick fix is to store N and M in a static // and do a dictionary. But to keep it simpler, we can do: // "x * y" is not correct. We need the actual formula with N and M in scope. // Easiest fix: We pass in the “global” N and M or store them as static. // For clarity, let's do the simpler approach: store a static N0,M0 and // set them before usage. Or pass them as arguments each time we do costOf. // Let’s do a separate costOf(x, y, N, M). // This method is just a placeholder. We'll never call it directly in the final BFS code // unless we have N and M. We will override with costOf(x,y,N,M). return 0; } // Overload with the real arguments: static long costOf(long x, long y, long N, long M){ long A = Math.max(x, N/x); // x divides N long B = Math.max(y, M/y); // y divides M return A * B; } // ---------------------------------------------------------------- // Run a Dijkstra from a single source node (startIndex) in compNodes. // We store dist[] = sum‐of‐cost of visited nodes, i.e. dist[v] = minimal cost // to reach v from the start, counting cost(start) + cost(...) + cost(v). // // Implementation detail: // We interpret the cost to *enter* a node v as cost(nodeV). Then // dist[u] + cost(v) if there's an edge (u->v). Also dist[start] = cost(start). // ---------------------------------------------------------------- static long[] runDijkstraSingleSource( ArrayList<Long> divN, ArrayList<Long> divM, ArrayList<LongPair> compNodes, Map<LongPair,Integer> compMap, int startIndex ){ // We'll need N and M to compute costOf. But we only have the arrays of divisors? // We do need the actual N=divN.getLast()*??? Wait, not so easy. The problem // statement uses the original N, M. We must store them? Actually we can glean // from the fact that each x in divN divides the same N, so to compute N/x we must // know N. So we do indeed need the original N, M. Let's store them in arrays: // The simplest is to note that divN.get(divN.size()-1) is the largest divisor, // which should be N itself (since obviously N divides N). So N = divN.getLast(). // Similarly M = divM.getLast(). (Unless N=0 or M=0, but that’s not in constraints.) long bigN = divN.get(divN.size()-1); long bigM = divM.get(divM.size()-1); int size = compNodes.size(); long[] dist = new long[size]; Arrays.fill(dist, Long.MAX_VALUE); dist[startIndex] = costOf(compNodes.get(startIndex).x, compNodes.get(startIndex).y, bigN, bigM); // adjacency on‐the‐fly => for each node, up to 4 neighbors PriorityQueue<NodeDist> pq = new PriorityQueue<>(); pq.add(new NodeDist(startIndex, dist[startIndex])); while(!pq.isEmpty()){ NodeDist nd = pq.poll(); int u = nd.node; long curD = nd.dist; if(curD>dist[u]) continue; // stale // u’s coordinate: LongPair upair = compNodes.get(u); long ux = upair.x, uy = upair.y; // check 4 neighbors: (ux±1, uy), (ux, uy±1) if valid // we do "if in compMap" then we update // use binary search or direct check with compMap // left: if(ux>1){ LongPair vpair = new LongPair(ux-1, uy); Integer vidx = compMap.get(vpair); if(vidx!=null){ long ndist = curD + costOf(ux-1, uy, bigN, bigM); if(ndist<dist[vidx]){ dist[vidx] = ndist; pq.add(new NodeDist(vidx, ndist)); } } } // right: LongPair vpairR = new LongPair(ux+1, uy); Integer vidxR = compMap.get(vpairR); if(vidxR!=null){ // must check if (ux+1) is indeed consecutive in X, but compMap ensures that long ndist = curD + costOf(ux+1, uy, bigN, bigM); if(ndist<dist[vidxR]){ dist[vidxR] = ndist; pq.add(new NodeDist(vidxR, ndist)); } } // down: if(uy>1){ LongPair vpairD = new LongPair(ux, uy-1); Integer vidxD = compMap.get(vpairD); if(vidxD!=null){ long ndist = curD + costOf(ux, uy-1, bigN, bigM); if(ndist<dist[vidxD]){ dist[vidxD] = ndist; pq.add(new NodeDist(vidxD, ndist)); } } } // up: LongPair vpairU = new LongPair(ux, uy+1); Integer vidxU = compMap.get(vpairU); if(vidxU!=null){ long ndist = curD + costOf(ux, uy+1, bigN, bigM); if(ndist<dist[vidxU]){ dist[vidxU] = ndist; pq.add(new NodeDist(vidxU, ndist)); } } } return dist; } // ---------------------------------------------------------------- // Run a Dijkstra multi‐source from a set of boundary nodes in compNodes. // That is, we set dist[b] = costOf(b) for each boundary b, and dist[u] = ∞ // for others. Then proceed. This yields dist[u] = minimal cost to get // from any boundary node to u, counting cost( boundary ) + ... + cost(u). // ---------------------------------------------------------------- static long[] runDijkstraMultiSource( ArrayList<Long> divN, ArrayList<Long> divM, ArrayList<LongPair> compNodes, Map<LongPair,Integer> compMap, ArrayList<Integer> boundaryList ){ long bigN = divN.get(divN.size()-1); long bigM = divM.get(divM.size()-1); int size = compNodes.size(); long[] dist = new long[size]; Arrays.fill(dist, Long.MAX_VALUE); PriorityQueue<NodeDist> pq = new PriorityQueue<>(); // Initialize boundary nodes for(int bidx : boundaryList){ LongPair bpair = compNodes.get(bidx); long cst = costOf(bpair.x,bpair.y,bigN,bigM); dist[bidx] = cst; pq.add(new NodeDist(bidx,cst)); } while(!pq.isEmpty()){ NodeDist nd = pq.poll(); int u = nd.node; long curD = nd.dist; if(curD>dist[u]) continue; LongPair upair = compNodes.get(u); long ux = upair.x, uy = upair.y; // neighbors: // left: if(ux>1){ LongPair vpair = new LongPair(ux-1, uy); Integer vidx = compMap.get(vpair); if(vidx!=null){ long ndist = curD + costOf(ux-1, uy, bigN, bigM); if(ndist<dist[vidx]){ dist[vidx] = ndist; pq.add(new NodeDist(vidx,ndist)); } } } // right: { LongPair vpair = new LongPair(ux+1, uy); Integer vidx = compMap.get(vpair); if(vidx!=null){ long ndist = curD + costOf(ux+1, uy, bigN, bigM); if(ndist<dist[vidx]){ dist[vidx] = ndist; pq.add(new NodeDist(vidx,ndist)); } } } // down: if(uy>1){ LongPair vpair = new LongPair(ux, uy-1); Integer vidx = compMap.get(vpair); if(vidx!=null){ long ndist = curD + costOf(ux, uy-1, bigN, bigM); if(ndist<dist[vidx]){ dist[vidx] = ndist; pq.add(new NodeDist(vidx, ndist)); } } } // up: { LongPair vpair = new LongPair(ux, uy+1); Integer vidx = compMap.get(vpair); if(vidx!=null){ long ndist = curD + costOf(ux, uy+1, bigN, bigM); if(ndist<dist[vidx]){ dist[vidx] = ndist; pq.add(new NodeDist(vidx, ndist)); } } } } return dist; } // ---------------------------------------------------------------- // A small helper for storing (node, distance) in a PQ. // ---------------------------------------------------------------- static class NodeDist implements Comparable<NodeDist>{ int node; long dist; public NodeDist(int n, long d){ node=n; dist=d; } public int compareTo(NodeDist o){ return Long.compare(dist,o.dist); } } // ---------------------------------------------------------------- // A small pair of longs // ---------------------------------------------------------------- static class LongPair { long x, y; LongPair(long a, long b){ x=a; y=b; } public boolean equals(Object o){ if(this==o) return true; if(!(o instanceof LongPair)) return false; LongPair oo=(LongPair)o; return x==oo.x && y==oo.y; } public int hashCode(){ // a standard combination long val = x*1000000009L + y; return (int)((val ^ (val>>>32)) & 0xffffffff); } } // ---------------------------------------------------------------- // Fast input reader (faster than Scanner) // ---------------------------------------------------------------- static class FastReader { BufferedReader br; StringTokenizer st; public FastReader(){ br = new BufferedReader(new InputStreamReader(System.in),1<<16); } String next(){ while(st==null || !st.hasMoreTokens()){ try{ String line = br.readLine(); if(line==null) return null; st = new StringTokenizer(line); } catch(IOException e){ return null; } } return st.nextToken(); } int nextInt(){ return Integer.parseInt(next()); } long nextLong(){ return Long.parseLong(next()); } } }
Explanation of the core ideas:
-
A cell (x,y) has cost A[x]*B[y] = 0 unless x divides N and y divides M.
We gather the divisors of N into a sorted list X, and the divisors of M into a sorted list Y. -
All nonzero‐cost cells form the set X×Y in the first quadrant. Outside that set, cost = 0.
-
Because moves outside X×Y are free, we only need to see how much “damage” we must pay when we enter or remain inside X×Y. In particular:
• We always pay the cost of (1,1) if 1 divides N and 1 divides M (which it does),
• We can move around outside freely, so effectively we can “exit” from the connected component containing (1,1) whenever we reach a boundary cell (one that has at least one neighbor outside X×Y).
• If (P,Q) ∈ X×Y, we may have to re‐enter its connected component and pay costs there,
• Or, if (1,1) and (P,Q) are in the same connected component, we can either stay inside for the entire trip, or possibly exit and re‐enter, whichever is cheaper. -
Technically, X×Y may split into multiple disconnected “components” because we only allow moves (x,y)→(x±1,y) or (x,y)→(x,y±1) when x±1 remains in X or y±1 remains in Y. We do a standard graph search (Dijkstra) for each relevant component to compute minimal sums of node‐costs.
-
Combine those minimal “exit” and “re‐entry” costs to get the final answer.