TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

kvadratici.cpp    707 b      izvorni kod rešenja
kvadratici.pas    350 b      izvorni kod rešenja
kvadratici.tests.7z    860 b      test primeri

zadatak: Kvadratici

Data je celobrojna kvadratna rešetka u ravni dimenzija n x m (ima nm kvadratića). Koliko ima različitih kvadrata čija su sva temena u čvorovima ove rešetke (stranice tih kvadrata ne moraju da budu paralelne sa ivicama kvadratne rešetke)?

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza.) U prvom i jedinom redu standradnog ulaza nalaze se dva prirodna broja n i m - dimenzije kvadratne rešetke (1 ≤ n, m ≤ 109).

Izlaz.

(Izlazne podatke ispisati na standardan izlaz.) Neka je traženi broj kvadrata K. Na standardni izlaz ispisati ostatak pri deljenju broja K sa 109 + 7.

Ograničenja.

U 40% test primera 1 ≤ n, m ≤ 100.
U 60% test primera 1 ≤ n, m ≤ 1.000.
U 80% test primera 1 ≤ n, m ≤ 1.000.000.

Primer 1.

standardni ulaz      standardni izlaz
2 3
        
10

Primer 2.

standardni ulaz      standardni izlaz
500 501
        
271062715
fajl: kvadratici.cpp
#include <cstdlib>
#include <cstdio>
#include <cmath>

const int MODUO = 1000000007;

long long n, m, sol, tmp1, tmp2;

int main() {

  scanf("%d%d", &n, &m);
  if (m < n) {
    long long tmp = m; m = n; n = tmp;
  }

  sol = 0;

  tmp1 = ((n + 1) * (m + 1)) % MODUO;
  tmp2 = (n * (n + 1) / 2) % MODUO;
  sol = (sol + tmp1 * tmp2) % MODUO;

  sol = (sol + tmp2 * tmp2) % MODUO;

  tmp1 = ((n + m + 2) * (2 * n + 1)) % MODUO;
  tmp1 = (tmp1 * tmp2) % MODUO;
  sol = (sol - tmp1 * 333333336) % MODUO;
  // ovo je umesto deljenja sa 3 jer je 333333336 inverz za 1/3
  // u polju Z_p, gde je p = 10^9 + 7 (prost broj)

  //bitno
  if (sol < 0) sol += MODUO;

  printf("%d\n", sol);
  return 0;
}
fajl: kvadratici.pas
const
  MODUO = 1000000007;

var
  m, n, sol, tmp : int64;
  i : longint;

begin

  readln(n, m);

  if (m < n) then begin
      tmp := m; m := n; n := tmp;
  end;

  sol := 0;

  for i := 1 to n do begin
      tmp := ((n - i + 1) * (m - i + 1)) mod MODUO;
      sol := (sol + i * tmp) mod MODUO;
  end;

  writeln(sol);

end.