まぁ言われてみれば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; }
まとめ
最近包除原理で苦労しているのでちょうどよい題材でした。