📄 usaco 1_4_3 arithmetic progressions 题解_leokan的blog.mht
字号:
void quicksort (int[], int ,int);
int pivotlist (int[], int,int);
ofstream out ("ariprog.out"); =20
int n;
int main () {
ifstream in ("ariprog.in"); =20
=20
bool array[125001] =3D {false}, noneF;
int m, upper, upperdef, def, p;=20
int places[300000], pl =3D 0;
noneF =3D true;
=20
in>>n>>m;
=20
for (int i =3D 0; i <=3D m; i++)
for (int j =3D 0; j <=3D m; j++) {
if (!array[i*i+j*j]) {
places[pl] =3D i*i+j*j; //Saving generated numbers
pl++;
}
array[i*i+j*j] =3D true;
}
=20
upper =3D 2*m*m;
upperdef =3D upper/(n-1);
=20
quicksort (places, 0, pl-1);
=20
for ( def =3D 1; def<=3Dupperdef; def++) // Loop to check for =
solutions
// It looks for solutions in
// correct order so you=20
// print the solution directly
// without sorting first, thnx to =
who said:
// Trade Memory for Speed !!
{
for ( p =3D 0; places[p]<=3D(upper-((n-2)*def)); p++) {
bool is;
is =3D true;
int where;
for (int c =3D (n-1); c>=3D0 ; c--)
if (!array[places[p]+c*def]) {
is =3D false;
where =3D (p+c*def);
break;
}
=20
if (is) {
noneF =3D false;
out<<places[p]<<" "<<def<<endl;
}
}
}
=20
if (noneF)
out<<"NONE"<<endl;
=20
return 0;
}
void quicksort (int array[], int start, int last) {
int pivot;
if (start < last) {
pivot =3D pivotlist(array, start,last);
quicksort (array, start,pivot-1);
quicksort (array, pivot+1,last);
}
}
int pivotlist(int array[], int f, int l) {
int pivotpoint;
int pivotvalue, temp;
=20
pivotvalue =3D array[f];
pivotpoint =3D f;
=20
for (int i =3D f+1;i<=3Dl; i++) {
if (array[i]<pivotvalue) {=20
pivotpoint++;
temp =3D array[i];
array[i] =3D array[pivotpoint];
array[pivotpoint] =3D temp;
}
}
temp =3D array[f];
array[f] =3D array[pivotpoint];
array[pivotpoint] =3D temp;
=20
return pivotpoint;
}</PRE>
<P></P>
<HR>
</STRONG></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
href=3D"http://hi.baidu.com/leokan/modify/blog/833ab401eb6fa107728da5d8">=
=B1=E0=BC=AD</A> |=20
<A onclick=3D"return blogdel('blogdelform')"=20
href=3D"http://hi.baidu.com/leokan/blog/item/833ab401eb6fa107728da5d8.htm=
l#">=C9=BE=B3=FD</A>=20
<FORM id=3Dblogdelform style=3D"DISPLAY: none" name=3Dblogdelform=20
action=3D/leokan/commit method=3Dpost><INPUT type=3Dhidden value=3D1 =
name=3Dct><INPUT=20
type=3Dhidden value=3D3 name=3Dcm><INPUT type=3Dhidden =
value=3D833ab401eb6fa107728da5d8=20
name=3DspBlogID><INPUT type=3Dhidden =
value=3Dhttp://hi.baidu.com/leokan/blog=20
name=3DspRefURL></FORM>
<SCRIPT language=3Djavascript>
<!--
function blogdel(str)
{
var pop=3Dnew Popup({ =
contentType:3,isReloadOnClose:false,width:340,height:80});
pop.setContent("title","=C9=BE=B3=FD=CE=C4=D5=C2");
=
pop.setContent("confirmCon","=C4=FA=C8=B7=B6=A8=D2=AA=B3=B9=B5=D7=C9=BE=B3=
=FD=D5=E2=C6=AA=CE=C4=D5=C2=BC=B0=C6=E4=CB=F9=D3=D0=C6=C0=C2=DB=C2=F0=A3=BF=
");
pop.setContent("callBack",delCallback);
pop.setContent("parameter",{fid:str,popup:pop});
pop.build();
pop.show();
return false;
}
function delCallback(para)
{
var o_pop=3Dpara["popup"];
o_pop.config.contentType=3D1;
o_pop.setContent("contentUrl","");
o_pop.reBuild();
G(para["fid"]).target=3Do_pop.iframeIdName;
eval("document."+para["fid"]).submit();
}
//-->
</SCRIPT>
| <A =
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/833ab401eb6fa107728da5d8.htm=
l#send">=C6=C0=C2=DB</A> (1)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D =
[true,'=D1=A7=CA=F5=B5=A5=BC=AB=BB=AF=C7=F7=CA=C6=B5=C4=B7=A2=D5=B9', =
'=D1=A7=CA=F5=B5=A5=BC=AB=BB=AF=C7=F7=CA=C6=B5=C4=B7=A2=D5=B9','/leokan/b=
log/item/649a424af972132708f7eff7.html'];
var post =3D =
[true,'=B9=D8=D3=DA=B1=BE=B2=A9=BF=CD=B5=C4=CB=BC=CF=EB=C8=A1=CF=F2...','=
=B9=D8=D3=DA=B1=BE=B2=A9=BF=CD=B5=C4=CB=BC=CF=EB=C8=A1=CF=F2...', =
'/leokan/blog/item/ae57c31bb72ba5feaf51339d.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%201%2E4%2E3=
%20Arithmetic%20Progressions%20%CC%E2%BD%E2&item=3D833ab401eb6fa107728da5=
d8">=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%201%2E4%2E3%20Arithmetic%20Progression=
s%20%CC%E2%BD%E2&item=3D833ab401eb6fa107728da5d8&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=3Dfalse;
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_833ab401eb6fa107728da5d8_";
</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>
<TABLE class=3Ditem=20
style=3D"TABLE-LAYOUT: fixed; OVERFLOW: hidden; WORD-WRAP: break-word"=20
cellSpacing=3D0 cellPadding=3D0 width=3D"100%" border=3D0 ;>
<TBODY>
<TR>
<TD class=3Dindex vAlign=3Dtop width=3D"5%">1</TD>
<TD vAlign=3Dtop align=3Dmiddle width=3D"10%">
<DIV class=3Duser style=3D"OVERFLOW: hidden">
<SCRIPT language=3Djavascript>
writecmt(2,"009ca618939c040334fa4117","=B2=DD=B8=F9=B5=C4=B9=CA=CA=C2","h=
ttp://www.grstory.com","0000b2ddb8f9b5c4b9cacac20000");
</SCRIPT>
</DIV></TD>
<TD class=3Dcnt style=3D"PADDING-LEFT: 20px"><SPAN =
class=3Ddate>2008=C4=EA01=D4=C225=C8=D5 =D0=C7=C6=DA=CE=E5=20
19:50 |
<SCRIPT language=3Djavascript>
<!--
var delrefurl=3Dwindow.location.href;
if((pos=3Ddelrefurl.indexOf("%2Ehtml"))!=3D-1) =
delrefurl=3Ddelrefurl.substring(0,pos+7);
else if((pos=3Ddelrefurl.indexOf(".html"))!=3D-1) =
delrefurl=3Ddelrefurl.substring(0,pos+5);
//var =
delrefurl=3D"http://hi.baidu.com/leokan/blog/item/833ab401eb6fa107728da5d=
8%2Ehtml";
document.write("<a href=3D'#' onClick=3D'return =
cmtdel(\"dform"+i+"\")'>=C9=BE=B3=FD</a><form action=3D'/leokan/commit' =
id=3D'dform"+i+"' name=3D'dform"+i+"' method=3D'post'><input =
type=3D'hidden' name=3D'ct' value=3D'8'><input type=3D'hidden' =
name=3D'cm' value=3D'2'><input type=3D'hidden' name=3D'spBlogID' =
value=3D'833ab401eb6fa107728da5d8'><input type=3D'hidden' =
name=3D'spBlogCmtID' value=3D'009ca618939c040334fa4117'><input =
type=3D'hidden' name=3D'spRefURL' =
value=3D'"+delrefurl+"/index/0#comment'></form>");
i++;
//-->
</SCRIPT>
</SPAN>
<DIV class=3Ddesc=20
style=3D"OVERFLOW: hidden; WORD-BREAK: =
normal">=C0=B4=C4=E3=B5=C4=B2=A9=BF=CD=BF=B4=BF=B4=A3=AC=B2=DD=B8=F9=B5=C4=
=B9=CA=CA=C2=B5=C8=C4=FA=BB=D8=B2=C8=A3=A1<BR>=D0=D2=B8=A3=D4=DA=C4=E3=C9=
=ED=B1=DF=A3=AC=CE=A2=D0=A6=D4=DA=C4=E3=D0=C4=BC=E4=A3=AC=BB=B6=C0=D6=CB=E6=
=C4=E3=C3=BF=CC=EC=A3=AC<BR>=D7=A3=B8=A3=C4=E3=D0=C4=CF=EB=CA=C2=B3=C9=A1=
=A2=CD=F2=CA=C2=C8=E7=D2=E2=A1=A2=BD=A1=BF=B5=D0=D2=B8=A3=BF=EC=C0=D6=C3=BF=
=D2=BB=CC=EC!<BR>=B2=DD=B8=F9=B5=C4=CC=EC=BF=D5=A3=A1=B2=DD=B8=F9=B5=C4=CA=
=C0=BD=E7=A3=A1=B2=DD=B8=F9=B5=C4=B9=CA=CA=C2=A1=AA=A1=AA=B8=F8=D0=C4=C1=E9=
=D2=BB=B8=F6=C7=E3=CB=DF=B5=C4=CE=E8=CC=A8=A3=A1</DIV></TD></TR></TBODY><=
/TABLE>
<DIV class=3Dline></DIV>
<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=3D833ab401eb6fa107728da5d8=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>gba1991 <INPUT id=3DspBlogCmtor style=3D"DISPLAY: none" =
maxLength=3D50=20
value=3Dgba1991 name=3DspBlogCmtor>
<DIV id=3Dnmerror style=3D"DISPLAY: =
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -