Codeforces #942 : Div1 B2. Reverse Card (Hard Version)

こちらが本命。
https://codeforces.com/contest/1967/problem/B2

問題

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

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

解法

bとg=gcd(a,b)の値を総当たりし、b*gがa+bの何倍か総当たりしよう。

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(int g2=1;g2<=M;g2++) {
			for(int g=g2;g<=M;g+=g2) {
				for(int b=1;b<g&&b*g<=M;b++) {
					int a=g2-b;
					if(a>=1&&1LL*a*g<=N&&__gcd(a,b)==1) ret++;
				}
			}
		}
		cout<<ret<<endl;
	}
}

まとめ

Easyに比べるとだいぶ苦戦した。