学步园

UVA_106

    继续积累数学知识，这个题目需要用到勾股数的产生公式a=m^2-n^2，b=2*m*n，c=m^2+n^2，枚举m和n就可以求出所有<=N的互质的勾股数，然后把他们的<=N的倍数都删去，剩下的数就是不属于任何一组<=N的勾股数的数字。

#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAXD 1000010
int N, f[MAXD];
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
void solve()
{
int i, j, k, limit, num[2] = {0}, a, b, c;
for(i = 0; i <= N; i ++)
        f[i] = 1;
    limit = (int)sqrt(N + 1);
for(i = 1; i <= limit; i ++)
for(j = i + 1; j <= limit; j ++)
        {
            c = i * i + j * j;
if(c > N)
break;
            a = j * j - i * i;
            b = 2 * i * j;
if(gcd(gcd(a, b), c) == 1)
            {
                f[a] = f[b] = f[c] = 0;
                num[0] ++;
for(k = 2; k * c <= N; k ++)
                    f[a * k] = f[b * k] = f[c * k] = 0;
            }
        }
for(i = 1; i <= N; i ++)
if(f[i])
            num[1] ++;
    printf("%d %d\n", num[0], num[1]);
}
int main()
{
while(scanf("%d", &N) == 1)
    {
        solve();
    }
return 0;
}