P9853 [入门赛 #17] 方程求解

P9853 [入门赛 #17] 方程求解 - 洛谷

题目描述

小A有n个关于x的方程，第i个方程形如ai​xi​+bi​=ci​。方程的解x均为正整数，例如下面几个方程都是符合要求的方程：

2x + 4 = 10
-3x + 13 = 10
4x - 8 = 16

其中，第一组方程的解为x1​=3，第二组方程的解为x2​=1，第三组方程的解为x3​=6。

小A想要知道，给定L, R，在L≤x≤R的范围内，有多少个正整数x满足x是其中至少一个方程的解。为了防止你欺骗他，他会询问你Q次。

输入格式

第一行输入两个正整数n, Q，分别表示小A有的方程数，以及小A想要向你询问的次数。

第二行开始，往下n行，每行一个字符串，描述一个方程。

第(n+2)行开始，往下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

说明/提示

[样例解释]

对于第一组样例，即为题目中的举例。三组方程的解分别为 x1​=3,x2​=1,x3​=6。则：

• 对于 1≤x≤6 的范围，有3个 x 的取值（x=1,3,6）是其中至少一个方程的解；
• 对于 1≤x≤8 的范围，同上所述；
• 对于 3≤x≤6 的范围，有2个 x 的取值（x=3,6）是其中至少一个方程的解；
• 对于 4≤x≤5 的范围，不存在一个 x 是其中至少一个方程的解；
• 因此分别输出 3, 3, 2, 0。

对于第二组样例，五组方程的解分别为 x1​=3,x2​=5,x3​=5,x4​=3,x5​=3。则：

• 对于 1≤x≤3 的范围，只有 x=3 满足是其中至少一个方程的解；
• 对于 1≤x≤5 的范围，有2个 x 的取值（x=3,5）是其中至少一个方程的解；
• 对于 3≤x≤5 的范围，有2个 x 的取值（x=3,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。

本题输入数据较大，请注意代码输入输出的运行效率。

思路：

暴力

代码如下：

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
ll n,q;
const ll N = 2e5+10;
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;
}