wustoj(x^m+y^m=z^m问题)

问题描述:

众所周知，ZiP有一个室友叫老郭，是个满分帅气暖男，只是有个习惯是*狗。

然而老郭是一个强迫症患者，他*的狗必须满足以下条件：

首先他会把n只狗排成一排，从1到n依次编号。

接着他会让ZiP给他报一个整数m。

然后任意选出三只狗编号为x,y,z，如果能满足x^m+y^m=z^m(分别代表x,y,z的m次方)，则会把狗*掉。

那么问题来了，对于n只狗，已经ZiP给定的一个数m，老郭有多少种可能*到狗？

Input

多组测试数据（不超过10组），每组一行。

有2个数，第一个是n（1<=n<=5000），第二个是m（1<=m<=100）

Output

每组输出一行，代表老郭能*到狗的可能数。

Sample Input

3 1

1000 2

1000 1

Sample Output

1 881 249500

题目分析:关于x,y,z的方程,x^n+y^n=z^n(n为大于2的整数)没有正整数解. 1995年已经被安德鲁.怀尔斯解决了,论文有200页.用的理论是椭圆曲线和模型式. 觉得挺有意思的，嘿嘿！ 我们只需要计算m=1和m=2时就好了。 m=1的时候我们只需要找x+y=z,我们循环x,不难发现要满足z-y这样的式子每次只要n-2*x手动算一下就好啦！ 当m=2时，即x*x+y*y=z*z即z*z-y*y可以开平方为整数，现在我们把三层循环变成二重循环了，就可以了，记得除以2咯！ 代码如下:

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF) {
        if (m>2)
            printf("%d\n",0);
        else {
            int num=0;
            if (m==1) {
                for (int i=1;i<=n;i++) {
                    int res=n-2*i;
                    if (res<=0) break;
                    else num+=res;
                }
                printf("%d\n",num);
            }
            else {
                for (int i=2;i<=n;i++) {
                    for (int j=1;j<=i-1;j++) {
                        if (((int)sqrt(i*i-j*j))*((int)sqrt(i*i-j*j))==(i*i-j*j))
                            num++;
                    }
                }
                printf("%d\n",num/2);
            }
        }
    }
    return 0;
}