自分でもやってますがどうにも難しいですね・・・
乗算回数がnpより良い方法が見つかりませんし、存在しないかもしれません。