Pythagoras's Revenge

题目

potenuse length C, satisfies the formula
A2 + B2 = C2
It is also well known that there exist some right triangles in which all three side lengths are integral, such as the classic:
Further examples, both having A = 12, are the following:
The question of the day is, given a fixed integer value for A, how many distinct integers B > A exist such that the hypotenuse length C is integral?
Input Each line contains a single integer A, such that 2 ≤ A < 1048576 = 220. The end of the input is designated by a line containing the value 0.
Output
For each value of A, output the number of integers B > A such that a right triangle having side lengths A and B has a hypotenuse with integral length.
A Hint and a Warning: Our hint is that you need not consider any value for B that is greater than (A2 −1)/2, because for any such right triangle, hypotenuse C satisfies B < C < B + 1, and thus cannot have integral length. Our warning is that for values of A ≈ 220, there could be solutions with B ≈ 239, and thus valuesof C2 > B2 ≈ 278. You can guarantee yourself 64-bit integer calculations by using the type long long in C++ or long in Java. But neither of those types will allow you to accurately calculate the value of C2 for such an extreme case. (Which is, after all, what makes this Pythagoras’s revenge!)

Sample Input
3
12
2
1048574
1048575
0

Sample Output
1
2
0
1
175

题意:给你直角三角形的一条较小的直角边A(整数),问:有几个也是整数的直角边B使得斜边C都是整数?(C可能到达2^78,64位存不下!
思路: 题目说了,C很大,所以含有A^2+B^2的任何思路都免谈.64位存不下!!!
设C=x+B; 则由(C^2-B^2)=a^2;得x(x+2*B)=A^2;=>x是A^2的因子!
于是可以对A进行素因子分解,再dfs组合因子作为x进行枚举,后求得B,计数.详见代码.
对于时间复杂度因式分解不成问题,关键是dfs,由于有整除因数和i的剪枝,也是可以ac的!

#include <iostream>
#include <cstdio>
#define LL long long
#include <map>

using namespace std;
map<LL,LL> mp;//除重
LL A,A2,sum,cnt;//sum用于计算B的个数,cnt用于计算A的因子数,A2即是A^2
LL factor[50];//因子
void factory(LL A)//分解成素因子
{
    cnt=0;
    for (LL i=2;i*i<=A;i++)
    {
        if (A%i==0)
        {
            factor[cnt++]=i;
            while (A%i==0) A/=i;
        }
    }
    if (A>1) factor[cnt++]=A;
}
void dfs(LL num,LL i)
{
    if (i==cnt||A2%num)//关键剪枝
        return;
    LL res=(A2/num-num);
    if (res%2==0)
    {
        res/=2;
        if (res>A&&!mp[res])
        {
            sum++;//计数
            mp[res]++;//去重
        }
    }
    dfs(num*factor[i],i);//同一个素因子允许多次使用
    dfs(num,i+1);//不取第i个素因子
}
int main()
{
    while (scanf("%lld",&A)==1&&A)
    {
        mp.clear();
        A2=A*A;
        sum=0;
        factory(A);
        dfs(1,0);
        printf("%lld\n",sum);
    }
    return 0;
}

声明:个人原创,仅供相互学习交流,请勿抄袭!转载请注明出处!!!