2018中国大学生程序设计竞赛 - 网络选拔赛 D Find Integer (规律)

Find Integer

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 293    Accepted Submission(s): 78
Special Judge

Problem Description

people in USSS love math very much, and there is a famous math problem .

give you two integers n,a,you are required to find 2 integers b,c such that an+bn=cn.

Input

one line contains one integer T;(1≤T≤1000000)

next T lines contains two integers n,a;(0≤n≤1000,000,000,3≤a≤40000)

Output

print two integers b,c if b,c exits;(1≤b,c≤1000,000,000);

else print two integers -1 -1 instead.

Sample Input

1 2 3

Sample Output

4 5

签到的EASY题，题目浅显易懂。
听说是什么费马大定理什么的，队友直接找规律，发现n>2无解，然后n ==1跟n==2的情况就简单了，n==2的情况就是勾股定理的一个规律，n为奇数有勾股数(2*n+1，2*n*n+2*n，n*n+1)；n为偶数有勾股数(2*n，n*n-1，n*n+1)。

代码实现：

/*
Look at the star
Look at the shine for U
*/
#include<bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define sl(x) scanf("%lld",&x)
using namespace std;
const int N = 1e6+5;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
ll inv(ll b){if(b==1)return 1; return (mod-mod/b)*inv(mod%b)%mod;}
ll fpow(ll n,ll k){ll r=1;for(;k;k>>=1){if(k&1)r=r*n%mod;n=n*n%mod;}return r;}
struct node{
	ll num,index;
	node(ll a,ll b)
	{
		num = a;
		index = b;
	}
	friend bool operator < (node a,node b)
    {
       	if(a.num == b.num) return a.index < b.index;
       	return a.num > b.num;
	}
};
priority_queue <node> q;
int main()
{
	ll t,p,i,j,k,n,x,a;
	sl(t);
	while(t--)
	{
		sl(n);sl(a);
        if(n > 2 || n == 0) puts("-1 -1");
        else if(n == 2)
        {
            if(a&1)
            {
                x = (a-1)>>1;
                printf("%lld %lld\n",2*x*x+2*x,2*x*x+2*x+1);
            }
            else
            {
                x = a>>1;
                printf("%lld %lld\n",x*x-1,x*x+1);
            }
        }
        else if(n == 1)
        {
            printf("1 %lld\n",a+1);
        }
	}
}