А если long вместо int везде использовать? Там же сразу четыре лярда на результат вычисления получится.
Думаю, лучше сразу и на ближайшие пару тысяч лет хватит 
В sic 2.0 рестартанувшие цепочка и сложность сети опять до 1.001 опустят награду поначалу?
Да. Можно искуственно задать большую сложность на старте, но смысла в этом большого нет. Только создавать дополнительную головную боль. 
Кстати, Бальтазар, если прочитаешь это, как-то бы отрегулировать этот момент, чтобы сложность более резво реагировала на изменение мощности сети 
Копипаст функции из NVC решил бы этот вопрос...