WustOj--1546传说中的教主（思维，脑洞）

1546: 传说中的教主

Time Limit: 1 Sec Memory Limit: 128MB 64bit IO Format: %lld
Submitted: 38 Accepted: 18
[Submit][Status][Web Board]

Description

众所周知，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

881

249500

HINT

对于第一组样例，（1,2,3）满足，所以输出为1。

（1,2,3）和（2,1,3）视为同一组

Author

ZiP

题目最后只需要考虑1和2的情况

2以后的数字，都找不到一个三元对符合条件

有兴趣的同学可以通过数学证明出来

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
 
 
int main()
{
    int n,m;
    int i,j,k;
    long long a,b,c,d;
    long long cnt;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        cnt=0;
        if(m==1)
        {
            k=n;
            for(i=1;i<=n-2;i++)
            {
                if(k-2>0)
                {
                    cnt+=(k-2);
                    k-=2;
                }
            }
        }
        else if(m==2)
        {
            for(i=1;i<=n;i++)
            {
                for(j=i+1;j<=n;j++)
                {
                    a=i*i;
                    b=j*j;
                    d=(long long)sqrt(a+b);
                    c=d*d;
                    if(a+b==c&&c>b&&d<=n)
                        cnt++;

                }
            }
        }
        else
            cnt=0;
        printf("%ld\n",cnt);
    }
}

已下搬自百度回答

据说1995年已经被安德鲁.怀尔斯解决了,论文有200页.用的理论是椭圆曲线和模型式.
我来水一下,说不定就是费尔玛当年的绝妙的想法：
假设X^n+Y^n=Z^n,其中XYZn为正整数,当n>2时,XYZ有正整数解,设n=2+m,而我们知道：
方程X^2+Y^2=Z^2是有解的：x=a^2-b^2,y=2ab,z=a^2+b^2,那么
x^(2+m)+y^(2+m)=z^(2+m)意味着：x^2(x^m-1)+y^2(y^m-1)=z^2(z^m-1)
这样,x^m-1=1,y^m-1=1,z^m-1=1,x=2^(1/m),y=2^(1/m),z=2^(1/m)
所以：x=y=z,x^n+y^n=2x^n=z^n=x^n,得出：2=1,矛盾,因此原方程没有正整数解.