nefu 628 Garden visiting

題目：給出一個n*m大的花園，求出從左上角到右下角的路徑數目（路徑單調）。

方法：路徑數=c（m+n-2,m-1);别忘了最後對p取餘。由于資料最大能達到10^5，使用楊輝三角記錄的話會爆記憶體，是以隻能換方法。

           由于c(x,y)=x!/(y!*(x-y)!)，這裡我們可以将x!分解素因子，并儲存記錄下來，同樣的方法記錄後面兩個，由于x!必然能夠整除(y!*(x-y)!)，是以後面兩個數有的因子，x!比然有，隻需要将他們的因子的指數相加減，就能得到最後結果的素因子分解的情況，然後最後使用快速幂取模，就能得到最後的結果。

注意：如何進行素因子分解？

            首先要打表将所有的素因子求出來，這裡有是将n！進行素因子分解，假設想要求出其中有多少個5，這裡是有技巧的。

            假設n=200，那麼因子5的個數=200/5+40/5+8/5=49，怎麼得到的呢？200中5的倍數有40個，這40個數中其中是25的倍數的有8個，是以還能分解出8個5，這8個數中還有一個是125的倍數，還能分解出一個5，就這樣一直循環下去，就能求出指數的值。

代碼：