Uva 10976 Fractions Again?! (テクニック暴力)

転送ドア:クリックして問題のリンクを開く
标题:nをあげて、2つの値x,yを求めさせます.彼に1/n=1/x+1/yを満足させ、そのうちx>=yはすべての成立したxとyを列挙する.
構想:yを列挙し、yの範囲はnから2*nである.
x<=yなので1/x<=1/y
また1/n=1/x+1/y
だから1/n-1/y=1/x
従って1/n−1/y<=1/y
だから1/n<=2/y
だからn>=2 y
上のコード:

#include
#include
#include
using namespace std;

int gcd(int a,int b){
	if(a == 0) return b;
	else return gcd(b%a,a);
}
int main(){
	int n ;
	while(~scanf("%d",&n)){
		int a,b;
		int ans = 0; 
		for(int i = n ; i <= 2*n ;i ++){
			b = i;
			int fenzi = b - n;
			int fenmu = b*n;

			int T = gcd(fenzi,fenmu);
			fenzi /= T;
			fenmu /= T;		
			if(fenzi == 1 && fenmu >= b)  
				ans++;
		}
		printf("%d
",ans);
		for(int i = n ; i <= 2*n ;i ++){
			b = i;
			int fenzi = b - n;
			int fenmu = b*n;

			int T = gcd(fenzi,fenmu);
			fenzi /= T;
			fenmu /= T;		
			if(fenzi == 1 && fenmu >= b)  
				printf("1/%d = 1/%d + 1/%d
",n,fenmu,b);
		}
	}
	return 0;
}