CF1342C Yet Another Counting Problem

#include<iostream>
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
ll n, m, q, l, r;
long long cnt (ll x, ll lcm) {
	ll  a = x % lcm, b = x / lcm;
	ll ans = b * max(n, m);
	if(a >= max(n, m) - 1){
		ans += max(n, m) - 1;
	}
	else ans += a ;
	return x - ans ;
}
int main() {
	int t;
	cin >> t;
	while (t--) {
		cin >> n >> m >> q;
		while (q --) {
			cin >> l >> r;
			long long lcm = n / __gcd(n, m) * m;
			printf("%lld ",cnt(r, lcm) - cnt(l - 1, lcm));
		}
		printf("\n");
	}
}
根据猜测可发现,在1到n ,m中较大的数减一这些数是不满足条件的,而且在n和m的最小公倍数到最小公倍数加max(n,m)-1这个区间以及这个区间的倍数也是不满足的
全部评论

相关推荐

09-01 11:31
门头沟学院 Java
buul:七牛云的吧,感觉想法是好的,但是大家没那么多时间弄他这个啊。。。不知道的还以为他是顶尖大厂呢还搞比赛抢hc,只能说应试者的痛苦考察方是无法理解的,他们只会想一出是一出
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务