The way I did it was to have Yuna and Paine as dark knights using "Darkness" every turn, while Rikku was an alchemist using "Mega-Potion Stash" every turn (if you don't have it, have the alchemist Mix a Potion and a Hi-Potion for the same effect). Still, Angra Mainyu was still able to get Perdition's Flame through once in awhile (although it can't use it when the side pieces are dead). Yuna survived it, and I just used a Mega-Phoenix and started the routine over again. My characters were between levels 72 and 75 and it still took 20 minutes to half an hour to beat him.