Fastest way to gain Elixirs/Power Elixirs?

Pap, captain latanica, and pianus all drop a ton of them. Just make sure you do twice a day. Then you'll have them when you want to train.

If you want to work hard for it though, then go to Zakum dungeon and hit the little boxes for the power elixers.