hud 6441+费马大定理+奇偶数列法

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6441

题目大意:多样例测试,输入n, a;求 a^n+b^n=c^n 的b, c的值

思考:
根据费马大定理n>2该方程无解
n=0也无解, n=1输出两个随便满足的值就行了(a+b=c)。
n=2用奇偶数列法,证明链接:https://blog.csdn.net/Dilly__dally/article/details/82081922

        //a为奇数
        //a=2n+1; b=n^2+(n+1)^2-1; c=n^2+(n+1)^2
        if(a%2==1)
        {
            int n=(a-1)/2;
            b=n*n+(n+1)*(n+1)-1;
            c=n*n+(n+1)*(n+1);
            printf("%lld %lld\n",b, c);
        }

        //a为偶数
        //a=2n; b=n^2-1; c=n^2+1 
        else
        {
            int n=a/2;
            b=n*n-1;
            c=n*n+1;
            printf("%lld %lld\n",b, c);
        }

队友提高一种新方法:找规律

//a为奇数
//b=int(a^a/2); c=b+1

//a为偶数
//while(a/2); 直到a==奇数||a=4

奇偶数列法+AC代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long

//费马大定理a^n+b^n=c^n, n>2||n==0无解 

//n=2 
//a^2+b^2=c^2
//输入a, 求b, c;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        LL a, b, c, m;

        scanf("%lld%lld",&m,&a);

        if(m>2||m==0)
        {
            printf("-1 -1\n");
        }
        else if(m==1)
        {
            printf("%lld %lld\n",a, a*2);
        }
        //a为奇数
        //a=2n+1; b=n^2+(n+1)^2-1; c=n^2+(n+1)^2
        else if(a%2==1)
        {
            int n=(a-1)/2;
            b=n*n+(n+1)*(n+1)-1;
            c=n*n+(n+1)*(n+1);
            printf("%lld %lld\n",b, c);
        }
        //a为偶数
        //a=2n; b=n^2-1; c=n^2+1 
        else
        {
            int n=a/2;
            b=n*n-1;
            c=n*n+1;
            printf("%lld %lld\n",b, c);
        }
    }

    return 0;
}

规律+AC代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long

//费马大定理a^n+b^n=c^n, n>2||n==0无解

//n=2
//a^2+b^2=c^2
//输入a, 求b, c;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        LL a, b, c, m;

        scanf("%lld%lld",&m,&a);

        if(m>2||m==0)
        {
            printf("-1 -1\n");
        }
        else if(m==1)
        {
            printf("%lld %lld\n",a, a*2);
        }
        //a为奇数
        //b=int(a^a/2); b+1
        else if(a%2==1)
        {
            b=(a*a/2);
            c=b+1;
            printf("%lld %lld\n",b, c);
        }
        //a为偶数
        //while(a/2); 直到a==奇数||a=4

        else
        {
            if(a==0)
            {
                printf("0 0\n");
                continue;
            }
            else if(a==2)
            {
                printf("0 2\n");
                continue;
            }

            LL n=1;
            while(1)
            {
                a/=2;
                n*=2;

                if(a==4||a%2==1)
                break;
            }
            if(a==4)
            {
                b=3*n;
                c=5*n;
                printf("%lld %lld\n",b, c);
            }
            else
            {
                b=(a*a/2);
                c=(b+1);
                printf("%lld %lld\n",b*n, c*n);
            }
        }
    }

    return 0;
}
全部评论

相关推荐

12-09 16:31
已编辑
门头沟学院 前端工程师
Apries:这个阶段来说,很厉害很厉害了,不过写的简历确实不是很行,优势删掉吧,其他的还行
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务