kmjp's blog

競技プログラミング参加記です

九州大学プログラミングコンテスト2018 : I - Buffalo

まぁ言われてみれば800ptぐらいか。
https://beta.atcoder.jp/contests/qupc2018/tasks/qupc2018_i

問題

N個の容器があり、各容器の容量はA[i]リットルである。
このうち2つの容器を用いたとき、無限にある水源から、両容器合わせてKリットルを測り切れるような組み合わせは何通りか。

解法

Kリットルの容器およびK/2リットルの容器が2つある場合は明らかにはかり切れる。
以下、異なる容量の容器の対を考えよう。

XリットルとYリットルの容器でKリットルを測りきれる条件は以下のとおりである。

  • X+Y≧K
  • GCD(X,Y)がKの約数

包除原理を用いて、前者を満たす組み合わせを、GCD毎に分類しよう。
前者は尺取り法の要領で求めることができる。
あとはGCDがKの約数になるものの総和が解。

int N,K;
ll A[3010101];
ll SA[3010101];
ll P[3010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>x, A[x]++;
	
	ll ret=0;
	for(i=1000000;i>=1;i--) {
		ll tot=0;
		for(j=i;j<=3000000;j+=i) {
			SA[j]=SA[j-i]+A[j];
			tot=SA[j];
			P[i]-=P[j];
		}
		for(j=i;j<=1000000;j+=i) {
			int sum=(K-j+i-1)/i*i;
			if(sum<=j) sum=j+i;
			P[i]+=A[j]*(tot-SA[sum-i]);
		}
		
		if(K%i==0) ret+=P[i];
	}
	
	ret+=A[K]*(A[K]-1)/2;
	if(K%2==0) ret+=A[K/2]*(A[K/2]-1)/2;
	
	cout<<ret<<endl;
	
	
	
}

まとめ

最近包除原理で苦労しているのでちょうどよい題材でした。