Cod sursa(job #2292447)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 29 noiembrie 2018 16:16:58
Problema Dreptunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>
#include <iostream>

using namespace std;
long long root[160010];
int main()
{
    FILE *fin=fopen ("dreptunghiuri.in","r");
    FILE *fout=fopen ("dreptunghiuri.out","w");
    long long n,m,i,fr,h,w,dh,delta,r;
    long long sol;
    fscanf (fin,"%lld%lld",&n,&m);
    root[1]=1;
    for (i=2;i<=160000;i++){
        if ((root[i-1]+1)*(root[i-1]+1)==i)
            root[i]=root[i-1]+1;
        else root[i]=root[i-1];
    }
    sol=0;
    for (h=1;h<n;h++){
        for (w=1;w<m;w++){
            fr=0;
            sol= sol + (n-h)*(m-w);
            for (dh=1;dh<h;dh++){ // dh = lungime
                delta=w*w - 4*dh*(h-dh);
                if (delta<0 || root[delta]*root[delta]!=delta || w%2!=root[delta]%2)
                    continue; // delta nu e pp sau rad nu in Z

                r=(w+root[delta])/2;
                if (0<r && r<w)
                    fr++;
                r=(w-root[delta])/2;
                if (0<r && r<w && root[delta])
                    fr++;
            }
            //printf ("%d\n",fr);
            sol= sol + fr*(n-h)*(m-w);
        }
    }
    fprintf (fout,"%lld",sol);
    return 0;
}