Codeforces #846 : Div2 F. Three Chairs

この回は全完できた。
https://codeforces.com/contest/1780/problem/F

問題

distinctな値を取る整数列Aが与えられる。
Aから3要素を選んだ時、最小値と最大値のGCDが1となるのは何通りか。

解法

f(n) := GCDがnとなる選び方
g(n) := GCDがnの倍数となる選び方
とすると、g(n)が求められれば約数包除の要領で、f(n)が求まり、f(1)が求められる。

g(n)は、nの倍数を最小値・最大値とするときに、A中で最小値・最大値の間の値を取るものを数え上げればよい。

int N;
ll C[303030];
ll S[303030];

ll G[303030];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		C[x]++;
	}
	for(i=1;i<=300000;i++) {
		S[i]=S[i-1]+C[i];
	}
	
	for(int g=1;g<=300000;g++) {
		int num=0;
		ll sum=0;
		for(i=g;i<=300000;i+=g) if(C[i]) {
			G[g]+=S[i-1]*num-sum;
			num++;
			sum+=S[i];
		}
	}
	for(int g=300000;g>=1;g--) {
		for(i=g*2;i<=300000;i+=g) G[g]-=G[i];
	}
	cout<<G[1]<<endl;
	
}

まとめ

これはすんなりだったね。