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 == 0 = succ.factor p $ div x p
           | otherwise = 0

factorMemo p = listArray (0,n).scanl (+) 0.map (factor p) $ [1..n] :: UArray Int Int

p154 = foldl'(+) 0$ 
       do a <- [0..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==0? 1+factor(p,x/p): 0;
    }
    public static void main(String[] args){
	long count=0;
	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=0, 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[c], d5=f5[a]+f5[b]+f5[c];
		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==0? 1+factor(p,x/p): 0;
}
int main(){
  long count=0;
  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=0, 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[c], d5=f5[a]+f5[b]+f5[c];
      if(n5-d5>=d&&n2-d2>=d)count+= a==b||b==c? 3: 6;
    }
  cout << count << endl;
}

速度は予想通りの
c++>java>>haskell
ま、重要なのはアルゴリズムだから。