HDU 6441 -- Find Integer（2018ccpc網絡選拔賽）費馬大定理+勾股數構造

題意：給定n和a，找b和c滿足a ^n + b ^n =c ^n的整數解，若不存在輸出-1，-1。

每當看到資料各得這麼大就感覺有什麼定理之類的很短的做法…

費馬大定理：對于方程a ^n + b ^n =c ^n，當n大于2時沒有整數解。

n==0時對于所給資料範圍顯然無解，故僅需去判斷n = = 1 和 n = = 2時的情況

即可。

對于n = =1的情況有很多種，例如取b=1，則c=a+1輸出即可。

對于n = = 2時就要構造勾股數了，使用“奇偶數列法則”構造，

即：對于a為2n+1的奇數時，有：

b = n ^2 +（n+1） ^2-1 ，

c = n ^ 2+（n+1） ^ 2 .

展開也記為：b =2n^2 + 2n, c =2n ^ 2+2n+1

對于a為2*n的偶數時，有：

b = n^2-1, c= n ^ 2+1.

證明：代入a^2 +b ^2 =c ^2推出等式兩邊相等即可。

代碼如下：

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
int main()
{
    int i,j;
    int t;
    ll n,a,b,c;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&a);
        if(n==0||n>2)//費馬大定理
        {
            printf("-1 -1\n");
        }
        else
        {
            if(n==1)
            {
                printf("1 %lld\n",a+1);//設b為1,則c為a+1;
            }
            else
            {
                if(a%2!=0)//奇數時
                {
                    ll x=(a-1)/2;
                    b=2*x*x+2*x;
                    c=2*x*x+2*x+1;
                }
                else//偶數時
                {
                    ll x=a/2;
                    b=x*x-1;
                    c=x*x+1;
                }
                printf("%lld %lld\n",b,c);
            }
        }
    }
    return 0;
}