제출 #968727

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
968727		vjudge1	이상한 기계 (APIO19_strange_device)	C++17	100 / 100	372 ms	112252 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

class strangeDevice{
private:
	using ll=long long;
	using i128=__int128;
public:
	long long count(long long A, long long B, vector<long long> left, vector<long long> right) {
		long long ans{0ll};
		i128 F = i128(A / __gcd(A, B + 1)) * B;
		vector<pair<ll,ll> > rgs, rgx;
		for(int i{0}; i < (int)left.size(); ++i){
			long long l{left[i]}, r{right[i]};
			long long len{r - l + 1};
			if(len>=F) return F;
			l %= F, r %= F;
			if(l <= r) rgs.emplace_back(l, r);
			else rgs.emplace_back(l, F - 1),rgs.emplace_back(0, r);
		}
		sort(rgs.begin(), rgs.end());
		for(auto [l,r]: rgs){
			if(rgx.empty() || rgx.back().second < l ) rgx.emplace_back(l, r);
			else rgx.back().second = max(rgx.back().second, r);
		}
		for(auto [l,r]: rgx) ans += r - l + 1;
		return ans;
	}
}solution;

int main() {
	cin.tie(0) -> sync_with_stdio(0);
	int lengthOfL;
	long long A, B;
	cin >> lengthOfL >> A >> B;
	vector<long long> L(lengthOfL),R(lengthOfL);
	for(int i = 0; i < lengthOfL; i++ ){
		cin >> L[i] >> R[i];
	}
	cout << solution.count(A, B, L, R) << '\n';
	return 0;
}

/*
这类题目可以考虑找循环节

t1=xB+y,t2=x1B+y
x1B+y+[(x1B+y)/B]=x2B+y+[(x2B+y)/B]
x1B+y+x1=x2B+y+x2
(x1-x2)(B+1)=0 (mod A)
x1-x2=K* A/gcd(A,B+1)
t1-t2=K* AB/gcd(A,B+1)	
∴循环节(最小正周期) F=AB/gcd(A,B+1)

转化成：有一些区间，求区间的并 %F 意义下有多少个不同的数
len>=F: ans=F
否则转化成了区间覆盖操作
*/

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30