SPOJ 91 — Two squares or not two squares (code: TWOSQRS)
给出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 winstyprogram 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) […]