Cod sursa(job #781941)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 25 august 2012 14:33:35
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.2 kb
#include <cstdio>

using namespace std;

const int MaxN = 405;

int N, M, Sqrt[MaxN*MaxN];
long long Sol;

void BuildSqrt() {
    for (int i = 1; i <= N || i <= M; ++i)
        Sqrt[i*i] = i;
}

void Solve() {
    BuildSqrt();
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            int R = 0;
            for (int k = 0; k < i; ++k) {
                int a = 1, b = -j, c = k*(i-k);
                int Delta = b*b-4*a*c;
                if (Delta < 0 || (Delta && !Sqrt[Delta]))
                    continue;
                Delta = Sqrt[Delta];
                if ((-b+Delta)%2 != 0)
                    continue;
                int x1 = (-b-Delta)/2, x2 = (-b+Delta)/2;
                R += (0 <= x1 && x1 < j && (-b-Delta)%2 == 0);
                R += (0 <= x2 && x2 < j && (-b-Delta)%2 == 0 && x1 != x2);
            }
            Sol += (1LL*(N-i+1)*(M-j+1)*R);
        }
    }
}

void Read() {
    freopen("dreptunghiuri.in", "r", stdin);
    scanf("%d %d", &N, &M); --N, --M;
}

void Print() {
    freopen("dreptunghiuri.out", "w", stdout);
    printf("%lld\n", Sol);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}