HDU-6441-Find Integer-费马大定理+奇偶数列法则

感觉这样看的比较清楚。

题意：

给出n和a，判断能否求出a^n+b^n=c^n中b和c的值，若可以输出b和c，否则则输出-1 -1。

思路：

数据给的比较大，但是题目很简单，套两个公式：费马打定理和奇偶数列法则分类讨论即可。

以下是对这两个法则的介绍：

费马大定理：

当整数n >2时，关于x, y, z的方程 x^n + y^n = z^n 没有正整数解。

相关题目：UVALive - 6862 Triples

 #include<stdio.h>

 int main()

 {

     int m,n;

     while(~scanf("%d %d",&m,&n))

     {

         int sum=;

         for(int x=; x<=m; x++) //当j==2时 题目给出条件x=<y=<z

         {

             for(int y=x; y<=m; y++)

             {

                 for(int z=y; z<=m; z++)

                 {

                     if(x*x+y*y==z*z)

                         sum++;

                 }

             }

         }

         sum=sum+(n-)*(m+);//当2<j<=n时，有n-2种情况。

         //即x=0时，y=z，0=<y<=m，有m+1种情况

         printf("%d\n",sum);

     }

     return ;

 }

奇偶数列法则：

定理: 是直角三角形的三个整数边长，则必有如下a值的奇数列、偶数列关系成立；

奇数列法则：
若a表为2n+1型奇数（n=1、2、3……），则a为奇数列平方整数解的关系是：
a=2n+1

偶数列法则：
若a表为2n型偶数（n=2、3、4……），则a为偶数列平方整数解的关系是：
a= 2n

推荐一个好用的可以在markdown插入数学公式的网站，今天也是第一次用。

http://latex.codecogs.com/eqneditor/editor.php

 #include<stdio.h>

 typedef long long ll;

 int main()

 {

     int t;

     ll n,a;

     scanf("%d",&t);

     while(t--)

     {

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

         if(n>||n==)//n>2可以根据费马大定理可得，n==0等式是无法成立的，但题目给出了需要判断不然WA

             printf("-1 -1\n");

         else if(n==)//想到勾股定理，根据奇偶数列法则可得

         {

             //分a是奇数还是偶数讨论

             if(a%==)

             {

                 ll x=(a-)/;

                 ll b=x*x+(x+)*(x+)-;

                 ll c=x*x+(x+)*(x+);

                 printf("%lld %lld\n",b,c);

             }

             else if(a%==)

             {

                 ll x=a/;

                 ll b=x*x-;

                 ll c=x*x+;

                 printf("%lld %lld\n",b,c);

             }

         }

         else if(n==)//因为可以随便输出一个解，所以假设b=1,a+1=c

             printf("1 %lld\n",a+);

     }

     return ;

 }

巴特西

HDU-6441-Find Integer-费马大定理+奇偶数列法则

最新文章

热门文章