UVa 106 - Fermat vs Pythagoras(数论题目)

题目来源:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=42

 Fermat vs. Pythagoras 

Background

Computer generated and assisted proofs and verification occupy a small niche in the realm of Computer Science. The first proof of the four-color problem was completed with the assistance of a computer program and current efforts in verification have succeeded in verifying the translation of high-level code down to the chip level.

This problem deals with computing quantities relating to part of Fermat's Last Theorem: that there are no integer solutions ofUVa 106 - Fermat vs Pythagoras(数论题目) for n > 2.

The Problem

Given a positive integer N, you are to write a program that computes two quantities regarding the solution of

UVa 106 - Fermat vs Pythagoras(数论题目)

where xy, and z are constrained to be positive integers less than or equal to N. You are to compute the number of triples (x,y,z) such that x<yz, and they are relatively prime, i.e., have no common divisor larger than 1. You are also to compute the number of valuesUVa 106 - Fermat vs Pythagoras(数论题目) such that p is not part of any triple (not just relatively prime triples).

The Input

The input consists of a sequence of positive integers, one per line. Each integer in the input file will be less than or equal to 1,000,000. Input is terminated by end-of-file.

The Output

For each integer N in the input file print two integers separated by a space. The first integer is the number of relatively prime triples (such that each component of the triple is UVa 106 - Fermat vs Pythagoras(数论题目) ). The second number is the number of positive integers UVa 106 - Fermat vs Pythagoras(数论题目) that are not part of any triple whose components are all UVa 106 - Fermat vs Pythagoras(数论题目) . There should be one output line for each input line.

Sample Input

10
25
100

Sample Output

1 4
4 9
16 27
解题思路:

这是一道数论题,用数学的语言描述就是:x, y, z∈N,给定一个数n,找出所有的x, y, z ≤ n,使得x2 + y2 = z2成立。如果要穷举所有的x, y, z的话,按照题目所给的数据量,肯定是无法在限定时间内完成的。考虑利用毕达哥拉斯数的性质生成所有的x, y, z来解决,数学推导简要介绍如下:

先假定x, y, z两两互质,由于x, y互质,故x, y中至少有1个是奇数。下面用反证法证明x和y中有且只有1个奇数。假定x, y都为奇数,设:

  • x = 2a + 1
  • y = 2b + 1
  • x2 + y2 = (2a + 1)2 + (2b + 1)2 
    = 4(a2 + b2 + a + b) + 2

又因为x2和y2是奇数,则z2是偶数,且必能被4整除,与上式矛盾,因此x, y中只有一个奇数。

假设x为奇数,y为偶数,则z为奇数,2z与2x的最大公因数为2,2z和2x可分别写作

  • 2z = (z + x) + (z - x)
  • 2x = (z + x) - (z - x)

那么跟据最大公因数性质,z + x和z - x的最大公因数也为2,又因为:

  • (z + x)(z - x) = y2,两边同除以4得:
    ((z + x) / 2)((z - x) / 2) = (y / 2)2

故可令:

  • z + x = 2m2, z - x = 2n2
    其中z = m + n, x = m - n(m与n互质)

则有:

  • y2 = z2 - x2 = 2m22n2 = 4m2n2
    即y = 2mn。

综上所述,可得到下式:

  • x = m2 - n2, y = 2mn, z = m2 + n2. (m, n为任意自然数)

这里还有一个问题:题目要求统计(x, y, z)三元组的数量时只统计x,y和z两两互质的的情况,这个问题用上面的算法就可以解决了。但对于统计p的数量,题目并不限定三元组是两两互质的。但是上式不能生成所有x, y, z并不是两两互质的情况。然而假设x与y最大公因数w不为1,则z也必能被w整除,因此w为x, y, z三个数的公因数。归纳总结可知,所有非两两互质的x0, y0, z0都可由一组互质的x, y, z乘以系数得到。根据以上理论就可以快速的求解了。


参考代码:
 #include <cstdio>
#include <cmath>
#include <cstring>
#define N 1000010
bool used[N]; long long gcd(long long a , long long b)
{ return b== ? a: gcd(b,a%b); } int main()
{
long long n,a,b,c;
long long count1,count2;
while(scanf("%lld",&n)!=EOF)
{
count1=count2=;
memset(used,,sizeof(used));
long long m=(long long)sqrt(n+0.5);
for(long long t=; t<=m; t+=)
for(long long s=t+; s*t<=n; s+=)
if(gcd(s,t)==) //s>t>=1且s与t互质
{
a=s*t; //奇数
b=(s*s-t*t)/; //偶数
c=(s*s+t*t)/; //奇数
if(c<=n) //在n范围内的PPT
{
count1++;
//printf("本原勾股数组:%lld %lld %lld\n",a,b,c);
if(!used[a]) { count2++; used[a]=; }
if(!used[b]) { count2++; used[b]=; }
if(!used[c]) { count2++; used[c]=; } for(int j=; c*j<=n; j++) //j是倍数
{
if(!used[a*j]) { count2++; used[a*j]=; }
if(!used[b*j]) { count2++; used[b*j]=; }
if(!used[c*j]) { count2++; used[c*j]=; }
}
}
}
printf("%lld %lld\n",count1,n-count2);
}
return ;
}
上一篇:获取地图文档(*.mxd)中比例尺问题


下一篇:[Git] Git 文件归档, include submodule