Even a full format or factory reset might not be useful.Hard drives have to be cleanly wiped out.
Read that news from Kaspersky
https://www.kaspersky.com/blog/cryptoshuffler-bitcoin-stealer/19976/First , it's nothing new
It took the Trojan a little more than a year to collect that money. Peak activity in late 2016 was followed by a slump, but then in June 2017, CryptoShuffler reawakened.
Second , I really doubt that claim that FR will not solved it.
Kaspersky didn't mention it not did the former article:
https://securelist.com/tales-from-the-blockchain/82971/I only know a few trojans capable of surviving by embedding themselves in the MBR.
Not sure how this would work on android.
That's besides the point. Just because you doubt that it would be able to do that doesn't mean you shouldn't protect against it. It might be one of the few trojans which can do it.