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;
}