Cod sursa(job #548105)

Utilizator DraStiKDragos Oprica DraStiK Data 7 martie 2011 09:07:09
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <algorithm>
using namespace std;

#define DIM 405

int rad[DIM*DIM];
bool pp[DIM*DIM];
long long nrt;
int N,M;

void read ()
{
    int i;

    scanf ("%d%d",&N,&M);

    for (i=0; i<DIM; ++i)
    {
        pp[i*i]=1;
        rad[i*i]=i;
    }
}

void solve ()
{
    int i,j,k,cnt,delta,x1,x2;

    for (i=1; i<=N; ++i)
        for (j=1; j<=M; ++j)
        {
            cnt=1;
            for (k=1; k<=j; ++k)
            {
                delta=i*i-4*k*(j-k);
                if (delta>=0 && pp[delta])
                {
                    x1=i+rad[delta];
                    if (!(x1&1))
                        if ((x1>>1)>=1 && (x1>>1)<i)
                            ++cnt;

                    if (delta)
                    {
                        x2=i-rad[delta];
                        if ((x2>>1)>=1 && (x2>>1)<i)
                            ++cnt;
                    }
                }
            }
            nrt+=1LL*cnt*(N-i)*(M-j);
        }

    printf ("%lld",nrt);
}

int main ()
{
    freopen ("dreptunghiuri.in","r",stdin);
    freopen ("dreptunghiuri.out","w",stdout);

    read ();
    solve ();

    return 0;
}