Fastest way to go from linear index to grid index

I think this is what you want:

IntegerDigits[35 - 1, MixedRadix[{5, 4, 3}], 3] + 1

In general:

gridIndex[n_Integer, shape_List] := 
 IntegerDigits[n - 1, MixedRadix[shape], Length@shape] + 1

If you have enough memory, then a lookup table may be fastest:

shape = {5, 4, 3};
indices = Tuples[Range /@ shape];

Lookup is fast:

indices[[35]] // RepeatedTiming
(* {3.*10^-7, {3, 4, 2}} *)

Also, it seems that doing lots of lookups simultaneously is even faster (per lookup):

indices[[{22, 45, 35, 49, 36, 9, 9, 39, 59, 14}]] // RepeatedTiming

Here is the obligatory compiled version; it is not as fast as Roman's lookup method but it is also less memory hungry (in particular if indexing is supposed to be done into SparseArray whose dense version does not fit into memory).

A compiled helper function:

cf = Compile[{{n, _Integer}, {mods, _Integer, 1}},
   Block[{r = n - 1, d, m},
    Table[
     m = Compile`GetElement[mods, i];
     d = Quotient[r, m];
     r = r - d m;
     d + 1,
     {i, 1, Length[mods]}]
    ],
   CompilationTarget -> "C",
   RuntimeAttributes -> {Listable},
   Parallelization -> True,
   RuntimeOptions -> "Speed"
   ];
getInds[idx_, shape_] :=
 cf[idx, Reverse[Most[FoldList[Times, 1, Reverse[shape]]]]]

Usage example and timing test, comparing against swish's and Roman's proposals:

RandomSeed[123];
shape = RandomInteger[{1, 10}, 4];
idx = RandomInteger[{1, Times @@ shape}, 10000];

a = gridIndex[#, shape] & /@ idx; // RepeatedTiming // First

b = getInds[idx, shape]; // RepeatedTiming // First

indices = Tuples[Range /@ shape];
c = indices[[idx]]; // RepeatedTiming // First
a == b == c

0.429

0.00059

0.0000700

True