Seletiva IOI 2017

selecao.cpp

// Ivan Carvalho
// Seleção - Seletiva IOI - OBI 2017
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2*1e6 + 10;
int A[MAXN],B[MAXN],soma[MAXN],N;
ll K;
int ax,bx,cx,mx,ay,by,cy,my;
int func(int val){
	ll total = 0;
	for(int i = 1;i<=N;i++){
		if(val - A[i] >= 0) total += 1LL*soma[val - A[i]];
	}
	return total >= K;
}
int main(){
	cin >> N >> K;
	cin >> ax >> bx >> cx >> mx;
	cin >> ay >> by >> cy >> my;
	A[1] = ax;
	B[1] = ay;
	for(int i = 2;i<=N;i++){
		A[i] = (A[i-1]*cx + bx) % mx;
		B[i] = (B[i-1]*cy + by) % my;
	}
	for(int i = 1;i<=N;i++){
		soma[B[i]]++;
	}
	for(int i = 1;i<MAXN;i++) soma[i] += soma[i-1];
	int ini = 0,fim = MAXN - 1,resp = -1,meio;
	while(ini <= fim){
		meio = (ini+fim)/2;
		if(func(meio)){
			resp = meio;
			fim = meio - 1;
		}
		else{
			ini = meio + 1;
		}
	}
	cout << resp << endl;
	return 0;
}