Problem 154

http://projecteuler.net/index.php?section=problems&id=154

3項係数の約数について。

haskellでの実装。

import Control.Monad
import Data.Array.Unboxed
import Data.List
n = 2*10^4
d = 10
main = print p154
factor p x | mod x p ==  = succ.factor p $ div x p
| otherwise = 
factorMemo p = listArray (,n).scanl (+) .map (factor p) $ [1..n] :: UArray Int Int
p154 = foldl'(+) $
do a <- [..div n 3]
b <- [a..div (n-a) 2]
let c  = n-a-b
let d2 = sum.map (factor2!)$ [a,b,c]
d5 = sum.map (factor5!)$ [a,b,c]
guard$ n2 - d2 >= d && n5 - d5 >= d
return$ if a==b||b==c then 3 else 6
where n2 = factor2! n
n5 = factor5! n
factor2 = factorMemo 2
factor5 = factorMemo 5

遅い。

同じアルゴリズムをjavaで

public class P154{
static int n=2*(int)Math.pow(10,5),d=12;
public static int factor(int p,int x){
return x%p==? 1+factor(p,x/p): ;
}
public static void main(String[] args){
long count=;
int[] f2 = new int[n+1],f5 = new int[n+1];
for(int i=1; i<n+1; f2[i]=f2[i-1]+factor(2,i++));
for(int i=1; i<n+1; f5[i]=f5[i-1]+factor(5,i++));
for(int a=, n2=f2[n], n5=f5[n]; a<=n/3; a++)
for(int b=a; b<=(n-a)/2; b++){
int c=n-a-b, d2=f2[a]+f2[b]+f2, d5=f5[a]+f5[b]+f5;
if(n5-d5>=d&&n2-d2>=d)count+= a==b||b==c? 3: 6;
}
System.out.println(count);
}
}

c++で

#include <iostream>
using namespace std;
int n=200000,d=12;
int factor(int p,int x){
return x%p==? 1+factor(p,x/p): ;
}
int main(){
long count=;
int f2[n+1],f5[n+1];
for(int i=1; i<n+1; i++)f2[i]=f2[i-1]+factor(2,i);
for(int i=1; i<n+1; i++)f5[i]=f5[i-1]+factor(5,i);
for(int a=, n2=f2[n], n5=f5[n]; a<=n/3; a++)
for(int b=a; b<=(n-a)/2; b++){
int c=n-a-b, d2=f2[a]+f2[b]+f2, d5=f5[a]+f5[b]+f5;
if(n5-d5>=d&&n2-d2>=d)count+= a==b||b==c? 3: 6;
}
cout << count << endl;
}

速度は予想通りの

c++>java>>haskell

ま、重要なのはアルゴリズムだから。