NOT A BLOG | sqybi

SPOJ 91 — Two squares or not two squares (code: TWOSQRS)

Posted on 五月 6th, 2008.

给出c个数,判断它们能不能表示成两个定义在正整数集中的完全平方数的和.
看<什么是数学>看多了=.=…

传说中的A7大牛的强力解法,1.8x秒过掉,zch的纯暴力(带sqrt的)就挂了…
见程序,l和r的应用是经典…加上下面的while循环和if判断,就是整个算法了…好神奇…
没有sqrt所以常数小得多.

{
SPOJ 91; Two squares or not two squares; TWOSQRS
- sqybi’s code
- swc
}
//for my winsty
program twosqrs_sqybi;
  const
    fin = ‘twosqrs.in’;
    fout = ‘twosqrs.out’;
    mm = 1000000;

  var
    i, times, cases: longint;
    n, l, r: int64;
    f: array[0..mm]of int64;

  begin
    assign(input, fin);
    assign(output, fout);
    reset(input);
    rewrite(output);

    for i:=1 to mm do f[i] := int64(i) * i;
    readln(cases);
    for times:=1 to cases do begin
      readln(n);
      l := 0;
      r := trunc(sqrt(n));
      while l <= r do
        if f[l] + f[r] = n then
          break
        else if f[l] + f[r] > n then
          dec(r)
        else
          inc(l);
      if l <= r then
        writeln(’Yes’)
      else
        writeln(’No’);
    end;

    close(input);
    close(output);
  end.

阅读(93 次)

Make a Comment

Make A Comment: ( 2 so far )

2 Responses to “SPOJ 91 — Two squares or not two squares (code: TWOSQRS)”

Comments RSS Feed

Where's The Comment Form?