牛客周赛 Round 50 D小红的因式分解 超级无敌大暴力
首先拿到这个题,真的是一头雾水,本蒟蒻今天才想出来。。。
首先拆开式子,我们可以得到a1a2 == a; a1b2+a2b1 == b;b1b2 == c;
那么,我们只需要求解一对a1与b1即可得到本题答案,因为剩下的一对a2 b2由a/a1和b/b1得到
所以我们可以运用暴力,检索a%a1 == 0的值并且在此时再去检索c%b1 == 0如若满足则输出,无满足就输出NO即可。那么我们真的要运行最差情况下高达2 x 10^6 x 2 x 10^6次数的这一坨吗?
当然不!!!比如1000,对1000除以10得到的是1000,对1000除以100得到的是10,由基本数学知识可知,a1a2的位置是没有要求的,b1b2同理,所以我们只需要对他开根,检索其中一部分就好了,也就是对a1 b1暴力只检索 -10^3 到 +10^3 即可
并且注意 0 不能做除数
代码如下
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
int main() {
long long int T;
cin >> T;
while (T--) {
int vis = -1;
long long int a, b, c;
cin >> a >> b >> c;
for (long long i = -1000; i <= 1000; i++) {
if (i == 0)
continue;
if(a%i == 0)
for (long long j = -1000; j <= 1000; j++) {
if (j == 0)
continue;
if (c % j == 0 && a * j / i + c * i / j == b) {
vis = 1;
cout << i << " " << j << ' ' << a / i << ' ' << c / j << endl;
break;
}
}
if (vis == 1)
break;
}
if (vis != 1)
cout << "NO" << endl;
}
}
标签:周赛,因式分解,10,50,long,a1,b1,include,1000
From: https://www.cnblogs.com/lgdxxs12138/p/18289943