Não sei se é possível fazer. Primeiro que para números com 100 dígitos, você precisaria de um PHI de alta precisão, 90 casas talvez. Eu creio que caso consiga processar PHI com precisão, este tipo de solução não gera TLE, afinal uma multiplicação de 100x90 dígitos vai dar uma complexidade de 9000. Como entre 0 e 10^100 existem exatamente 480 números, sua complexidade no pior caso vai ser de O(N) => N = 4.320.000 + um tempo de busca 48.000*K casos testes.

Em java existe o bignum, em C/C++ é preciso implementar manualmente. Seria interessante implementar uma classe generalizada de números grandes com precisão variável e operações matemáticas básicas.