题目传送门：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=42

求给定范围n内的所有本原勾股数组个数和非勾股数的数目。

由于题目n较大，直接暴力会超时，这题需要用到数论一些结论，先阅读下面数论的一些背景知识：

背景知识

勾股数组:

所有满足a^2 + b^2 = c^2的(a,b,c)三元组，即3个数满足勾股定理。

当a,b,c最大公约数为1时，(a, b, c)称为本原勾股数组 (primitive Pythagorean triple)，所有勾股数组都可以由原本勾股数组求得：

a^2 + b^2 = c^2
=> (ka)^2 + (kb)^2 = (k*c)^2

一个关于勾股数组的定理：

每个本原勾股数组(a, b, c), 都可以由下面公式组成：
a = st, b = (s^2 - t^2)/2, c = (s^2 + t^2)/2
其中s > t, s, t为奇数，且互质。

证明如下：

首先证明下面一个引理：

引理1：本原勾股数组(a, b, c), a,b为一奇一偶，c为奇数。

枚举每种可能

  • 情况1：a,b都为奇数，a=2x+1, b=2y+1, c=2z
1
2
3
4
5
a^2 + b^2 = c^2
(2x+1)^2 + (2y+1)^2 = 4z^2
4x^2 + 4x + 4y^2+4y + 2 = 4z^2
2x^2 + 2x + 2y^2+2y + 1 = 2z^2
等式不成立，左边是奇数，右边是偶数。
  • 情况2: a,b都为偶数，那么c也是偶数，gcd(a, b, c) = 2, 不满足题意。

所以剩下最后一种情况，a,b为一奇一偶。

不妨假设a为奇数，那么b为偶数，c为奇数。

a^2 = c^2 - b^2 = (c+b)(c-b)

步骤1： 证明gcd(c+b，c-b) = 1
反证法：

1
2
3
4
5
6
7
8
9
10
11
假设存在gcd(c+b, c-b) = k, k > 1
(c+b)%k == 0, (c-b)%k == 0,
((c+b)+(c-b))%k = 0 => (2c)%k == 0
((c+b)-(c-b))%k = 0 => (2b)%k == 0
gcd(2c, 2b) = k => 2*gcd(c, b) = k
gcd(c, b) = 1(设gcd(c, b) = k, k > 1, 那么(c-b)%k == 0, (c+b)%k == 0, a%k == 0, gcd(a, b, c) = k > 1, 不满足题意。)
k = 2*gcd(c, d) = 2.
=> gcd(c+b, c-b) = k = 2,
=> c+b为偶数，c-b为偶数，与假设矛盾, 所以gcd(c+b, c-b) = 1, 证毕。

步骤2：

对a^2进行质因数分解：

1
2
3
4
a^2 = p1^t1*p2^t2*...*pn^tn, p1,...,pn为素数，t1,...,tn为偶数，保证a^2能够开方。
gcd(c+b, c-b) = 1,
=> c+b = pi^ti, c-b = pi^ti, c+b为平方数，c-b为平方数，

那么可以假设c+b=s^2 = pi^ti, c-b=t^2=pj^tj,
求得：

1
2
a=st, b=(s^2-t^2)/2, c=(s^2+t^2)/2.
gcd(s, t) = 1

下面证明s,t都为奇数：

  • s，t都为偶数：a,b都为偶数，不满足奇偶性。
  • s, t为一奇一偶：c不是整数，不符合。

所以只剩下一种情况，s, t都为奇数。

证毕，a=st, b=(s^2-t^2)/2, c=(s^2+t^2)/2, gcd(s, t)=1, s,t为奇数，s>t.

还有另外一个等价定理：

所有勾股数可以由下面公式生成(Euclid’s formula):
a=m^2-n^2, b = 2mn, c=m^2+n^2

##Solution

根据上面的本原勾股数定理，只需要枚举s，t即可，枚举范围为[1, sqrt(n)]范围内的所有奇数即可。时间复杂度为O(n)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1000005;
bool vis[N];
int gcd(ll a, ll b) {
  if (b == 0)
    return a;
  return gcd(b, a%b);
}
int main() {
  //freopen("test.txt", "r", stdin);
  ll n;
  while (cin >> n) {
    memset(vis, 0, sizeof(vis));
    int ans = 0;
    for (ll s = 1; s*s <= n; s+=1) {
      for (int t = 1; t < s && s*s + t*t <= n; t+=1) {
        ll x = s*s - t*t;
        ll y = 2*s*t;
        ll z = (s*s+t*t); // z*z = x*x + y*y.
        if (gcd(gcd(x, y), z) == 1) // check gcd(a, b, c) == 1
          ans++;
        for (int i = 1; z*i <= n; ++i)
          vis[i*x] = vis[i*y] = vis[i*z] = 1;
      }
    }
    int ans2 = 0;
    for (int i = 1; i <= n; ++i)
      if (!vis[i])
        ans2++;
    cout << ans << " " << ans2 << endl;
  }
  return 0;
}