Ah! I think I will get an TLE but got AC the First Time!
You can use brute-force for n=8k+1 and use simple math method for other cases!

Edited by author 22.12.2008 20:46

Edited by author 22.12.2008 20:46

Publish worst case for your solution please. Is it when k=100000, n is always 8k+1, prime near 32767?

Yes!

And how much time your program work on this test on Timus check server? You may estimate it by comparing time of your current program and the same program also calculating answers (without output) for 1000/10000 such n.

Edited by author 11.01.2009 12:38