1980 unit fraction partition~.cpp

湖南大学ACM-OJ的部分题目代码

#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;
int f[10];
int k=0;
int gcd(int a,int b){   //求最大公因子
	if (b==0) return a;
	else return gcd(b,a%b);
}

int shu (int p,int q,int a,int b,int n,double g2){
	int s=0;
	int p1,q1,p2,q2,h;
	double g,l;
	k++;
	for(int v=0;v<10;v++)
		cout<<k;
	cout<<endl;
//	cout<<p<<ends<<q<<ends<<a<<ends<<b<<ends<<n<<ends<<g2<<endl;
	
	if (n==0) return 0;
	for ( int i=q/p-1;i<=a/b+1;i++){
		if (i==0) continue;
		p1=1;
		q1=i;
        p2=q1*p-q;
	//	cout<<p1<<ends<<q1<<ends<<p2<<endl;
		if (p2<0) continue;
		q2=q*q1;
		h=gcd(p2,q2);
	//	cout<<q2<<ends<<p2<<ends<<h<<endl;
		p2=p2/h;
		q2=q2/h;
//      cout<<q2<<ends<<p2<<endl;
		g=double (p1)/q1;	
		l=double (p2)/q2;
//		cout<<g<<ends<<l<<endl;
		if (a-b*q1<0) break;
		f[n]=q1;
	
			
		if ((p2==0)&&g2>=g){			
			s++;
			cout<<"x1 "<<s<<endl;
			cout<<p1<<ends<<q1<<ends<<p2<<ends<<q2<<endl;
			continue;
		}
        if(p2==1 && n==2 && b*q1*q2<=a)
		{

			s++;
			cout<<"xx "<<s<<endl;
			cout<<p1<<ends<<q1<<ends<<p2<<ends<<q2<<endl;
			continue;
		}
		if (p2>0 && g2>=g && (n-1)*g>=l && n>2) {
//			cout<<"////////////////////////////////"<<endl;
//			cout<<"x2 "<<s<<endl;
			 s=s+shu(p2,q2,a,b*q1,n-1,g);
//			 cout<<"x3 "<<s<<endl;
		
		}
		if ((n-1)*g<l) 
		{
//			cout<<"break:"<<endl;
//			cout<<n-1<<ends<<g<<ends<<l<<endl;
			break;
		}
	}
	for( v=0;v<10;v++)
		cout<<k;
	cout<<endl;
	k--;
	return s;
}
main(){
	int p,q,a,n;
	scanf("%d%d%d%d",&p,&q,&a,&n);
	while(p!=0 && q!=0 && a!=0 && n!=0){
		int h=gcd(p,q);
		p=p/h;
		q=q/h;
		cout<<shu(p,q,a,1,n,q)<<endl;
//		for(int i=0;i<10;i++)
//			cout<<f[i]<<endl;
		scanf("%d%d%d%d",&p,&q,&a,&n);
	}

}