D.Cirno's Perfect Equation Class

题目大意

给定三个整数 $k,c,nk,c,n$ 求满足以下条件的有序对 $(a,b)(a,b)$ 的个数： $ka+b=cka+b=c$ ， $b\mathrm{\mid }cb|c$ ， $gcd(a,b)>ngcd(a,b)>n$

解题思路

注意到 $bb$ 是 $cc$ 的因子，因此对 $bb$ 枚举，判断计数即可

时间复杂度

$O(q{c}^{\frac{1}{2}})O(qc^\backslash frac\{1\}\{2\})$

参考代码

void solve()
{
	ll k,c,n,a,tb;
	cin >> k >> c >> n;
	ll r=floor(sqrt(c)),cnt=0;
	for(ll b=1;b*b<=c;b++){
		if(c%b==0&&(c-b)%k==0){
			a=(c-b)/k;
			if(a&&b&&gcd(a,b)>=n) cnt++;
		}
		tb=c/b;
		if(tb!=b&&c%tb==0&&(c-tb)%k==0){
			a=(c-tb)/k;
			if(a&&tb&&gcd(a,tb)>=n) cnt++;
		}
	}cout << cnt << endl;
}