题解：P9788 [ROIR 2020 Day2] 区域规划

法1

枚举 \(a,b,c\)，考虑到 \(c\) 的最小值为 \(\max(1,\frac{(a\cdot b−n)}{b})\)，所以直接剪枝即可通过。

代码：

#include<bits/stdc++.h>
using namespace std;
int ans,n,m;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int a=1;a<=n;a++){
		if(a!=m){
			for(int b=a;b<=n;b++){
				if(b!=m&&a*b>n){
					for(int c=max(1,(a*b-n)/b);c<a;c++){
						int d=a*b-n;
						if(d%c==0&&d/c<b){
							ans+=2;
							if(a==b) ans--;
						}
					}
				}
				
			}	
		}
		
	}
	cout<<ans;
}

法2

想法来自于：https://www.cnblogs.com/7KByte/p/15567809.html

枚举 \(a\) 和 \(c\) ，使用扩展欧几里得算法来求解不定方程 \(a \cdot b - c \cdot d = \gcd(a,c)\) 然后变换成 \(a \cdot b - c \cdot d = n\)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,x;
int exgcd(int a,int b,int &x,int &y){
	if(!b){
		x=1,y=0;
		return a;
	}
	int xx=0,yy=0;
	int g=exgcd(b,a%b,xx,yy);
	x=yy,y=xx-a/b*yy;
	return g;
}
int main(){
	cin>>n>>x;
	int ans=0;
	for(int a=2;a<=n;a++){
		if(a!=x){
			for(int c=1;c<=a-1;c++){
				int b=0,d=0;
				int g=exgcd(a,c,b,d);
				if(n%g) continue;
				int k=n/g,kb=c/g,kd=a/g;
				b*=k,b=(b%kb+kb)%kb;
				d=(n-a*b)/c;
				while(b>-d){
					if(d<0&&b!=x)ans++;
					b+=kb,d-=kd;
				}
			}	
		}
		
	}
	cout<<ans;
	return 0;
}