Codeforces #775 : Div1 B. Integral Array

ずいぶんすんなり解いてるな。
https://codeforces.com/contest/1648/problem/B

問題

整数列Aが与えられる。
Aの2要素x≧yを任意に選んだ場合、常にfloor(x/y)がA中に存在するなら、Aは完全であるといえる。
Aが完全か判定せよ。

解法

floor(x/y)=zを総当たりしよう。zがA中に存在し、かつyが存在しないのにz*y以上z*(y+1)未満の値がAに存在するとき、Aは完全でありえない。

int T;
int N,C;
int A[1010101];
int S[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>C;
		FOR(i,C+1) A[i]=0;
		FOR(i,N) {
			cin>>x;
			A[x]=1;
		}
		for(i=1;i<=C;i++) {
			S[i]=S[i-1]+A[i];
		}
		int ng=0;
		for(i=1;i<=C;i++) if(A[i]) {
			for(x=i;x<=C;x+=i) {
				y=S[min(x+i-1,C)]-S[x-1];
				if(y&&A[x/i]==0) ng=1;
			}
		}
		if(ng) {
			cout<<"No"<<endl;
		}
		else {
			cout<<"Yes"<<endl;
		}
	}
}

まとめ

これは750ptとかでもいい気はするな。