POJ3406 Last digit

組み合わせの計算nCmを行い、0でない最後の桁を求めるプログラムを書いてください。という問題です。例えば、n=8,m=3だと56なので、1のくらいの6が正解。n=8,m=4だと70なので、10のくらいの7が正解。n,mの最大値が1000000なので、普通に計算すると時間が全然足りません。組み合わせに関するショートコーディングは、これまでイヤというほどやってきましたが、これはまた新しいかんじで面白かったです。

• 普通のコード

最初に思いついた方法です。この後、因数分解とかパスカルの三角形も考えたのですが、結局これが簡単だし速度もなかなかでした。とにかく、1の位がいつの間にか0になってしまうのさえ気をつければそれほど大変ではないと思います。とりあえず、n,mについて、2と5が因数になっている場合だけガシガシ割って、あとで適当に調整しておけばよろしいかと。

#include<stdio.h>

int main()
{
  int n,m;

  // 素因数2,5の数を保持
  int n2,n5;
  int m2,m5;

  int i,j,k;
  int ans=1;
  int tm,tn;

  n2 = n5 = m2 = m5 = 0;

  scanf("%d%d",&n,&m);

  for(i=0;i<m;++i)
  {
    tn = ans*n--;
    tm = m-i;
    
    // 2,5で可能な限り割る。同時に回数も記録
    while(tn%2==0){ ++n2; tn/=2; }
    while(tn%5==0){ ++n5; tn/=5; }
    while(tm%2==0){ ++m2; tm/=2; }
    while(tm%5==0){ ++m5; tm/=5; }
    
    // 掛けて下一桁が等しくなるansを見つける
    for(ans=1;1;++ans)
    {
      if( (tm*ans)%10==tn%10 )break;
    }
  }
  
  // 共通な素因数は約分できるので、どちらかが0になるまで
  // カウントを減らす(mが先のハズ)
  while(n2&&m2){ --n2; --m2; }
  while(n5&&m5){ --n5; --m5; }
  
  // 10の倍数は下一桁が0になってしまうので消去
  while(n2&&n5){ --n2; --n5; }

  while(n2){ --n2; ans = (ans*2)%10; }
  while(n5){ --n5; ans = (ans*5)%10; }
  
  printf("%d\n",ans);
  
  return 0;
}

• 超短いコード

こちらは続きを読むにしとくかな

m,n;b,c;e;

F(y)
{
  for(;c%2*c%5<1;c/=c%2?5:2)e+=c%2?-y:y;
}

main(a)
{
  for(scanf("%d%d",&n,&m);c=m--;)
   for(F(-1),b=c,a=!F(1,c=a*n--);(b*++a-c)%10;);
  putchar((e<0?5:a<<e)%10+48);
}

10で割れる場合は必ず割るので、結局因数は2か5のいずれか一方しかないという点に気付けば、変数をかなり減らすことができます。2が残る場合は正、5が残る場合は負のようにしておけば、一つの変数で済みますし、5が残ればLast Digitは必ず5になります。うまく縮まなかったので、関数作って誤魔化してますが、ちゃんと短縮すればいらないんじゃないかと思います（難しそう…）。あと、a<