2018中国大学生程序设计竞赛 – 网络选拔赛 1004 Find Integer [费马大定理]

                                          1004 Find Integer

 题目：给定,求满足等式的正整数b，c如果不存在则输出-1 -1。

题解：根据费马大定理，n>2是没有整数解，n = 0是也没有正整数解，故n=1,2是枚举一下就可以了。

代码：

#include<bits/stdc++.h>
#define ll long long

using namespace std;
const int maxn = 1e9+7;

ll a, n;

int main()
{
    //freopen("in.txt", "r", stdin);
    int t; scanf("%d", &t);

    while(t--) {
        scanf("%lld%lld", &n, &a);
        if(n>2||n==0) {
            printf("-1 -1\n");
            continue;
        } else if(n==1) {
            printf("1 %lld\n", a + 1);
            continue;
        } else if(n == 2){
            ll x = a - 1, y, s = a*a, b, c;
            bool f = false;
            while(x>0) {
                if(s%x == 0) {
                    y = s/x;
                    if((x+y)%2 == 0&&abs(x-y)%2 == 0) {
                        c = (x+y)/2;
                        b = abs(x-y)/2;
                        f = true;
                        break;
                    }
                }
                x--;
            }
            if(f) printf("%lld %lld\n", b, c);
            else printf("-1 -1\n");
        }
    }
    return 0;
}