yukicoder : No.886 Direct

解いたのに記事書いてない問題、ちょくちょく残ってるな。
https://yukicoder.me/problems/no/886

問題

2次元座標中において、縦H個×横W個の計H*W個の点が等間隔で格子状に並んでいる。
ここ2点を選んでその間を線分で結ぶとき、他の点が線分上に載らないようなケースは何通りか。

解法

縦の2点を選ぶケースはW*(H-1)通りで、横の2点を選ぶケースはH*(W-1)通り。
あとは残る斜めのケースを考えよう。

横幅をdx、斜めをdyとなる場合を考える。以下、dxもdyも正の場合のみを考える。
解はgcd(dx,dy)=1である場合に(W-dx)*(H-dy)の総和を取ることになる。
dxを総当たりすることにすると、gcd(dx,dy)=1の時の(H-dy)の総和が取れればよい。

f(y) := dy|yとなるdyにおける(H-dy)の総和
を先に計算しておく。
dxの素因数は高々7個なので、素因数の組み合わせ2^7通りを総当たりし、包除原理の要領でf(y)を加減算していこう。

ll mo=1000000007;
ll H,W;

ll A[3030303];
vector<int> P[3030303];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	ll ret=0;
	// 横と縦
	ret=((W-1)*H+(H-1)*W)%mo;
	
	for(y=1;y<=H-1;y++) A[y]=H-y;
	for(y=1;y<=3000000;y++) {
		for(i=y*2;i<=3000000;i+=y) A[y]+=A[i];
		A[y]%=mo;
	}
	
	for(y=2;y<=3010101;y++) if(P[y].empty()) {
		for(i=y;i<=3010101;i+=y) P[i].push_back(y);
	}
	
	ll v=0;
	for(x=1;x<=W-1;x++) {
		int mask;
		ll tot=0;
		FOR(mask,1<<P[x].size()) {
			ll v=1;
			FOR(i,P[x].size()) if(mask&(1<<i)) v*=P[x][i];
			if(__builtin_popcount(mask)%2==0) tot+=A[v];
			else tot-=A[v];
		}
		ret+=tot%mo*(W-x)*2%mo;
	}
	cout<<(ret%mo+mo)%mo<<endl;
	
	
}

まとめ

実装はそこまで重くないので、今見ると★3.5位でもいい気はする。