Решение задачи Очередная задача на подсчет с Codeforces

Без пояснения   Просмотров: 1134

Вам даны два числа a и b, а также q запросов. i-й запрос состоит из двух чисел li и ri, и ответ на него — количество таких целых чисел x, что li≤x≤ri и ((xmoda)modb)≠((xmodb)moda). Вычислите ответ на каждый запрос.

Напоминаем, что ymodz — остаток от деления y на z. Например, 5mod3=2, 7mod8=7, 9mod4=1, 9mod9=0.

Код 

#include <bits/stdc++.h>
using namespace std;
typedef  long long   ll;
typedef long double ld;

ll a, b, x;

ll pref(ll n) {
	ll cnt = (n / x) * (x - max(a, b));
	n %= x;
	if (n >= max(a, b))
		cnt += n - max(a, b) + 1;
	return cnt;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin >> t;
	while (t--) {
		ll q, l, r;
		cin >> a >> b >> q;
		x = lcm(a, b);
		while (q-- && cin >> l >> r) {
			cout << pref(r) - pref(l - 1) << ' ';
		}
		cout << '\n';
	}
	
		

}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp