yukicoder : No.3553 Good Quartet

これは力技で解いてしまった。
https://yukicoder.me/problems/no/3553

問題

正整数集合Sに対し、要素を追加・削除するクエリが与えられる。
そのつど、以下を満たす４要素の部分集合の個数を答えよ。

• ４要素からなる配列をAとすると、sum(A)をA[i]+A[j]が割り切れるような(i,j)は４組である。

解法

小さい値で実験すると、条件を満たす４要素の比は

• 1:5:7:11
• 1:11:19:29

の２択である。
要素の追加・削除の際に、この４つ組の増減差分を求めて行けばよい。

int N,Q;
set<ll> S;

vector<int> A={1,5,7,11};
vector<int> B={1,11,19,29};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>x;
		S.insert(x);
	}
	ll ret=0;
	FORR(a,S) {
		if(S.count(a*5)+S.count(a*7)+S.count(a*11)==3) ret++;
		if(S.count(a*11)+S.count(a*19)+S.count(a*29)==3) ret++;
	}
	while(Q--) {
		ll x,y;
		cin>>x>>y;
		if(x==1) {
			S.insert(y);
			FORR(a,A) if(y%a==0) {
				if(S.count(y/a*1)+S.count(y/a*5)+S.count(y/a*7)+S.count(y/a*11)==4) ret++;
			}
			FORR(a,B) if(y%a==0) {
				if(S.count(y/a*1)+S.count(y/a*11)+S.count(y/a*19)+S.count(y/a*29)==4) ret++;
			}
		}
		else {
			FORR(a,A) if(y%a==0) {
				if(S.count(y/a*1)+S.count(y/a*5)+S.count(y/a*7)+S.count(y/a*11)==4) ret--;
			}
			FORR(a,B) if(y%a==0) {
				if(S.count(y/a*1)+S.count(y/a*11)+S.count(y/a*19)+S.count(y/a*29)==4) ret--;
			}
			S.erase(y);
		}
		cout<<ret<<endl;
		
	}
}

まとめ

これ想定解は総当たりからの推測なのか証明なのかどっちだったんだろうな。