喵哈哈的矩阵
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.uestc.edu.cn/#/problem/show/1250
Description
人尽皆知，在喵哈哈村，有一个法力无边的廖神
他随手一挥，便移走山岳；他随手一指，便填平沟壑；他抬头一望，便斗转星移。
突然，他嘟嘟嘟的在念着咒语，只听噼啪一声，在喵哈哈村的中心广场就出现一个巨大的矩阵
村子里的人纷纷称奇。
好奇的沈宝宝走上前去，看了看这个矩阵。
这个矩阵是n行m列的矩阵。
矩阵很大，大到无法无天。
矩阵很小，小到只有n*3个元素。
因为，沈宝宝发现了其中的端倪。
假设T[i][j]表示原矩阵第i行j列的元素大小，那么 T[i][j] = A[i] x j x j + B[i] x j + C[i]
被人称奇的廖神，笑：“沈宝宝，就算让你看穿这个矩阵又如何？那你能否看出这个矩阵中究竟有多少个K呢？”
沈宝宝想了想，便轻松解决了这个问题。
廖神不断地更改K的值，不停的问着
沈宝宝不停的回答着
真是神奇。
“啪！坐在窗子边上的陈同学，不要睡觉了！刚才文中提到的沈宝宝，他的每次回答的答案是什么？答不上来，就叫你的家长下午来见我！”，何老师怒道。
陈同学一点都不方，尽管他只记得矩阵的端倪和廖神每次提问的K。就在他站起来的那几秒，他已经口算出答案了。
而你，你知道吗？
Input
第1行 n,m 表示矩阵n行m列
第2到n+1行 a[i],b[i],c[i]，表示沈宝宝所看出的端倪
第n+2行 Q，表示被人称奇的廖神向沈宝宝提问的次数
第n+3到n+Q+2行，K，表示每次廖神提问的K是什么
我们保证：1<=n<=50000 ,1<=m<=10^9,-10^9<=Ai,Bi,Ci<=10^9,0<=Q<=1000,k<=10^18
都是整数~
矩阵都是从1开始的哦~
Output
Q行答案
每一行一个整数，表示K出现的次数
Sample Input
3 3
1 2 3
3 4 5
2 3 4
3
18
7
6
Sample Output
2
0
1
HINT
题意
题解：
这道题的做法主要分为以下两种：
我们直接把矩阵暴力出来，然后对于每一个询问O(1)去回答，这样的时间复杂度是O(nm)，空间复杂度是O(1e9)，很显然不能接受。
对于每次询问，我们直接暴力算出每一行存在多少个K就好了，然后把每一行的ans加起来就是答案。由于每一行都是二次函数，那么我们讨论存在多少个K就比较轻松了，既可以二分得到，也可以利用二次函数的求根公式来解决。时间复杂度分别是O(qnlogm),O(qn)，而空间复杂度O(1)。
在题目所规定的的数据范围内，是可以通过的。
下面，我们就主要讲讲如何通过二次函数的求根公式来解决这个题目~
对于每一行，我们首先变形一下，使得c[i] = c[i] - k；
这样，方程就变为 a[i]*x*x+b[i]*x+c[i] = 0，我们只要讨论在[1,m]中存在多少个整数解，即是这一行的答案。
首先讨论a[i] = 0,b[i] = 0的情况，这样变成一个常数方程，很简单
然后讨论a[i] = 0,b[i] != 0，这样是一个一次函数，可以O(1)得到答案，然后再判断是否为整数，这个整数是否在[1,m]就好了。
接着就是二次函数了，首先判断Δ。然后按照Δ分类讨论就好。也比较简单。
注意，答案可以会超过int哦~
然后，这道题就结束了！
代码：
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int n,m;
#define maxn 100005
double eps = 1e-;
long long a[maxn],b[maxn],c[maxn];
long long gcd(long long a,long long b)
{
if(b==)return a;
return gcd(b,a%b);
}
long long ans;
void solve(long long x)
{
for(int i=;i<=n;i++)
{
if(a[i]==&&b[i]==)
{
if(c[i]==x)ans+=m;
}
else if(a[i]==)
{
long long BI = b[i];
long long KI = x-c[i];
if(gcd(BI,KI)==BI&&KI/BI<=m&&KI/BI>=)
ans+=;
}
else
{
long long A = a[i],B = b[i],C = c[i]-x;
long long p = B*B - 4LL*A*C;
if(p<)continue;
if(p==)
{
if(gcd(-B,2LL*A)==2LL*A&&-B/(2LL*A)<=m&&-B/(2LL*A)>=)
ans++;
}
if(p>)
{
double x1 = (-B + sqrt(B*B-*A*C))/(*A);
double x2 = (-B - sqrt(B*B-*A*C))/(*A);
long long X1 = x1;double XX1 = X1;
if(abs(XX1-x1)<=eps)
{
if(x1<=m&&x1>=)ans++;
}
long long X2 = x2;double XX2 = X2;
if(abs(XX2-x2)<=eps)
{
if(x2<=m&&x2>=)ans++;
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
int q;scanf("%d",&q);
while(q--)
{
long long k;scanf("%lld",&k);
ans = ;
solve(k);
printf("%lld\n",ans);
}
}