#include <bits/stdc++.h> using namespace std; vector<bool> is_square; bool should_break(int a, int b, int h, int n2) { return h*h + a*a + b*b > n2; } int count_possibilities(int n, int cached_n) { int result = 0; int b2; int start = (cached_n+1) * (cached_n+1); int end_for = n*n; for(int curr_n=start; curr_n<=end_for; curr_n++) { if(!is_square[curr_n]) { continue; } for(int h=1; h<=n; h++) { for(int a=1; a<=n; a++) { /*for(int b=1; b<=n; b++) { result += (int)(curr_n*curr_n == h*h + a*a + b*b); } continue;*/ b2 = curr_n - h*h - a*a; //if(b2 >= is_square.size()) { cout << "wyszlo" << b2 << endl; } if(b2 < a*a) { break; } result += (int)is_square[b2]; //if(is_square[b2]) { cout << a << " " << sqrt(b2) << " " << h << " = " << sqrt(curr_n) << endl; } //cout << "nie zawsze break" << endl; } } } return result; } int main() { char buffer[100]; int n, result=0; int n2; is_square.resize(25000001, false); vector<int> d(251,0); d[0]=0; d[1]=55;d[2]=246;d[3]=570;d[4]=1019;d[5]=1630;d[6]=2341;d[7]=3200;d[8]=4181;d[9]=5326;d[10]=6559; d[11]=8004;d[12]=9507;d[13]=11169;d[14]=13005;d[15]=14936;d[16]=16960;d[17]=19146;d[18]=21520;d[19]=23975;d[20]=26634; d[21]=29375;d[22]=32155;d[23]=35240;d[24]=38344;d[25]=41686;d[26]=45102;d[27]=48698;d[28]=52217;d[29]=56083;d[30]=60033; d[31]=64035;d[32]=68451;d[33]=72822;d[34]=77166;d[35]=81927;d[36]=86596;d[37]=91520;d[38]=96637;d[39]=101765;d[40]=106873; d[41]=112556;d[42]=118051;d[43]=123697;d[44]=129497;d[45]=135555;d[46]=141591;d[47]=147875;d[48]=154240;d[49]=160689;d[50]=167451; d[51]=174117;d[52]=181016;d[53]=188173;d[54]=195314;d[55]=202682;d[56]=210028;d[57]=217674;d[58]=225267;d[59]=233394;d[60]=241388; d[61]=249364;d[62]=257728;d[63]=266114;d[64]=274401;d[65]=283202;d[66]=291951;d[67]=300990;d[68]=310141;d[69]=319302;d[70]=328477; d[71]=338102;d[72]=347523;d[73]=357280;d[74]=367319;d[75]=377404;d[76]=387381;d[77]=397910;d[78]=408165;d[79]=418716;d[80]=429378; d[81]=440521;d[82]=451076;d[83]=462454;d[84]=473360;d[85]=484454;d[86]=496470;d[87]=507899;d[88]=519515;d[89]=531626;d[90]=543652; d[91]=555898;d[92]=568157;d[93]=580431;d[94]=592623;d[95]=606001;d[96]=618688;d[97]=631591;d[98]=645027;d[99]=658143;d[100]=671258; d[101]=684844;d[102]=698524;d[103]=712147;d[104]=726735;d[105]=740406;d[106]=754131;d[107]=768840;d[108]=783048;d[109]=797737;d[110]=812483; d[111]=827507;d[112]=842019;d[113]=857538;d[114]=872986;d[115]=888232;d[116]=903631;d[117]=919506;d[118]=935101;d[119]=951197;d[120]=966956; d[121]=983450;d[122]=999749;d[123]=1016616;d[124]=1032725;d[125]=1049846;d[126]=1066561;d[127]=1083086;d[128]=1100498;d[129]=1117861;d[130]=1134938; d[131]=1153063;d[132]=1170476;d[133]=1188147;d[134]=1206557;d[135]=1224606;d[136]=1242570;d[137]=1261294;d[138]=1279396;d[139]=1297865;d[140]=1317249; d[141]=1335680;d[142]=1354889;d[143]=1373963;d[144]=1393249;d[145]=1412771;d[146]=1432607;d[147]=1452225;d[148]=1471168;d[149]=1491882;d[150]=1511687; d[151]=1532389;d[152]=1552466;d[153]=1573401;d[154]=1593550;d[155]=1614575;d[156]=1635321;d[157]=1656287;d[158]=1678286;d[159]=1699288;d[160]=1720101; d[161]=1742086;d[162]=1763550;d[163]=1785735;d[164]=1807671;d[165]=1830112;d[166]=1851635;d[167]=1875211;d[168]=1896757;d[169]=1919198;d[170]=1942571; d[171]=1965337;d[172]=1988284;d[173]=2011353;d[174]=2035146;d[175]=2058329;d[176]=2082263;d[177]=2106032;d[178]=2129411;d[179]=2154001;d[180]=2178198; d[181]=2202339;d[182]=2226868;d[183]=2251099;d[184]=2275492;d[185]=2300620;d[186]=2325868;d[187]=2350704;d[188]=2376213;d[189]=2401568;d[190]=2426407; d[191]=2452917;d[192]=2477962;d[193]=2503818;d[194]=2530316;d[195]=2427751;d[196]=2453414;d[197]=2480603;d[198]=2506871;d[199]=2533454;d[200]=2560861; d[201]=2587785;d[202]=2614030;d[203]=2642306;d[204]=2669063;d[205]=2696721;d[206]=2724177;d[207]=2752484;d[208]=2779574;d[209]=2808365;d[210]=2836406; d[211]=2864151;d[212]=2893405;d[213]=2921809;d[214]=2950626;d[215]=2979254;d[216]=3008024;d[217]=3036856;d[218]=3066643;d[219]=3096021;d[220]=3125241; d[221]=3155615;d[222]=3185450;d[223]=3215385;d[224]=3245427;d[225]=3275474;d[226]=3305387;d[227]=3335974;d[228]=3367143;d[229]=3397305;d[230]=3429242; d[231]=3460076;d[232]=3489867;d[233]=3522254;d[234]=3553286;d[235]=3585469;d[236]=3616600;d[237]=3648626;d[238]=3679485;d[239]=3712998;d[240]=3744392; d[241]=3776873;d[242]=3809676;d[243]=3843180;d[244]=3874732;d[245]=3908292;d[246]=3940855;d[247]=3973874;d[248]=4007726;d[249]=4041320;d[250]=4074428; // dla n=2000: 671258 // n=1000: 167000 cos int pomoc, n_policzone; fgets(buffer, sizeof(buffer), stdin); //sscanf(buffer, " %d %d %d ", &n, &pomoc, &n_policzone); sscanf(buffer, " %d ", &n); int shift = 20; n2 = n * n; for(int i=1; i<=n; i++) { is_square[i*i] = true; } int low_n = 0; int limit = d.size(); for(int i=1; i<limit; i++) { if(d[i] == 0) {break;} if(n >= i*shift) { low_n = i*shift; result = d[i]; } else { break; } } //result = pomoc; //low_n = n_policzone; int part_result = count_possibilities(n, low_n); result += part_result; /*result = 0; for(int h=1; h<=n; h++) { //cout << h << endl; if(should_break(1,1,h,n2)) { break; } for(int a=1; a<=n; a++) { //cout << a << endl; if(should_break(a,a,h,n2)) { break; } for(int b=a; b <= n; b++) { //cout << b << endl; if(should_break(a,b,h,n2)) { break; } result += (int)is_square[a*a + b*b + h*h]; if(is_square[a*a + b*b + h*h]) { //cout << a << " " << b << " " << h << " " << sqrt(a*a + b*b + h*h) << endl; } } } }*/ printf("%d\n", result); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 | #include <bits/stdc++.h> using namespace std; vector<bool> is_square; bool should_break(int a, int b, int h, int n2) { return h*h + a*a + b*b > n2; } int count_possibilities(int n, int cached_n) { int result = 0; int b2; int start = (cached_n+1) * (cached_n+1); int end_for = n*n; for(int curr_n=start; curr_n<=end_for; curr_n++) { if(!is_square[curr_n]) { continue; } for(int h=1; h<=n; h++) { for(int a=1; a<=n; a++) { /*for(int b=1; b<=n; b++) { result += (int)(curr_n*curr_n == h*h + a*a + b*b); } continue;*/ b2 = curr_n - h*h - a*a; //if(b2 >= is_square.size()) { cout << "wyszlo" << b2 << endl; } if(b2 < a*a) { break; } result += (int)is_square[b2]; //if(is_square[b2]) { cout << a << " " << sqrt(b2) << " " << h << " = " << sqrt(curr_n) << endl; } //cout << "nie zawsze break" << endl; } } } return result; } int main() { char buffer[100]; int n, result=0; int n2; is_square.resize(25000001, false); vector<int> d(251,0); d[0]=0; d[1]=55;d[2]=246;d[3]=570;d[4]=1019;d[5]=1630;d[6]=2341;d[7]=3200;d[8]=4181;d[9]=5326;d[10]=6559; d[11]=8004;d[12]=9507;d[13]=11169;d[14]=13005;d[15]=14936;d[16]=16960;d[17]=19146;d[18]=21520;d[19]=23975;d[20]=26634; d[21]=29375;d[22]=32155;d[23]=35240;d[24]=38344;d[25]=41686;d[26]=45102;d[27]=48698;d[28]=52217;d[29]=56083;d[30]=60033; d[31]=64035;d[32]=68451;d[33]=72822;d[34]=77166;d[35]=81927;d[36]=86596;d[37]=91520;d[38]=96637;d[39]=101765;d[40]=106873; d[41]=112556;d[42]=118051;d[43]=123697;d[44]=129497;d[45]=135555;d[46]=141591;d[47]=147875;d[48]=154240;d[49]=160689;d[50]=167451; d[51]=174117;d[52]=181016;d[53]=188173;d[54]=195314;d[55]=202682;d[56]=210028;d[57]=217674;d[58]=225267;d[59]=233394;d[60]=241388; d[61]=249364;d[62]=257728;d[63]=266114;d[64]=274401;d[65]=283202;d[66]=291951;d[67]=300990;d[68]=310141;d[69]=319302;d[70]=328477; d[71]=338102;d[72]=347523;d[73]=357280;d[74]=367319;d[75]=377404;d[76]=387381;d[77]=397910;d[78]=408165;d[79]=418716;d[80]=429378; d[81]=440521;d[82]=451076;d[83]=462454;d[84]=473360;d[85]=484454;d[86]=496470;d[87]=507899;d[88]=519515;d[89]=531626;d[90]=543652; d[91]=555898;d[92]=568157;d[93]=580431;d[94]=592623;d[95]=606001;d[96]=618688;d[97]=631591;d[98]=645027;d[99]=658143;d[100]=671258; d[101]=684844;d[102]=698524;d[103]=712147;d[104]=726735;d[105]=740406;d[106]=754131;d[107]=768840;d[108]=783048;d[109]=797737;d[110]=812483; d[111]=827507;d[112]=842019;d[113]=857538;d[114]=872986;d[115]=888232;d[116]=903631;d[117]=919506;d[118]=935101;d[119]=951197;d[120]=966956; d[121]=983450;d[122]=999749;d[123]=1016616;d[124]=1032725;d[125]=1049846;d[126]=1066561;d[127]=1083086;d[128]=1100498;d[129]=1117861;d[130]=1134938; d[131]=1153063;d[132]=1170476;d[133]=1188147;d[134]=1206557;d[135]=1224606;d[136]=1242570;d[137]=1261294;d[138]=1279396;d[139]=1297865;d[140]=1317249; d[141]=1335680;d[142]=1354889;d[143]=1373963;d[144]=1393249;d[145]=1412771;d[146]=1432607;d[147]=1452225;d[148]=1471168;d[149]=1491882;d[150]=1511687; d[151]=1532389;d[152]=1552466;d[153]=1573401;d[154]=1593550;d[155]=1614575;d[156]=1635321;d[157]=1656287;d[158]=1678286;d[159]=1699288;d[160]=1720101; d[161]=1742086;d[162]=1763550;d[163]=1785735;d[164]=1807671;d[165]=1830112;d[166]=1851635;d[167]=1875211;d[168]=1896757;d[169]=1919198;d[170]=1942571; d[171]=1965337;d[172]=1988284;d[173]=2011353;d[174]=2035146;d[175]=2058329;d[176]=2082263;d[177]=2106032;d[178]=2129411;d[179]=2154001;d[180]=2178198; d[181]=2202339;d[182]=2226868;d[183]=2251099;d[184]=2275492;d[185]=2300620;d[186]=2325868;d[187]=2350704;d[188]=2376213;d[189]=2401568;d[190]=2426407; d[191]=2452917;d[192]=2477962;d[193]=2503818;d[194]=2530316;d[195]=2427751;d[196]=2453414;d[197]=2480603;d[198]=2506871;d[199]=2533454;d[200]=2560861; d[201]=2587785;d[202]=2614030;d[203]=2642306;d[204]=2669063;d[205]=2696721;d[206]=2724177;d[207]=2752484;d[208]=2779574;d[209]=2808365;d[210]=2836406; d[211]=2864151;d[212]=2893405;d[213]=2921809;d[214]=2950626;d[215]=2979254;d[216]=3008024;d[217]=3036856;d[218]=3066643;d[219]=3096021;d[220]=3125241; d[221]=3155615;d[222]=3185450;d[223]=3215385;d[224]=3245427;d[225]=3275474;d[226]=3305387;d[227]=3335974;d[228]=3367143;d[229]=3397305;d[230]=3429242; d[231]=3460076;d[232]=3489867;d[233]=3522254;d[234]=3553286;d[235]=3585469;d[236]=3616600;d[237]=3648626;d[238]=3679485;d[239]=3712998;d[240]=3744392; d[241]=3776873;d[242]=3809676;d[243]=3843180;d[244]=3874732;d[245]=3908292;d[246]=3940855;d[247]=3973874;d[248]=4007726;d[249]=4041320;d[250]=4074428; // dla n=2000: 671258 // n=1000: 167000 cos int pomoc, n_policzone; fgets(buffer, sizeof(buffer), stdin); //sscanf(buffer, " %d %d %d ", &n, &pomoc, &n_policzone); sscanf(buffer, " %d ", &n); int shift = 20; n2 = n * n; for(int i=1; i<=n; i++) { is_square[i*i] = true; } int low_n = 0; int limit = d.size(); for(int i=1; i<limit; i++) { if(d[i] == 0) {break;} if(n >= i*shift) { low_n = i*shift; result = d[i]; } else { break; } } //result = pomoc; //low_n = n_policzone; int part_result = count_possibilities(n, low_n); result += part_result; /*result = 0; for(int h=1; h<=n; h++) { //cout << h << endl; if(should_break(1,1,h,n2)) { break; } for(int a=1; a<=n; a++) { //cout << a << endl; if(should_break(a,a,h,n2)) { break; } for(int b=a; b <= n; b++) { //cout << b << endl; if(should_break(a,b,h,n2)) { break; } result += (int)is_square[a*a + b*b + h*h]; if(is_square[a*a + b*b + h*h]) { //cout << a << " " << b << " " << h << " " << sqrt(a*a + b*b + h*h) << endl; } } } }*/ printf("%d\n", result); return 0; } |