中国建设人才服务信息网站,哈尔滨 建网站,企业注册视频号,整合网络营销策划P9853 [入门赛 #17] 方程求解 - 洛谷
题目描述
小A有n个关于x的方程#xff0c;第i个方程形如aixibici。方程的解x均为正整数#xff0c;例如下面几个方程都是符合要求的方程#xff1a;
2x 4 10
-3x 13 10
4x - 8 16
其中#xff0c;第一组方程的解为x1…P9853 [入门赛 #17] 方程求解 - 洛谷
题目描述
小A有n个关于x的方程第i个方程形如aixibici。方程的解x均为正整数例如下面几个方程都是符合要求的方程
2x 4 10
-3x 13 10
4x - 8 16
其中第一组方程的解为x13第二组方程的解为x21第三组方程的解为x36。
小A想要知道给定L, R在L≤x≤R的范围内有多少个正整数x满足x是其中至少一个方程的解。为了防止你欺骗他他会询问你Q次。
输入格式
第一行输入两个正整数n, Q分别表示小A有的方程数以及小A想要向你询问的次数。
第二行开始往下n行每行一个字符串描述一个方程。
第(n2)行开始往下Q行每行两个正整数L, R表示一次询问即给定L, R询问在L≤x≤R的范围内有多少个正整数x满足x是其中至少一个方程的解。
输出格式
对于每次询问输出一行一个整数表示有多少个在L≤x≤R的范围内的正整数x满足x是其中至少一个方程的解。
输入输出样例
输入#1
3 4
2x 4 10
-3x 13 10
4x - 8 16
1 6
1 8
3 6
4 5
输出#1
3
2
0
1
输入#2
5 3
5x - 2 13
8x 5 45
4x - 12 8
-2x 10 4
3x - 7 2
1 3
1 5
3 5
输出#2
1
2
2
说明/提示
[样例解释]
对于第一组样例即为题目中的举例。三组方程的解分别为 x13,x21,x36。则
对于 1≤x≤6 的范围有3个 x 的取值x1,3,6是其中至少一个方程的解对于 1≤x≤8 的范围同上所述对于 3≤x≤6 的范围有2个 x 的取值x3,6是其中至少一个方程的解对于 4≤x≤5 的范围不存在一个 x 是其中至少一个方程的解因此分别输出 3, 3, 2, 0。
对于第二组样例五组方程的解分别为 x13,x25,x35,x43,x53。则
对于 1≤x≤3 的范围只有 x3 满足是其中至少一个方程的解对于 1≤x≤5 的范围有2个 x 的取值x3,5是其中至少一个方程的解对于 3≤x≤5 的范围有2个 x 的取值x3,5是其中至少一个方程的解因此分别输出 1, 2, 2。
[数据范围]
数据保证1≤n,Q≤2×105方程中 ai,bi,ci 满足 1≤∣ai∣,∣bi∣,∣ci∣≤109每一组方程的解 xi 必定为正整数。询问时的 L,R 满足 1≤L≤R≤2×109。
本题输入数据较大请注意代码输入输出的运行效率。
思路
暴力
代码如下
#includeiostream
#includealgorithm
#includemap
using namespace std;
typedef long long ll;
ll n,q;
const ll N 2e510;
map ll,ll p;
int main(void)
{cin n q; ll a,b,c;for(ll i 1 ; i n ; i){scanf(%lldx%lld%lld,a,b,c);ll x (c-b)/a;p[x]; }while(q--){ll ans 0;ll l,r;cin l r;for(ll i l ; i r ; i){if(p[i] 0){ans;}}cout ans endl;}return 0;
}
