登 录
//poj 1150 The Last Non-zero Digit (计数)<br /> /*<br /> 题解：http://www.aowe.net/n285c6.aspx这位老兄的题解够清楚了，只是网页有毒，汗。。。<br /> PS: 好像和之前做的求阶乘的0尾数个数的题如出一辙，只不过这题是求非0的最后一位。除了<br /> 经典的求质因数2和5的个数外，还要求以3、7、9这样的奇数结尾的数的个数。<br /> */<br /> #include <iostream><br /> #include <algorithm><br /> #include <cmath><br /> #include <vector><br /> using namespace std;<br /> const int inf = 1<<28;<br /> int n,m;</p> <p>//返回2或5的个数<br /> int getnum(int n,int val)<br /> {<br /> int ans=0;<br /> while(n)<br /> {<br /> ans+=(n/=val);<br /> }<br /> return ans;<br /> }<br /> //返回1、3或7 的 个数<br /> int getx(int n,int val)<br /> {<br /> int ans=0;<br /> for (int i=n;i;i>>=1)<br /> for (int j=i;j;j/=5)<br /> {<br /> ans+=j/10 + (j%10>=val);<br /> }<br /> return ans;<br /> }</p> <p>int num[10];</p> <p>//分别代表2^i(i=2、3、7、9)的个位数循环节<br /> int fac[4][4]={6,2,4,8, 1,3,9,7, 1,7,9,3, 1,9,1,9};<br /> int main()<br /> {<br /> while (scanf("%d%d",&n,&m)!=EOF)<br /> {<br /> int ans=1;<br /> m=n-m;<br /> num[5]=getnum(n,5)-getnum(m,5);<br /> num[2]=getnum(n,2)-getnum(m,2);<br /> if (num[5]>num[2]) {<br /> printf("5/n");<br /> continue;<br /> }<br /> else if (num[5]==num[2]) ans=1;<br /> else ans=fac[0][(num[2]-num[5])%4];</p> <p> num[3]=getx(n,3)-getx(m,3);<br /> ans=ans*fac[1][num[3]%4]%10;<br /> num[7]=getx(n,7)-getx(m,7);<br /> ans=ans*fac[2][num[7]%4]%10;<br /> num[9]=getx(n,9)-getx(m,9);<br /> ans=ans*fac[3][num[9]%2]%10;</p> <p> printf("%d/n",ans);<br /> }<br /> system("pause");<br /> return 0;<br /> }</p> <p>
抱歉!评论已关闭.