📄 usaco 3_2_1 factorials 题解_leokan的blog.mht
字号:
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 3.2.1 Factorials =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA02=D4=C202=C8=D5 =D0=C7=C6=DA=C1=F9 =
11:09</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<P></P>
<H2>USACO 3.2.1 Factorials</H2>
<DIV class=3Dt_msgfont>Factorials<BR><BR>The factorial of an =
integer N,=20
written N!, is the product of all the integers from 1 through N =
inclusive.=20
The factorial quickly becomes very large: 13! is too large to =
store in a=20
32-bit integer on most computers, and 70! is too large for most=20
floating-point variables. Your task is to find the rightmost =
non-zero=20
digit of n!. For example, 5! =3D 1 * 2 * 3 * 4 * 5 =3D 120, so the =
rightmost=20
non-zero digit of 5! is 2. Likewise, 7! =3D 1 * 2 * 3 * 4 * 5 * 6 =
* 7 =3D=20
5040, so the rightmost non-zero digit of 7! is 4. <BR><BR>PROGRAM =
NAME:=20
fact4<BR>INPUT FORMAT<BR>A single positive integer N no larger =
than 4,220.=20
<BR>SAMPLE INPUT (file fact4.in) <BR>7<BR><BR>OUTPUT FORMAT<BR>A =
single=20
line containing but a single digit: the right most non-zero digit =
of N! .=20
<BR>SAMPLE OUTPUT (file=20
=
fact4.out)<BR>4<BR><BR><BR><BR>Factorials<BR><BR>=BD=D7=B3=CB<BR><BR>=D2=EB=
by=20
=
!Starliu<BR><BR>N=B5=C4=BD=D7=B3=CB=D0=B4=D7=F7N!=B1=ED=CA=BE=D0=A1=D3=DA=
=B5=C8=D3=DAN=B5=C4=CB=F9=D3=D0=D5=FD=D5=FB=CA=FD=B5=C4=B3=CB=BB=FD=A1=A3=
=BD=D7=B3=CB=BB=E1=BA=DC=BF=EC=B5=C4=B1=E4=B4=F3=A3=AC=C8=E713!=BE=CD=B1=D8=
=D0=EB=D3=C332=CE=BB=D5=FB=CA=FD=C0=E0=D0=CD=C0=B4=B4=E6=B4=A2=A3=AC70=A3=
=A1=BC=B4=CA=B9=D3=C3=B8=A1=B5=E3=CA=FD=D2=B2=B4=E6=B2=BB=CF=C2=C1=CB=A1=A3=
=C4=E3=B5=C4=C8=CE=CE=F1=CA=C7=D5=D2=B5=BD=BD=D7=B3=CB=D7=EE=BA=F3=C3=E6=B5=
=C4=B7=C7=C1=E3=CE=BB=A1=A3=BE=D9=B8=F6=C0=FD=D7=D3,5!=3D1*2*3*4*5=3D120=CB=
=F9=D2=D45!=B5=C4=D7=EE=BA=F3=C3=E6=B5=C4=B7=C7=C1=E3=CE=BB=CA=C72=A3=AC7=
=A3=A1=3D1*2*3*4*5*6*7=3D5040=A3=AC=CB=F9=D2=D4=D7=EE=BA=F3=C3=E6=B5=C4=B7=
=C7=C1=E3=CE=BB=CA=C74=A1=A3<BR><BR>PROGRAM=20
NAME: fact4<BR>INPUT =
FORMAT<BR>=B9=B2=D2=BB=D0=D0=A3=AC=D2=BB=B8=F6=D5=FB=CA=FD=B2=BB=B4=F3=D3=
=DA4=A3=AC220=B5=C4=D5=FB=CA=FDN=A1=A3<BR><BR>SAMPLE INPUT=20
(file fact4.in) <BR>7<BR>OUTPUT =
FORMAT<BR>=B9=B2=D2=BB=D0=D0=A3=AC=CA=E4=B3=F6N!=D7=EE=BA=F3=C3=E6=B5=C4=B7=
=C7=C1=E3=CE=BB=A1=A3<BR><BR>SAMPLE=20
OUTPUT (file fact4.out)<BR>4</DIV>
<HR>
<P><STRONG>USACO 3.2.1 Factorials=20
=
<BR>=CC=E1=BD=BB=B4=CE=CA=FD:1=B4=CE<BR><BR>=C8=A1=C4=A3100000=BF=C9=B1=A3=
=D6=A4=D4=DA=CC=E2=C4=BF=B7=B6=CE=A7=C4=DA=D3=D0=D5=FD=C8=B7=BD=E2,=D3=A6=
=CE=AA=CC=E2=C4=BF=B7=B6=CE=A7=C4=DA2=BA=CD5=B5=C4=BB=FD=B2=BB=B9=BB10000=
0.=20
</STRONG></P>
<P><STRONG>{<BR>TASK:fact4<BR>LANG:PASCAL<BR>}<BR>program=20
fact4;<BR>var<BR> n:integer;<BR>procedure=20
init;<BR>begin<BR> =20
assign(input,'fact4.in');reset(input);<BR> =20
readln(n);<BR> =
close(input);<BR>end;<BR>procedure=20
work;<BR>var<BR> =
i:integer;<BR> =20
ans:qword;<BR>begin<BR> =20
assign(output,'fact4.out');rewrite(output);<BR> =20
ans:=3D1;<BR> for i:=3D1 to n=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
ans:=3Dans*i;<BR> &n=
bsp; =20
while ans mod 10=3D0 do ans:=3Dans div=20
=
10;<BR> =
=20
if ans>100000 then ans:=3Dans mod=20
100000;<BR> =
end;<BR> =20
while ans mod 10=3D0 do ans:=3Dans div 10;<BR> =
writeln(ans mod=20
10);<BR> =
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.</STRONG></P>
<P>
<P></P>
=
<P><STRONG>=C4=B3=C4=EA=C9=CF=BA=A3=CA=D0=CA=D0=D1=A1=B5=C4=D7=F6=B7=A8,=B2=
=BB=B9=FD=CA=D0=D1=A1=D3=C3=C1=CB=B8=DF=BE=AB</STRONG></P>
<P><STRONG>The insight for this problem is that 0's at the end of =
a number=20
come from it being divisible by 10, or equivalently, by 2 and 5.=20
Furthermore, there are always more 2s than 5s in a factorial.=20
</STRONG></P>
<P><STRONG>To get the last digit of the factorial, we can run a =
loop to=20
calculate it modulo 10, as long as we don't include any 2s or 5s =
in the=20
product. Of course, we want to exclude the same number of 2s and =
5s, so=20
that all we're really doing is ignoring 10s. So after the loop, we =
need to=20
multiply in any extra 2s that didn't have 5s to cancel them out.=20
</STRONG></P><PRE><STRONG>/*
PROG: fact4
ID: rsc001
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
void
main(void)
{
FILE *fin, *fout;
int n2, n5, i, j, n, digit;
fin =3D fopen("fact4.in", "r");
fout =3D fopen("fact4.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%d", &n);
digit =3D 1;
n2 =3D n5 =3D 0;
for(i=3D2; i<=3Dn; i++) {
j =3D i;
while(j%2 =3D=3D 0) {
n2++;
j /=3D 2;
}
while(j%5 =3D=3D 0) {
n5++;
j /=3D 5;
}
digit =3D (digit * j) % 10;
}
for(i=3D0; i<n2-n5; i++)
digit =3D (digit * 2) % 10;
fprintf(fout, "%d\n", digit);
exit(0);
}</STRONG></PRE>
<P></P>
<HR>
</DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/b7b1666324db02640d33fad8.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 3.1.6 Stamps =CC=E2=BD=E2', 'USACO 3.1.6 Stamps =
=CC=E2=BD=E2','/leokan/blog/item/b5895160134537db8cb10dcd.html'];
var post =3D [true,'USACO 3.2.2 Stringsobits =CC=E2=BD=E2','USACO 3.2.2 =
Stringsobits =CC=E2=BD=E2', =
'/leokan/blog/item/727307463c56d40d6a63e562.html'];
if(pre[0] || post[0]){
document.write('<div =
style=3D"height:5px;line-height:5px;"> </div><div id=3D"in_nav">');
if(pre[0]){
document.write('=C9=CF=D2=BB=C6=AA=A3=BA<a href=3D"' + pre[3] + '" =
title=3D"' + pre[1] + '">' + pre[2] + '</a> ');
}
if(post[0]){
document.write('=CF=C2=D2=BB=C6=AA=A3=BA<a href=3D"' + post[3] + '" =
title=3D"' + post[1] + '">' + post[2] + '</a>');
}
document.write('</div>');
}
/*]]>*/
</SCRIPT>
</DIV>
<DIV class=3Dline></DIV>
<STYLE type=3Dtext/css>#in_related_doc A {
TEXT-DECORATION: none
}
</STYLE>
<DIV id=3Din_related_tmp></DIV>
<SCRIPT language=3Djavascript type=3Dtext/javascript>
/*<![CDATA[*/
function HI_MOD_IN_RELATED_DOC_CALLBACK(arg){
if(arg.length <=3D 1) return false;
var hasMore =3D arg[0];
var D=3Dfunction(A,B){A[A.length]=3DB;}
if(arg.length % 2 =3D=3D 0) D(arg, ["","","",""]);
var html =3D ['<div id=3D"in_related_doc"><div =
class=3D"tit">=CF=E0=B9=D8=CE=C4=D5=C2=A3=BA</div>'];
D(html, '<table cellpadding=3D"0" cellspacing=3D"3" border=3D"0">');
for(var i =3D 1, j =3D arg.length; i < j; i +=3D 2){
D(html, '<tr>');
D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>•</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i][3] + =
'/blog/item/' + arg[i][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i][0] + '">' + arg[i][1] + '</a>');
D(html, new Array(10).join('\u3000'));
D(html, '</td>');
if(arg[i + 1][0] !=3D "")
D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>•</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i + 1][3] + =
'/blog/item/' + arg[i + 1][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i + 1][0] + '">' + arg[i + 1][1] + '</a></td>');
else
D(html, '<td> </td><td> </td>');
D(html, '</tr>');
}
if(hasMore) D(html, '<tr><td colspan=3D"4"><a target=3D"_blank" =
href=3D"/sys/search?pageno=3D1&type=3D7&sort=3D1&word=3DUSACO%203%2E2%2E1=
%20Factorials%20%CC%E2%BD%E2&item=3Db7b1666324db02640d33fad8">=B8=FC=B6=E0=
>></a></td></tr>');
D(html, '</table></div><div class=3D"line"> </div>');
var div =3D document.getElementById('in_related_tmp');
if(div){
div.innerHTML =3D html.join('');
while(div.firstChild){
div.parentNode.insertBefore(div.firstChild, div);
}
div.parentNode.removeChild(div);
}
}
if(RelatedDocData =3D=3D -1){ // not supported xhr
var script =3D document.createElement('script');
script.type =3D 'text/javascript';
script.src =3D =
'/sys/search?type=3D8&word=3DUSACO%203%2E2%2E1%20Factorials%20%CC%E2%BD%E=
2&item=3Db7b1666324db02640d33fad8&t=3D' + new Date().getTime();
document.getElementsByTagName('HEAD')[0].appendChild(script);
}else if(RelatedDocData =3D=3D null){
GetAndEval =3D true;
}else{
eval(RelatedDocData);
}
/*]]>*/
</SCRIPT>
<DIV id=3Din_reader>
<DIV class=3Dtit>=D7=EE=BD=FC=B6=C1=D5=DF=A3=BA</DIV>
<SCRIPT>
var g_spAnnony=3Dtrue;
var g_read=3D[
{}
];
g_read.length=3Dg_read.length-1;
var _rh1=3D"";
var _rh2=3D"";
function wrreader(){
_rh1 +=3D '<table width=3D"100%" ><tr>';
_rh2+=3D'<tr>';
if(g_spAnnony){
_rh1+=3D'<td align=3D"center" width=3D"10%" ><img border=3D"0" =
width=3D"55" height=3D"55" =
src=3D"http://img.baidu.com/hi/img/portraitn.jpg"></td>';
_rh2+=3D'<td> </td>';
if(g_read.length>0){
_rh1+=3D'<td align=3D"left" width=3D"12%">';
}else{
_rh1+=3D'<td align=3D"left" width=3D"100%">';
}
_rh1+=3D"<a =
href=3D'http://passport.baidu.com/?login&tpl=3Dsp&tpl_reg=3Dsp&u=3D"+myre=
f+"' =
target=3D'_self'>=B5=C7=C2=BC</a>=BA=F3=A3=AC=C4=FA=BE=CD=B3=F6=CF=D6=D4=DA=
=D5=E2=C0=EF=A1=A3</td>";
_rh2+=3D'<td> </td>'
}
if(g_read.length=3D=3D0){
if(!g_spAnnony){
_rh1+=3D'<td align=3Dleft =
width=3D"100%">=D7=EE=BD=FC=BB=B9=C3=BB=D3=D0=B5=C7=C2=BC=D3=C3=BB=A7=BF=B4=
=B9=FD=D5=E2=C6=AA=CE=C4=D5=C2=A1=AD=A1=AD</td>';
_rh2+=3D'<td> </td>';
}
}else{
for(i=3D0,len=3Dg_read.length;i<len;i++){
_rh1+=3D'<td align=3D"center" valign=3D"bottom" width=3D"10%" =
class=3D"user"><a href=3D"/'+g_read[i][0]+'" target=3D"_blank"><img =
border=3D"0" =
src=3D"http://himg.baidu.com/sys/portraitn/item/'+g_read[i][1]+'.jpg"></a=
></td>';
_rh2+=3D'<td align=3D"center" valign=3D"top" class=3D"user"><a =
href=3D"/'+g_read[i][0]+'" target=3D"_blank">'+g_read[i][2]+'</a></td>';
}
}
_rh1+=3D'<td width=3D"100%"></td></tr>';
_rh2+=3D'<td></td></tr></table>';
document.write(_rh1+_rh2);
}
wrreader();
</SCRIPT>
</DIV>
<DIV class=3Dline></DIV>
<SCRIPT language=3DJavaScript>
allkey=3Dallkey+"142d077b0bb076f40bd18714_b7b1666324db02640d33fad8_";
</SCRIPT>
<DIV id=3Din_comment><A name=3Dcomment></A>
<DIV class=3Dtit>=CD=F8=D3=D1=C6=C0=C2=DB=A3=BA</DIV>
<SCRIPT>
function writecmt(type,id,cmtname,cmturl,portraitId){
var html1=3D"";
if(type=3D=3D1){
html1=3D"<a name=3D'"+id+"' href=3D'"+cmturl+"' target=3D'_blank' =
title=3D'"+cmturl+"'><img border=3D'0' =
src=3D'http://himg.baidu.com/sys/portraitn/item/"+portraitId+".jpg'><br>"=
+cmtname+"</a>";
}else{
if(cmtname=3D=3D"" || cmtname=3D=3D"=C4=E4=C3=FB=CD=F8=D3=D1"){
if(cmturl=3D=3D""){
html1=3D"<a name=3D'"+id+"'>=C4=E4=C3=FB=CD=F8=D3=D1</a>";
}else{
html1=3D"<a name=3D'"+id+"' href=3D'"+cmturl+"' target=3D'_blank' =
title=3D'"+cmturl+"'>"+cmtname+"</a>";
}
}else{
if(cmturl=3D=3D""){
html1=3D"<div class=3D'f14' style=3D'display:inline'>=CD=F8=D3=D1:<a =
name=3D'"+id+"'>"+cmtname+"</a></div>";
}else{
html1=3D"<div class=3D'f14' style=3D'display:inline'>=CD=F8=D3=D1:<a =
name=3D'"+id+"' href=3D'"+cmturl+"' target=3D'_blank' =
title=3D'"+cmturl+"'>"+cmtname+"</a></div>";
}
}
}
document.write(html1);
}
</SCRIPT>
<DIV id=3Dpage></DIV></DIV>
<DIV id=3Din_send><A name=3Dsend></A>
<FORM id=3DpopFormSubmit name=3Dform1 onsubmit=3D"return checkcmtform()" =
action=3D/leokan/commit method=3Dpost><INPUT type=3Dhidden value=3D8 =
name=3Dct> <INPUT=20
type=3Dhidden value=3D1 name=3Dcm> <INPUT type=3Dhidden =
value=3Db7b1666324db02640d33fad8=20
name=3DspBlogID>
<SCRIPT language=3DJavaScript>
document.write("<input type=3D'hidden' name=3D'spRefURL' =
value=3D'"+window.location.href+"'>");
</SCRIPT>
=20
<DIV class=3Dtit>=B7=A2=B1=ED=C6=C0=C2=DB=A3=BA</DIV>
<TABLE cellSpacing=3D5 cellPadding=3D0 width=3D620 border=3D0>
<TBODY>
<TR>
<TD class=3Df14>=D0=D5=A1=A1=C3=FB=A3=BA</TD>
<TD><INPUT id=3DspBlogCmtor style=3D"WIDTH: 220px" =
onfocus=3DhidErr(1);=20
tabIndex=3D1 maxLength=3D49 onchange=3D"checkname('spBlogCmtor')"=20
name=3DspBlogCmtor>
<SCRIPT>
document.write(" <a =
href=3D'http://passport.baidu.com/?reg&tpl=3Dsp&return_method=3Dget&skip_=
ok=3D1&u=3Dhttp://hi.baidu.com/sys/reg/' =
target=3D'_blank'>=D7=A2=B2=E1</a>");
document.write(" | <a =
href=3D'http://passport.baidu.com/?login&tpl=3Dsp&tpl_reg=3Dsp&u=3D"+myre=
f+"'>=B5=C7=C2=BC</a>");
</SCRIPT>
=20
<DIV id=3Dnmerror style=3D"DISPLAY: =
none">*=D0=D5=C3=FB=D7=EE=B3=A4=CE=AA50=D7=D6=BD=DA</DIV></TD></TR>
<TR id=3D1_err style=3D"DISPLAY: none">
<TD> </TD>
<TD>
<DIV class=3Derror id=3D1_err_con></DIV></TD></TR>
<TR>
<TD class=3Df14>=CD=F8=D6=B7=BB=F2=D3=CA=CF=E4=A3=BA</TD>
<TD><INPUT id=3DspBlogCmtURL style=3D"WIDTH: 360px" =
onfocus=3DhidErr(2);=20
tabIndex=3D2 maxLength=3D128 =
onchange=3D"checkeandu('spBlogCmtURL')"=20
name=3DspBlogCmtURL> (=D1=A1=CC=EE)</TD>
<SCRIPT>
G("spBlogCmtor").value=3D"";
G("spBlogCmtURL").value=3D"";
</SCRIPT>
</TR>
<TR id=3D2_err style=3D"DISPLAY: none">
<TD> </TD>
<TD>
<DIV class=3Derror id=3D2_err_con></DIV></TD></TR>
<TR>
<TD class=3Df14 vAlign=3Dtop>=C4=DA=A1=A1=C8=DD=A3=BA</TD>
<TD><TEXTAREA id=3DspBlogCmtText style=3D"WIDTH: 520px; HEIGHT: =
155px" onfocus=3DhidErr(3); tabIndex=3D3 =
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -