HDU6441Find 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

 1 #include<stdio.h>
 2 int main()
 3 {
 4     int m,n;
 5     while(~scanf("%d %d",&m,&n))
 6     {
 7         int sum=0;
 8         for(int x=0; x<=m; x++) //当j==2时 题目给出条件x=<y=<z
 9         {
10             for(int y=x; y<=m; y++)
11             {
12                 for(int z=y; z<=m; z++)
13                 {
14                     if(x*x+y*y==z*z)
15                         sum++;
16                 }
17             }
18         }
19         sum=sum+(n-2)*(m+1);//当2<j<=n时，有n-2种情况。
20         //即x=0时，y=z，0=<y<=m，有m+1种情况
21         printf("%d\n",sum);
22     }
23     return 0;
24 }

View Code

奇偶数列法则：

定理: 是直角三角形的三个整数边长，则必有如下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

 1 #include<stdio.h>
 2 typedef long long ll;
 3 
 4 int main()
 5 {
 6     int t;
 7     ll n,a;
 8     scanf("%d",&t);
 9     while(t--)
10     {
11         scanf("%lld %lld",&n,&a);
12         if(n>2||n==0)//n>2可以根据费马大定理可得，n==0等式是无法成立的，但题目给出了需要判断不然WA
13             printf("-1 -1\n");
14         else if(n==2)//想到勾股定理，根据奇偶数列法则可得
15         {
16             //分a是奇数还是偶数讨论
17             if(a%2==1)
18             {
19                 ll x=(a-1)/2;
20                 ll b=x*x+(x+1)*(x+1)-1;
21                 ll c=x*x+(x+1)*(x+1);
22                 printf("%lld %lld\n",b,c);
23             }
24             else if(a%2==0)
25             {
26                 ll x=a/2;
27                 ll b=x*x-1;
28                 ll c=x*x+1;
29                 printf("%lld %lld\n",b,c);
30             }
31         }
32         else if(n==1)//因为可以随便输出一个解，所以假设b=1,a+1=c
33             printf("1 %lld\n",a+1);
34     }
35     return 0;
36 }

View Code