Guys, guys, don’t fight. I’m sure we’ll be able to come up with something roughly equal.
eulernt.pwni.ng:5555
NOTE: We originally uploaded the wrong version. It is still available here if you really want it: wrong version.
How to solve
We need to get a divisor of $333!$ that is close to $(333!)^{1/2}$.
Just factorize with factorDB. There are some $p^k$s of which $k$ is odd. Let’s define a product of those $p$s as $v := \prod p$.
So, we can easily get $(333! / v) ^ {1/2}$. The next step is to calculate a value which is similar to $v ^ {1/2}$.
Let’s just guess we can make the value with primes {2, 3, 5, 7, 11, 13, 17, 19, 23}. Then try all possible values nearby $v ^ {1/2}$. If you can get from this set, just add more primes.
import gmpy2
primes = [3, 5, 7, 19, 29, 37, 43, 47,
59, 61, 89, 97, 101, 103, 107,
109, 167, 173, 179, 181, 191,
193, 197, 199, 211, 223, 227,
229, 233, 239, 241, 251, 257,
263, 269, 271, 277, 281, 283,
293, 307, 311, 313, 317, 331]
v = 1
for p in primes:
v *= p
N = 1
for i in range(2, 333):
N *= i
Nv_root = gmpy2.isqrt(N // v)
v_root = gmpy2.isqrt(v)
# Rough upper limit
lim = v_root + v_root // 10000
primes = [3, 5, 7, 11, 13, 17, 19, 23]
def backtrack(idx, val):
if idx == len(primes):
lg = int(math.log(v_root, 2) - math.log(val, 2))
final = val * (2 ** lg) * Nv_root
fstr = str(final)
if len(fstr) == 349 and fstr[:8] == '32147263':
print(final)
final *= 2
fstr = str(final)
if len(fstr) == 349 and fstr[:8] == '32147263':
print(final)
return
while True:
val *= primes[idx]
if val > lim:
return
backtrack(idx + 1, val)
backtrack(0, 1)
From this, I was able to get a value:
3214726365718308699390009351051926320347863432801378170603206865184662872923685805900796110576640315841185356341136473888821110903341917546848786593096487214784202625564775154918631601168022399388653631105727651790627380050049166043926298612848761901579219048962836676642657563673663196096066312251333672960000000000000000000000000000000000000000000
The flag is PCTF{R3fr3sh1ngly_Sm00th}
.