Codeforces #942 : Div1 B1. Reverse Card (Easy Version)

一見部分点に見えて別の問題出すのやめてくれ…。
https://codeforces.com/contest/1967/problem/B1

問題

正整数N,Mが与えられる。
以下を満たす整数対(a,b)はいくつあるか。

• aはN以下の正整数、bはM以下の正整数
• a+bはb*gcd(a,b)の倍数

解法

a+bがbの倍数ということはaもbの倍数でなければならない。
a=cbとすると、(a+b)=(c+1)bがb*gcd(a,b)=b^2の倍数なので、結局c+1がbの倍数であればよい。

bを総当たりし、そのうえで(c+1)b≦Nとなるcを数えればよい。

int T;
ll N,M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		
		ll ret=0;
		for(i=1;i<=M;i++) {
			for(x=1;x*i<=N;x++) if((x+1)%i==0) ret++;
		}
		cout<<ret<<endl;
	}
}

まとめ

なんかいまいち面白みがないけど、Hardへの助走だと思えばよいか…。