hdu 5615 Jam's math problem(十字相乘判定)

d.

Jam有道数学题想向你请教一下,他刚刚学会因式分解比如说,x^2+6x+5=(x+1)(x+5)
就好像形如 ax^2+bx+c => pqx^2+(qk+mp)x+km=(px+k)(qx+m)
但是他很蠢,他只会做p,q,m,kp,q,m,k为正整数的题目
请你帮助他,问可不可以分解

题意就是问一个一元二次方程能不能进行十字相乘的分解?

s.

官方题解:第一道题比较简单,可以说是简单的模拟题,我们考虑到a,b,c都是10^9​​的,所以我们决定要把时间复杂度降下来,

对于每一个数,因为考虑到都是正数,所以我们处理起来就方便很多,打个比方32=2*16,那么枚举到2的时候就可以得出16,

这样子的话时间就变为O(√​a​​​√​b​​​),轻松解决这道题

就是枚举么,我也是这么想的。。。

当时感觉可能超时,还想到了合数分解。。。。最后也没做出来。。。真是想多了。。。

ps:如果知道下面这个的话,那么这个题就容易多了。。。

对于形如ax²+bx+c的多项式,在判定它能否使用十字分解法分解因式时,可以使用Δ=b²-4ac进行判定。当Δ为完全平方数时,可以在整数范围对该多项式进行十字相乘。

c.枚举

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std; int a,b,c;
int p[],cnt1;//p
int k[],cnt2;//k bool f(){
cnt1=cnt2=; int sqrt1=(int)sqrt(a);
for(int i=;i<=sqrt1;++i){
if(a%i==){
p[cnt1++]=i;
p[cnt1++]=a/i;
}
}
int sqrt2=(int)sqrt(c);
for(int i=;i<=sqrt2;++i){
if(c%i==){
k[cnt2++]=i;
k[cnt2++]=c/i;
}
} int q,m;
for(int i=;i<cnt1;++i){
for(int j=;j<cnt2;++j){
q=a/p[i];
m=c/k[j];
if( q*k[j]+m*p[i]==b ){
return true;
}
}
}
return false;
} int main(){ int T; scanf("%d",&T); while(T--){
scanf("%d%d%d",&a,&b,&c); if(f()){
printf("YES\n");
}
else{
printf("NO\n");
}
} return ;
}

c2.当Δ为完全平方数时,可以在整数范围对该多项式进行十字相乘。

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std; int main(){ int T;
__int64 a,b,c;
__int64 k,m; scanf("%d",&T); while(T--){
scanf("%I64d%I64d%I64d",&a,&b,&c);
m=b*b-*a*c; if(m<){//m不是完全平方数
printf("NO\n");
}
else{//m>=0
k=(__int64)sqrt(m);
if(k*k==m){//m是完全平方数
printf("YES\n");
}
else{//m不是完全平方数
printf("NO\n");
}
}
} return ;
}
上一篇:xamarin UWP ActivityIndicator


下一篇:洛谷⑨月月赛Round2 P3393逃离僵尸岛[最短路]