http://www.lydsy.com/JudgeOnline/problem.php?id=1041

  1. 不同的解必对应着不同的本原勾股数组(一一对应);
  2. 这样的话,枚举r的所有因子作本原勾股数组的z,再用枚举m和n;
  3. 加上一些小优化,详见代码注释。
/*28ms,1284KB*/

int get(int z)
{
    if (z == 1 || z % 4 != 1) return 0; /// 由于m,n必须一奇一偶,所以z=m^2+r^2必定是模4余1的
 int n, m, cnt = 0;
    for (n = 1; 2 * n * n  < z; ++n)
    {
        m = Sqrt(z - n * n);
        if (m * m + n * n == z && __gcd(n, m) == 1) ++cnt;
    }
    return cnt;
}

int main()
{
    int r, i;
    SI(r);
    int sqrtr = Sqrt(r), cnt = 0;
    Forr(i, 1, sqrtr)
    {
        if (r % i) continue;
        cnt += get(r / i), cnt += get(i); /// 枚举本原勾股数组的z
 }
    if (sq(sqrtr) == r) cnt += get(sqrtr);
    PI(cnt * 8 + 4); /// *8是因为有正负四种组合,并且(x,y)和(y,x)算两种
 return 0;
}

Comments

comments powered by Disqus