Cod sursa(job #1723491)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 30 iunie 2016 19:15:37
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.85 kb
#include <fstream>

using namespace std;

const int N_MAX = 405;

int Roots[N_MAX * N_MAX + 1];

inline int getInscribedRectangles(int Height, int Width) {
  int Count = 1;
  for(int i = 1; i < Height; i++) {
    int D = Width * Width - 4 * i * (Height - i);
    if(D >= 0) {
      int R = Roots[D];
      if(R * R == D and !((Width ^ R) & 1)) {
        if(!R) Count++;
        else if(R < Width) Count += 2;
      }
    }
  }
  return Count;
}

int main() {
  ifstream f("dreptunghiuri.in");
  ofstream g("dreptunghiuri.out");
  
  int N, M;
  
  f >> N >> M;
  
  for(int i = 1; i <= N_MAX; i++)
    Roots[i * i] = i;
  
  int64_t Answer = 0;
  for(int i = 1; i < N; i++) {
    for(int j = 1; j < M; j++) {
      Answer += getInscribedRectangles(i, j) * (N - i) * (M - j);
    }
  }
  
  g << Answer << "\n";
  return 0;
}