답안 #409334

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409334	2021-05-20T15:19:01 Z	inbarin	이상한 기계 (APIO19_strange_device)	C++14	100 / 100	780 ms	49260 KB

strange_device

#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <deque>
#include <string>
#include <stack>
#include <algorithm>
#include <utility>
#include <math.h>
#include <ctime>

using namespace std;
typedef long long int63;
typedef unsigned long long int64;
#define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
#define forlb(name,start,end,jump) for(int63 name = end - 1; name >= start; name+=jump)
#define forn(name,start,end) forl(name,start,end,1)
#define fornb(name,start,end) forlb(name,start,end,-1)
#define fort(start,end) forn(i,start,end)
#define fortb(start,end) fornb(i,start,end)
#define forto(start,end) forn(j,start,end)
#define fortob(start,end) fornb(j,start,end)
#define fortoo(start,end) forn(l,start,end)
#define all(vec) vec.begin(),vec.end()
#define rall(vec) vec.rbegin(),vec.rend()
#define makeitem(itemname,itemtype) itemtype itemname; cin >> itemname
#define makeint(intname) int63 intname; cin >> intname
#define makeN int63 n; cin >> n
#define makeM int63 m; cin >> m
#define makeL int63 l; cin >> l
#define makeT int63 t; cin >> t
#define makeK int63 k; cin >> k
#define point pair<int63,int63>
#define dpoint pair<double,double>
#define ldpoint pair<long double,long double>
#define spoint pair<short,short>
#define ipoint pair<int,int>
#define matrix(type) vector<vector<type>>
#define in(name) cin >> name;
#define tosort(name) name.begin(),name.end()
int63 powmod(int63 base, int63 exponent, int63 mod) {
	int63 result = 1;
	while (exponent > 0) {
		if (exponent % 2 == 0) {
			exponent /= 2;
			base = (base * base) % mod;
		}
		else {
			result = (result * base) % mod;
			exponent /= 2;
			base = (base * base) % mod;
		}
	}
	return result;
}
bool decresing(int63 x, int63 y) {
	return x > y;
}
int63 modInverse(int63 a, int63 b) {//finds inverse of a mod b ...?
	int63 m = b;
	int63 y = 0, x = 1;
	while (a > 1) {
		int63 q = a / m;
		int63 t = m;
		m = a % m, a = t;
		t = y;
		y = x - q * y;
		x = t;
	}
	if (x < 0) {
		x += b;
	}
	return x;
}
int63 trin(int63 start, int63 stop) {
	return (stop - start + 1) * (stop + start) / 2;
}
int63 trin2(int63 start, int63 stop, int63 mod) {
	return (((((stop - start + 1) % mod) * ((stop + start) % mod)) % mod)*modInverse(2, mod) % mod) % mod;
}
int63 trig(int63 start, int63 stop, int63 jump, int63 mod) {
	return ((trin2((start + jump - 1) / jump, stop / jump, mod)) * (jump%mod)) % mod;
}
int63 cntot(int63 start, int63 stop, int63 jump, int63 mod) {
	return (stop / jump - (start + jump - 1) / jump + 1) % mod;
}
bool sortvectorf(point a, point b) {
	return((a.first > b.first) || (a.first == b.first && a.second > b.second));
}
bool sortvectordiv(point a, point b) {
	return a.first * b.second > b.first * a.second;
}
bool sortvectorfv(point a, point b) {
	return((a.first > b.first) || (a.first == b.first && a.second < b.second));
}
bool sortvectors(point a, point b) {
	return((a.second > b.second) || (a.second == b.second && a.first > b.first));
}
bool negasortvectorf(point a, point b) {
	return((a.first < b.first) || (a.first == b.first && a.second < b.second));
}
bool negasortvectors(point a, point b) {
	return((a.second < b.second) || (a.second == b.second && a.first < b.first));
}
vector<vector<int63>> findPermutationsI(vector<int63> &a) {
	// Sort the given array
	sort(a.begin(), a.end());
	vector<vector<int63> > sol;
	// Find all possible permutations
	do {
		sol.push_back(a);
	} while (next_permutation(a.begin(), a.end()));
	return sol;
}
vector<vector<string>> findPermutationsS(vector<string> &a) {
	// Sort the given array
	sort(a.begin(), a.end());
	vector<vector<string> > sol;
	// Find all possible permutations
	do {
		sol.push_back(a);
	} while (next_permutation(a.begin(), a.end()));
	return sol;
}
int63 gcd(int63 a, int63 b) {
	if (a == 0) {
		return b;
	}
	if (b == 0) {
		return a;
	}
	return gcd(b % a, a);
}
bool isprime(int63 n) {
	fort(2, n) {
		if (i * i > n) {
			break;
		}
		if ((n / i) * i == n) {
			return false;
		}
	}
	return true;
}
int63 fdivisor(int63 n, int63 fro) {
	fort(1, n + 1) {
		if ((n / i) * i == n && i >= fro) {
			return i;
		}
	}
	return -1;
}
vector<int63> divlist(int63 n) {
	vector<int63> curr;
	fort(1, n + 1) {
		if ((int63)i * i > n) {
			break;
		}
		if ((n / i) * i == n) {
			curr.push_back(i);
			curr.push_back(n / i);
		}
		if ((int63)i * i == n) {
			curr.pop_back();
		}
	}

	sort(all(curr));
	return curr;
}
vector<int63> pdivlist(int63 n) {
	vector<int63> curr;
	fort(2, n + 1) {
		if (i * i > n) {
			break;
		}
		if ((n % i) == 0) {
			if (isprime(i)) { curr.push_back(i); }
			int63 ni = n / i;
			if (isprime(ni)) { curr.push_back(ni); }
			if (i * i == n && isprime(i)) {
				curr.pop_back();
			}
			if (isprime(i)) {
				while ((n % i) == 0) {
					n /= i;
				}
			}
			if (isprime(ni)) {
				while ((n % ni) == 0) {
					n /= ni;
				}
			}
		}
		if (i % 2) {
			i++;
		}
	}
	if (n > 1 && (curr.size() == 0 || curr[curr.size()-1] != n) && isprime(n)) {
		curr.push_back(n);
	}
	sort(all(curr));
	return curr;
}
int63 countdivisors(int63 n, int63 divd, int63 rem) {
	vector<int63> divs = divlist(n);
	int63 tot = 0;
	fort(0, (int63)divs.size()) {
		if (divs[i] % divd == rem) {
			tot++;
		}
	}
	if (n % divd == rem) {
		tot++;
	}
	return tot;
}
int63 digsum(int63 num) {
	int63 cr = 0;
	while (num > 0) {
		cr += num % 10;
		num /= 10;
	}
	return cr;
}
vector<int63>atzeret;
int63 azeret(int63 num, int63 mod) {
	if (mod == 1000000007) {
		if ((int63)atzeret.size() > num) {
			return atzeret[num];
		}
		if (num == 0) {
			atzeret.push_back(1);
			return atzeret[num];
		}
		azeret(num - 1, mod);
		atzeret.push_back((atzeret[num-1] * num) % mod);
		return atzeret[num];
	}
	int63 sil = 1;
	while (num > 1) {
		sil *= num;
		sil %= mod;
		num--;
	}
	return sil;
}
int63 moddiv(int63 to, int63 by, int63 mod) {
	to %= mod;
	by %= mod;
	to *= modInverse(by, mod);
	return to % mod;
}
int63 choose(int63 num, int63 choice, int63 mod) {
	if (choice < 0 || choice > num) {
		return 0;
	}
	return moddiv(azeret(num, mod), (azeret(choice, mod)*azeret(num - choice, mod)) % mod, mod);
}
class node {
public:
	int data1;
	int data2;
	node* nxt;
	node* bef;
	node(int dat1, int dat2, node*bif) {
		this->nxt = NULL;
		this->bef = bif;
		this->bef->nxt = this;
		this->data1 = dat1;
		this->data2 = dat2;
	}
	node(int dat1, int dat2) {
		this->nxt = NULL;
		this->bef = NULL;
		this->data1 = dat1;
		this->data2 = dat2;
	}
	node() {
		this->nxt = NULL;
		this->bef = NULL;
		this->data1 = 0;
		this->data2 = 0;
	}
	void remove() {
		this->bef->nxt = this->nxt;
		if (this->nxt != NULL) {
			this->nxt->bef = this->bef;
		}
	}
	void push(int dat1, int dat2) {
		node* next = this->nxt;
		node* curr = new node(dat1, dat2, this);
		curr->nxt = next;
		next->bef = curr;
	}
};
bool by_first(pair<point, point> a, pair<point, point> b) {
	return a.first.first < b.first.first;
}
bool ff_fs(pair<pair<int63, bool>, int63> a, pair<pair<int63, bool>, int63> b) {
	return a.first.first < b.first.first || (a.first.first == b.first.first && a.first.second && !b.first.second);
}
bool f_s_b(pair<int63, int63> a, pair<int63, int63> b) {
	return a.first > b.first || (a.first == b.first && a.second > b.second);
}
#define make(name) int63 name; cin >> name
#define remake(name) if(name == -1){cin >> name;}

bool palindrome(string s) {
	fort(0, (int63)s.size() / 2) {
		if (s[i] != s[s.size() - 1 - i]) {
			return 0;
		}
	}
	return 1;
}
struct union_find {
	vector<int63>rot;
	vector<vector<int63>> rat;
	void init(int63 n) {
		fort(0, n) {
			rot.push_back(i);
			rat.push_back({ i });
		}
	}
	bool unio(int63 f, int63 s) {
		if (rot[f] == rot[s]) {
			return false;
		}
		//rot[f] <-> rot[s]
		if (rat[rot[f]].size() > rat[rot[s]].size()) {
			//s to f
			int63 siz = rat[rot[s]].size();
			int63 rs = rot[s];
			fort(0, siz) {
				rat[rot[f]].push_back(rat[rs][i]);
				rot[rat[rs][i]] = rot[f];
			}
			return true;
		}
		int63 siz = rat[rot[f]].size();
		int63 rf = rot[f];
		fort(0, siz) {
			rat[rot[s]].push_back(rat[rf][i]);
			rot[rat[rf][i]] = rot[s];
		}
		return true;
	}
};
//
vector<int> subsum(vector<int> items, int limit) {
	vector<vector<int> > table(items.size() + 1, vector<int>(limit + 1));
	forto(1, (int63)items.size() + 1) {
		int wt = items[j - 1];
		int val = wt;
		for (int w = 1; w < limit + 1; w++) {
			if (wt > w) {
				table[j][w] = table[j - 1][w];
			}
			else {
				table[j][w] = max(table[j - 1][w], (int)(table[j - 1][w - wt] + val));
			}
		}
	}
	vector<int> result;
	int w = limit;
	for (int j = items.size(); j > 0; j--) {
		bool was_added = table[j][w] != table[j - 1][w];
		if (was_added) {
			int wt = items[j - 1];
			result.push_back(j - 1);
			w -= wt;
		}
	}
	sort(all(result));
	return result;
}
int63 detrig(int63 num) {
	int63 minus = 0;
	while (true) {
		if (num <= 0) {
			return minus;
		}
		minus++;
		num -= minus;
	}
}
int63 palpref(string &s) {
	int63 ha1 = 0, ha2 = 0, hr1 = 0, hr2 = 0;
	int63 m1 = 1, m2 = 1;
	int63 mix = 0;
	forto(0, s.size()) {
		ha1 = (ha1 + m1 * s[j]) % 1000000007;
		ha2 = (ha2 + m2 * s[j]) % 998244353;

		hr1 = (s[j] + 359 * hr1) % 1000000007;
		hr2 = (s[j] + 401 * hr2) % 998244353;

		m1 *= 359, m1 %= 1000000007;
		m2 *= 401, m2 %= 998244353;

		if (ha1 == hr1 && ha2 == hr2) {
			mix = j + 1;
		}
	}
	return mix;
}
double diffclock(clock_t clock1, clock_t clock2)
{
	double diffticks = clock1 - clock2;
	double diffms = (diffticks) / (CLOCKS_PER_SEC / 1000);
	return diffms;
}
struct fenwick {
	int63 n;
	vector<int63> data;
	vector<int63> real;
	void init(int63 n) {
		this->n = n;
		data.resize(n);
		real.resize(n);
	}
	void add(int63 pos, int63 val) {
		real[pos] += val;
		pos++;
		int63 cur = 0;
		while (pos << cur <= this->n) {
			if (pos % 2 == 1) {
				this->data[(pos << cur) - 1] += val;
			}
			cur++;
			pos = (pos + 1) / 2;
		}
	}
	void upd(int63 pos, int63 val) {
		add(pos, val - real[pos]);
	}
	int63 query0(int63 a) {
		int63 sol = 0;
		int63 cur = 0;
		a++;
		while (a) {
			if (a % 2 == 1) {
				sol += data[(a << cur) - 1];
			}
			cur++;
			a /= 2;
		}
		return sol;
	}
	int63 query(int63 a, int63 b) {
		return query0(b) - query0(a - 1);
	}
};
struct fenwickOPT {
	int63 n;
	vector<int63> data;
	void init(int63 nn) {
		n = nn;
		data = vector<int63>(n, 0);
	}
	void add(int63 pos, int63 val) {
		pos++;
		while (pos <= n) {
			data[pos - 1] += val;
			pos += (pos & (-pos));
		}
	}
	int63 query0(int63 a) {
		int63 sol = 0;
		a++;
		while (a) {
			sol += data[a - 1];
			a -= (a & (-a));
		}
		return sol;
	}
};
void setIO(string s) { //this function is the template that redefines the standard IO
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}
point mi(point a, point b) {
	return { a.first - b.first,a.second - b.second };
}
bool isleft(point a, point b, point c) {//line from a to b, when it is 0,0 -> 0,1
	if (a.first == b.first) {
		return (c.first < a.first) ^ (a.second > b.second);
	}
	long double m = (b.second - a.second) / ((double)b.first - a.first);
	long double y = a.second - a.first * m;
	return ((c.second - y - c.first * m) > 0) ^ (a.first > b.first);
}
bool online(point a, point b, point c) {//line from a to b, when it is 0,0 -> 0,1
	c = mi(c, a);
	b = mi(b, a);
	a = mi(a, a);
	return ((a == b) || (b.second * c.first == c.second * b.first));
}
bool linein(point a, point b, point c) {//line from a to b, when it is 0,0 -> 0,1
	b.first -= a.first;
	c.first -= a.first;
	a.first = 0;
	b.second -= a.second;
	c.second -= a.second;
	a.second = 0;
	if (b.second < 0) {
		b.second *= -1;
		c.second *= -1;
	}
	if (b.first < 0) {
		b.first *= -1;
		c.first *= -1;
	}
	if (b.first == 0) {
		return ((c.first == 0) && (c.second >= 0) && (c.second <= b.second));
	}
	long double m = (b.second - a.second) / ((double)b.first - a.first);
	long double cy = abs(c.second - c.first * m);
	return ((abs(cy) < 1e-11) && (c.first >= 0) && (c.first <= b.first));
}
bool interhelp(point a, point b, point c, point d) {
	if (online(a, b, c) || online(a, b, d)) {
		return 1;
	}
	return (isleft(a, b, c) ^ isleft(a, b, d));
}
bool intersect(ldpoint a, ldpoint b, ldpoint c, ldpoint d) {
	if (online(a, b, c) && online(a, b, d)) {
		b.first -= a.first;
		c.first -= a.first;
		d.first -= a.first;
		a.first = 0;
		b.second -= a.second;
		c.second -= a.second;
		d.second -= a.second;
		a.second = 0;
		if (b.first == 0) {
			if (b.second < 0) {
				b.second *= -1;
				c.second *= -1;
				d.second *= -1;
			}
			if (d.second > c.second) {
				swap(c, d);
			}
			return (c.second >= 0 && d.second <= b.second);
		}
		b.second /= b.first;
		c.second /= b.first;
		d.second /= b.first;
		c.first /= b.first;
		d.first /= b.first;
		b.first = 1;
		c.second -= c.first * b.second;
		d.second -= d.first * b.second;
		b.second = 0;
		if (d.first > c.first) {
			swap(c, d);
		}
		return (c.first >= -1e-11 && d.first <= 1e-11);
	}
	return (interhelp(a, b, c, d) && interhelp(c, d, a, b));
}
int63 vci(point a, point b) {
	return abs(a.first*b.second - a.second*b.first);
}
int63 ar(point a, point b, point c) {
	point bb = mi(b, a), cc = mi(c, a);
	return vci(bb, cc);
}
bool intriangle(point a, point b, point c, point d) {
	return ((ar(a, b, c) + ar(a, b, d) + ar(a, c, d)) == ar(b, c, d));
}
int63 countlattice(point a, point b) {
	b.first -= a.first;
	b.second -= a.second;
	a.first = 0;
	a.second = 0;
	b.first = abs(b.first);
	b.second = abs(b.second);
	if (b.first == 0) {
		return b.second;
	}
	vector<int63> ops = divlist(b.first);
	fort(0, (int63)ops.size()) {
		if ((b.second * ops[i] % b.first) == 0) {
			return b.first / ops[i];
		}
	}
	return 0;
}
struct Line {
	mutable int63 m, b, p;
	const bool real;//real = comparison 1, not real = comparison 2
	bool operator<(const Line& o) const { if (real && o.real) { return (m < o.m); } else { return p < o.p; } };
};
struct cht : multiset<Line, less<Line>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	const int63 inf = 9223372036854775807;
	int63 div(int63 a, int63 b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b);
	}
	//isect does ???
	//takes 2 iterators.
	bool isect(iterator x, iterator y) {
		if (y == end()) { x->p = inf; return false; }
		if (x->m == y->m) x->p = x->b > y->b ? inf : -inf;
		else x->p = div(y->b - x->b, x->m - y->m);
		return x->p >= y->p;
	}
	//adds a line...
	//how? 
	void add(int63 b, int63 m) {
		auto z = insert({ m, b, 0, 1 }), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
	}
	void init() {
		add(-9999999999999999, 0);
	}
	int63 query(int63 x) {
		if (empty()) exit(1);
		auto l = *(lower_bound({ 0, 0, x, 0 }));
		return l.m * x + l.b;
	}
};
bool spchfunc(point a, point b) {
	if (a.first == 0) {
		if (b.first == 0) {
			return a.second < b.second;
		}
		return 1;
	}
	if (b.first == 0) {
		return 0;
	}
	if (a.second * b.first != b.second * a.first) {
		return (a.second * b.first > b.second * a.first);
	}
	return (a.first < b.first);
}
vector<int63> ch(vector<int63> pts) {
	vector<point> ans;
	fort(0, pts.size() / 2) {
		ans.push_back({ pts[i * 2],pts[i * 2 + 1] });
	}
	sort(all(ans));
	point a0 = ans[0];
	fort(0, ans.size()) {
		ans[i] = mi(ans[i], a0);
	}
	sort(all(ans), spchfunc);
	fortb(0, ans.size() - 1) {
		if (ans[i].second * ans[i + 1].first != ans[i].first * ans[i + 1].second) {
			reverse(ans.begin() + i + 1, ans.begin() + ans.size());
			break;
		}
	}
	vector<bool>ich(ans.size(), 1);
	vector<int63> ret;
	vector<int63> st(2);
	st[0] = 0;
	st[1] = 1;
	fort(2, ans.size()) {
		while (st.size() > 1 && (!online(ans[st[st.size() - 2]], ans[st[st.size() - 1]], ans[i]) && isleft(ans[st[st.size() - 2]], ans[st[st.size() - 1]], ans[i]))) {
			ich[st[st.size() - 1]] = 0;
			st.pop_back();
		}
		st.push_back(i);
	}
	fort(0, ans.size()) {
		ans[i] = mi(ans[i], mi({ 0,0 }, a0));
	}
	fort(0, ans.size()) {
		if (!ich[i]) {
			continue;
		}
		ret.push_back(ans[i].first);
		ret.push_back(ans[i].second);
	}
	return ret;
}
struct Pqueue {
	#define Spoint pair<double,int63>
	vector<Spoint> vals;
	void add(Spoint ex) {
		vals.push_back(ex);
		int63 cr = vals.size() - 1;
		while (cr && vals[cr].first < vals[cr / 2].first) {
			swap(vals[cr], vals[cr / 2]);
			cr /= 2;
		}
	}
	void hpf() {
		int63 cr = 0;
		while (cr * 2 < vals.size()) {
			if (cr * 2 + 1 < vals.size() && vals[cr * 2 + 1].first < vals[cr * 2].first && vals[cr * 2 + 1].first < vals[cr].first) {
				swap(vals[cr], vals[cr * 2 + 1]);
				cr *= 2;
				cr++;
				continue;
			}
			if (vals[cr * 2].first < vals[cr].first) {
				swap(vals[cr], vals[cr * 2]);
				cr *= 2;
				continue;
			}
			break;
		}
	}
	void rem() {
		if (!vals.size()) {
			return;
		}
		swap(vals[0], vals[vals.size() - 1]);
		vals.pop_back();
		hpf();
	}
	int63 get() {
		if (!vals.size()) {
			return -1;
		}
		return vals[0].second;
	}
};
struct Seg {
	int63 l, r, v, t;
	Seg *lp, *rp;
	int63 v0() {
		if (t == 0) {
			return 999999999999;//min
		}
		if (t == 1) {
			return -999999999999;//max
		}
		if (t == 10) {
			return -999999999999;//min*
		}
		if (t == 11) {
			return 999999999999;//max*
		}
	}
	int63 v1() {
		if (t == 0) {
			return 999999999999;//min
		}
		if (t == 1) {
			return -999999999999;//max
		}
		if (t == 10) {
			return 999999999999;//min*
		}
		if (t == 11) {
			return -999999999999;//max*
		}
	}
	int63 act(int63 a, int63 b) {
		if (t == 0) {
			return min(a, b);
		}
		if (t == 1) {
			return max(a, b);
		}
		if (t == 10) {
			return min(a, b);
		}
		if (t == 11) {
			return max(a, b);
		}
	}
	void pull() {
		v = act(lp->v, rp->v);
	}
	Seg(int63 l, int63 r, int63 t) : l(l), r(r), t(t) {
		if (l == r) {
			v = v0();
			lp = NULL;
			rp = NULL;
			return;
		}
		lp = new Seg(l, (l + r) / 2, t);
		rp = new Seg((l + r) / 2 + 1, r, t);
		pull();
	}
	void upd(int63 p, int63 v) {
		if (l == r) {
			this->v = v;
			return;
		}
		if (p <= (l + r) / 2) {
			lp->upd(p, v);
		} else {
			rp->upd(p, v);
		}
		pull();
	}
	int63 query(int63 l, int63 r) {
		if (l > this->r || r < this->l) {
			return v1();
		}
		if (l <= this->l && r >= this->r) {
			return v;
		}

		return act(lp->query(l, r), rp->query(l, r));
	}
};
struct Dsu {
	vector<int63> f;
	vector<int63> s;
	Dsu(int63 n) {
		f = vector<int63>(n, -1);
		s = vector<int63>(n, 1);
	}
	int63 F(int63 x) {
		if (f[x] == -1) {
			return x;
		}
		return (f[x] = F(f[x]));
	}
	int63 S(int63 x) {
		return s[F(x)];
	}
	bool sm(int63 a, int63 b) {
		return F(a) == F(b);
	}
	void mrg(int63 a, int63 b) {
		a = F(a);
		b = F(b);
		if (a == b) {
			return;
		}
		if (s[a] > s[b]) {
			s[a] += s[b];
			f[b] = a;
		} else {
			s[b] += s[a];
			f[a] = b;
		}
	}
};

int63 t = 1;

bool mulK(int63 a, int63 b) {
	int63 c = a * b;
	if (c < 0 || c > (1e18 + 1e5) || c % a || c % b || ((c / a) != b) || ((c / b) != a)) {
		return 0;
	}
	return 1;
}

int main() {
	//setIO("tallbarn");
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(NULL));
	if (t == 0) {
		cin >> t;
	}
	do {
		make(n);
		make(A);
		make(B);
		//A,B
		//(x,y) -> ((x + B + 1) % A,y)
		//gcd(B+1,A) = ?
		//1 -> all ok
		//B = 1 -> (2t,0)
		//A * B / gcd
		A /= gcd(A, B + 1);
		int63 c;
		if (mulK(A, B)) {
			c = A * B;
		} else {
			c = 1e18 + 1e5;
		}
		vector<point> evnt;
		int63 L = 0;
		fort(0, n) {
			int63 a, b;
			cin >> a >> b;
			if (b - a > L) {
				L = b - a;
			}
			b -= a - (a % c);
			a %= c;
			if (b >= a + c - 1) {
				evnt.push_back({ 0,-1 });
				evnt.push_back({ c - 1,1 });
			} else if (b >= c) {
				evnt.push_back({ a,-1 });
				evnt.push_back({ c - 1,1 });
				evnt.push_back({ 0,-1 });
				evnt.push_back({ b - c,1 });
			} else {
				evnt.push_back({ a,-1 });
				evnt.push_back({ b,1 });
			}
		}
		sort(all(evnt));
		int63 ans = 0, cr = 0, pp = 0;
		fort(0, evnt.size()) {
			//cout << evnt[i].first << ' ' << -evnt[i].second << endl;
			if (cr) {
				ans += evnt[i].first - pp;
			}
			pp = evnt[i].first;
			if (evnt[i].second > 0) {
				cr--;
			} else {
				cr++;
				if (cr == 1) {
					ans++;
				}
			}
		}
		if (L <= c) {
			cout << ans << endl;
		} else {
			cout << c << endl;
		}
	} while (--t);
	return 0;
}

Compilation message

strange_device.cpp: In function 'int63 palpref(std::string&)':
strange_device.cpp:19:64: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
      |                                                                ^
strange_device.cpp:21:30: note: in expansion of macro 'forl'
   21 | #define forn(name,start,end) forl(name,start,end,1)
      |                              ^~~~
strange_device.cpp:25:26: note: in expansion of macro 'forn'
   25 | #define forto(start,end) forn(j,start,end)
      |                          ^~~~
strange_device.cpp:397:2: note: in expansion of macro 'forto'
  397 |  forto(0, s.size()) {
      |  ^~~~~
strange_device.cpp: In function 'std::vector<long long int> ch(std::vector<long long int>)':
strange_device.cpp:19:64: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
      |                                                                ^
strange_device.cpp:21:30: note: in expansion of macro 'forl'
   21 | #define forn(name,start,end) forl(name,start,end,1)
      |                              ^~~~
strange_device.cpp:23:25: note: in expansion of macro 'forn'
   23 | #define fort(start,end) forn(i,start,end)
      |                         ^~~~
strange_device.cpp:652:2: note: in expansion of macro 'fort'
  652 |  fort(0, pts.size() / 2) {
      |  ^~~~
strange_device.cpp:19:64: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
      |                                                                ^
strange_device.cpp:21:30: note: in expansion of macro 'forl'
   21 | #define forn(name,start,end) forl(name,start,end,1)
      |                              ^~~~
strange_device.cpp:23:25: note: in expansion of macro 'forn'
   23 | #define fort(start,end) forn(i,start,end)
      |                         ^~~~
strange_device.cpp:657:2: note: in expansion of macro 'fort'
  657 |  fort(0, ans.size()) {
      |  ^~~~
strange_device.cpp:19:64: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
      |                                                                ^
strange_device.cpp:21:30: note: in expansion of macro 'forl'
   21 | #define forn(name,start,end) forl(name,start,end,1)
      |                              ^~~~
strange_device.cpp:23:25: note: in expansion of macro 'forn'
   23 | #define fort(start,end) forn(i,start,end)
      |                         ^~~~
strange_device.cpp:672:2: note: in expansion of macro 'fort'
  672 |  fort(2, ans.size()) {
      |  ^~~~
strange_device.cpp:19:64: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
      |                                                                ^
strange_device.cpp:21:30: note: in expansion of macro 'forl'
   21 | #define forn(name,start,end) forl(name,start,end,1)
      |                              ^~~~
strange_device.cpp:23:25: note: in expansion of macro 'forn'
   23 | #define fort(start,end) forn(i,start,end)
      |                         ^~~~
strange_device.cpp:679:2: note: in expansion of macro 'fort'
  679 |  fort(0, ans.size()) {
      |  ^~~~
strange_device.cpp:19:64: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
      |                                                                ^
strange_device.cpp:21:30: note: in expansion of macro 'forl'
   21 | #define forn(name,start,end) forl(name,start,end,1)
      |                              ^~~~
strange_device.cpp:23:25: note: in expansion of macro 'forn'
   23 | #define fort(start,end) forn(i,start,end)
      |                         ^~~~
strange_device.cpp:682:2: note: in expansion of macro 'fort'
  682 |  fort(0, ans.size()) {
      |  ^~~~
strange_device.cpp: In member function 'void Pqueue::hpf()':
strange_device.cpp:704:17: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<std::pair<double, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  704 |   while (cr * 2 < vals.size()) {
      |          ~~~~~~~^~~~~~~~~~~~~
strange_device.cpp:705:19: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<std::pair<double, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  705 |    if (cr * 2 + 1 < vals.size() && vals[cr * 2 + 1].first < vals[cr * 2].first && vals[cr * 2 + 1].first < vals[cr].first) {
      |        ~~~~~~~~~~~^~~~~~~~~~~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:19:64: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
      |                                                                ^
strange_device.cpp:21:30: note: in expansion of macro 'forl'
   21 | #define forn(name,start,end) forl(name,start,end,1)
      |                              ^~~~
strange_device.cpp:23:25: note: in expansion of macro 'forn'
   23 | #define fort(start,end) forn(i,start,end)
      |                         ^~~~
strange_device.cpp:912:3: note: in expansion of macro 'fort'
  912 |   fort(0, evnt.size()) {
      |   ^~~~
strange_device.cpp: In function 'void setIO(std::string)':
strange_device.cpp:486:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  486 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:487:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  487 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	6 ms	976 KB	Output is correct
3	Correct	6 ms	848 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	6 ms	848 KB	Output is correct
17	Correct	66 ms	4528 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct

Subtask #2

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct

Subtask #3

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	416 ms	33220 KB	Output is correct

Subtask #4

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	577 ms	33168 KB	Output is correct
3	Correct	601 ms	33352 KB	Output is correct
4	Correct	568 ms	33168 KB	Output is correct

Subtask #5

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	577 ms	33168 KB	Output is correct
3	Correct	601 ms	33352 KB	Output is correct
4	Correct	568 ms	33168 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	591 ms	33188 KB	Output is correct
7	Correct	589 ms	33332 KB	Output is correct
8	Correct	604 ms	33336 KB	Output is correct
9	Correct	694 ms	33168 KB	Output is correct

Subtask #6

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	577 ms	33168 KB	Output is correct
3	Correct	601 ms	33352 KB	Output is correct
4	Correct	568 ms	33168 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	55 ms	4460 KB	Output is correct
7	Correct	79 ms	4508 KB	Output is correct
8	Correct	56 ms	4504 KB	Output is correct
9	Correct	67 ms	4472 KB	Output is correct
10	Correct	53 ms	4480 KB	Output is correct
11	Correct	57 ms	4508 KB	Output is correct
12	Correct	53 ms	4508 KB	Output is correct
13	Correct	75 ms	4488 KB	Output is correct
14	Correct	56 ms	4484 KB	Output is correct
15	Correct	65 ms	4440 KB	Output is correct
16	Correct	67 ms	4476 KB	Output is correct
17	Correct	59 ms	4464 KB	Output is correct
18	Correct	609 ms	33148 KB	Output is correct
19	Correct	580 ms	33164 KB	Output is correct
20	Correct	705 ms	33160 KB	Output is correct
21	Correct	63 ms	4468 KB	Output is correct
22	Correct	52 ms	4464 KB	Output is correct
23	Correct	171 ms	16792 KB	Output is correct

Subtask #7

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	67 ms	4516 KB	Output is correct
3	Correct	65 ms	4536 KB	Output is correct
4	Correct	736 ms	33156 KB	Output is correct
5	Correct	65 ms	4544 KB	Output is correct
6	Correct	63 ms	4544 KB	Output is correct
7	Correct	63 ms	4532 KB	Output is correct
8	Correct	66 ms	4468 KB	Output is correct
9	Correct	71 ms	4556 KB	Output is correct
10	Correct	71 ms	4484 KB	Output is correct
11	Correct	62 ms	4480 KB	Output is correct
12	Correct	56 ms	4472 KB	Output is correct
13	Correct	68 ms	4444 KB	Output is correct
14	Correct	696 ms	33224 KB	Output is correct
15	Correct	64 ms	4452 KB	Output is correct
16	Correct	586 ms	33232 KB	Output is correct
17	Correct	608 ms	33252 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct

Subtask #8

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	6 ms	976 KB	Output is correct
3	Correct	6 ms	848 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	6 ms	848 KB	Output is correct
17	Correct	66 ms	4528 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct
23	Correct	1 ms	204 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	1 ms	332 KB	Output is correct
28	Correct	416 ms	33220 KB	Output is correct
29	Correct	1 ms	204 KB	Output is correct
30	Correct	577 ms	33168 KB	Output is correct
31	Correct	601 ms	33352 KB	Output is correct
32	Correct	568 ms	33168 KB	Output is correct
33	Correct	1 ms	204 KB	Output is correct
34	Correct	591 ms	33188 KB	Output is correct
35	Correct	589 ms	33332 KB	Output is correct
36	Correct	604 ms	33336 KB	Output is correct
37	Correct	694 ms	33168 KB	Output is correct
38	Correct	1 ms	204 KB	Output is correct
39	Correct	55 ms	4460 KB	Output is correct
40	Correct	79 ms	4508 KB	Output is correct
41	Correct	56 ms	4504 KB	Output is correct
42	Correct	67 ms	4472 KB	Output is correct
43	Correct	53 ms	4480 KB	Output is correct
44	Correct	57 ms	4508 KB	Output is correct
45	Correct	53 ms	4508 KB	Output is correct
46	Correct	75 ms	4488 KB	Output is correct
47	Correct	56 ms	4484 KB	Output is correct
48	Correct	65 ms	4440 KB	Output is correct
49	Correct	67 ms	4476 KB	Output is correct
50	Correct	59 ms	4464 KB	Output is correct
51	Correct	609 ms	33148 KB	Output is correct
52	Correct	580 ms	33164 KB	Output is correct
53	Correct	705 ms	33160 KB	Output is correct
54	Correct	63 ms	4468 KB	Output is correct
55	Correct	52 ms	4464 KB	Output is correct
56	Correct	171 ms	16792 KB	Output is correct
57	Correct	1 ms	256 KB	Output is correct
58	Correct	67 ms	4516 KB	Output is correct
59	Correct	65 ms	4536 KB	Output is correct
60	Correct	736 ms	33156 KB	Output is correct
61	Correct	65 ms	4544 KB	Output is correct
62	Correct	63 ms	4544 KB	Output is correct
63	Correct	63 ms	4532 KB	Output is correct
64	Correct	66 ms	4468 KB	Output is correct
65	Correct	71 ms	4556 KB	Output is correct
66	Correct	71 ms	4484 KB	Output is correct
67	Correct	62 ms	4480 KB	Output is correct
68	Correct	56 ms	4472 KB	Output is correct
69	Correct	68 ms	4444 KB	Output is correct
70	Correct	696 ms	33224 KB	Output is correct
71	Correct	64 ms	4452 KB	Output is correct
72	Correct	586 ms	33232 KB	Output is correct
73	Correct	608 ms	33252 KB	Output is correct
74	Correct	1 ms	204 KB	Output is correct
75	Correct	1 ms	204 KB	Output is correct
76	Correct	1 ms	204 KB	Output is correct
77	Correct	1 ms	204 KB	Output is correct
78	Correct	1 ms	312 KB	Output is correct
79	Correct	8 ms	1232 KB	Output is correct
80	Correct	780 ms	48888 KB	Output is correct
81	Correct	762 ms	48868 KB	Output is correct
82	Correct	737 ms	48796 KB	Output is correct
83	Correct	693 ms	49108 KB	Output is correct
84	Correct	721 ms	49260 KB	Output is correct
85	Correct	747 ms	49128 KB	Output is correct
86	Correct	180 ms	24924 KB	Output is correct
87	Correct	1 ms	204 KB	Output is correct