yukicoder : No.1201 お菓子配り-4

これは思い出せてよかった。
https://yukicoder.me/problems/no/1201

問題

整数列A,Bが与えられる。
両者から1要素ずつ選んだとき、その値をa,bとする。
b人の人にお菓子をあげる。その際k番目の人には2*floor(a*k/b)個のお菓子をあげるとする。

要素の選び方全通りに対し、あげるお菓子の個数の総和を求めよ。

解法

a,bは愚直に総当たりするとして、をO(1)で求めることを考えよう。
ここでピックの定理を使う。
(0,0)-(b,0)-(a-b)の3点を結ぶ三角形を考える。
floorの中身の総和は、この三角形内または辺上の格子点の数から、y=0の部分の格子点の数を引いたものである。
面積と辺上の格子点はO(1)で求められるので、内部の格子点数もO(1)で求められる。

int N,M;
ll A[2020];
ll B[2020];
const ll mo=1000000007;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	FOR(i,M) cin>>B[i];
	
	ll ret=0;
	FOR(y,N) FOR(x,M) {
		ll P=A[y];
		ll Q=B[x];
		ll S2=Q*P;
		ll g=__gcd(P,Q);
		ll B=g+P+Q;
		ll V=S2-B+2+2*((P-1)+g);
		ret+=V%mo;
	}
	cout<<ret%mo<<endl;
}

まとめ

ピックの定理に持ち込めたのはよかったね。