>>447
少なくともFFTを使って高速化できるのはnに何の要件もなければ無理なんじゃないかな？
少なくともwikiではnが小さい素因子をたくさんかけた形の高速化法しか載ってない
一般の場合でもできるなら方法そのものを載せるのは無理でも論文へのリファレンスがないのは考えられないし
出題ミスかな？
FFTでできないから一般にも無理とは言えないけど