BestCoder Round #70 Jam's math problem(hdu 5615)

Problem Description

Jam has a math problem. He just learned factorization. He is trying to factorize ax^2+bx+cax​2​​+bx+c into the form of pqx^2+(qk+mp)x+km=(px+k)(qx+m)pqx​2​​+(qk+mp)x+km=(px+k)(qx+m). He could only solve the problem in which p,q,m,k are positive numbers. Please help him determine whether the expression could be factorized with p,q,m,k being postive.

Input

The first line is a number TT, means there are T(1 \leq T \leq 100 )T(1≤T≤100) cases

Each case has one line,the line has 33 numbers a,b,c (1 \leq a,b,c \leq 100000000)a,b,c(1≤a,b,c≤100000000)

Output

You should output the "YES" or "NO".

Sample Input
2
1 6 5
1 6 4
Sample Output
Copy
YES
NO
Hint

The first case turn x^2+6*x+5x​2​​+6∗x+5 into (x+1)(x+5)(x+1)(x+5)

 
题意:给你一个一元二次方程的三个系数a ,b,c问你是否能用十字相乘的方法分解这个式子
题解:直接暴力枚举,当然要优化下枚举的方法,不然会超时滴,优化:因为最大数据是一亿,一亿可以分解为一万乘一万,因为这样我们分解的两个数一定不可能超过一万,我们通过遍历让c除以1  2  3.....n来枚举c的因子,当超过10000时,新出现的因子我们已经枚举过了先将c的所有因子存在数组中,然后在计算出a的所有因子,一个一个试即可
#include<stdio.h>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#define LL long long
#define PI atan(1.0)*4
#define DD doublea
#define MAX 10100
#define mod 10007
using namespace std;
int ans[MAX];
int main()
{
int n,m,j,i,t,k;
int a,b,c,Min1,Min2;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&a,&b,&c);
Min1=min(a,10000);
Min2=min(c,10000);
k=1;n=m=1;
for(i=1;i<=Min2;i++)
{
n=c/i;
if(n*i==c)
ans[k++]=i;
}
int flag=0;
for(i=1;i<=Min1;i++)
{
m=a/i;
if(i*m==a)
{
for(j=1;j<k;j++)
{
if((i*ans[j]+m*(c/ans[j])==b)||(m*ans[j]+i*(c/ans[j])==b))
{
flag=1;
break;
}
}
}
if(flag)
break;
}
if(flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}

  

上一篇:mui-手动触发下拉刷新


下一篇:(one) 条件判断的总结