チョコの量を減らせ！

しばらくぶりです。修論も終わり少しずつ競技に復帰していきたい今日このごろですが、
CodeIQでたまに遊んでおります。
(レートがないので気楽にできる、時間に縛られない、などの理由により…)

問題

縦、横、高さが整数の直方体で体積が
280671392065546467397265294532969672241810318954163887187279320454220348884327
のもののうち、表面積が最小になるものを求めよ
という問題。

多倍長整数使うのに練習がてらpythonで書いてみた。

#!/usr/bin/python
import random
import math
import time

def mul_mod(a, b, m):
    return a * b % m

def gcd(a, b):
    if(b == 0):
        return a
    else:
        return gcd(b, a%b)

def rho(n,c):
    sttime = time.clock()
    x = 1
    p = 1
    next = 2
    i = 1
    while(p == 1):
        i = i + 1
        if(i == next):
            y = x
            next *= 2
        x = (mul_mod(x,x,n) + c) % n
        if(y == x):
            return rho(n,c+1)
        p = gcd(n,abs(x-y))
        if(time.clock() - sttime > 600):
            return n
    return p

n = int(raw_input())
while(n!=1):
    p = rho(n,1)
    print p
    n = n / p

まずはロー法で素因数分解してみる。
で

280671392065546467397265294532969672241810318954163887187279320454220348884327
=
358456949*369941863*369941863*162425297*215940091*706170617*479871607*481362815814826159

を得た。最後のやつは打ち切った残りだったのでミラーラビンで素数判定した。

あとはこの8個を3分割するのをO(2^8*2^8)で全探索した

#!/usr/bin/python
import sys

a = [
358456949,
369941863,
369941863,
162425297,
215940091,
706170617,
479871607,
481362815814826159,
]

mini = 10**100
mul = 280671392065546467397265294532969672241810318954163887187279320454220348884327
for i in range(1<<8):
    for j in range(1<<8):
        if((i&j) != 0):
            continue
        tmp = [1,1,1]
        rest = ((1<<8)-1)-(i|j)
        for k in range(8):
            if(i&(1<<k) != 0):
                tmp[0] *= a[k]
            if(j&(1<<k) != 0):
                tmp[1] *= a[k]
            if(rest&(1<<k) != 0):
                tmp[2] *= a[k]
        if(mini > tmp[0] * tmp[1] + tmp[1] * tmp[2] + tmp[0] * tmp[2]):
            print tmp[0] * tmp[1] + tmp[1] * tmp[2] + tmp[0] * tmp[2]
            mini = tmp[0] * tmp[1] + tmp[1] * tmp[2] + tmp[0] * tmp[2]
            for k in range(8):
                if(i&(1<<k) != 0):
                    print k,":",0
                if(j&(1<<k) != 0):
                    print k,":",1
                if(rest&(1<<k) != 0):
                    print k,":",2
            if(tmp[0] * tmp[1] * tmp[2] != mul):
                print "error!"
            else:
                tmp.sort()
                print str(tmp[0])+"x"+str(tmp[1])+"x"+str(tmp[2])

Python便利すなぁ…