概述
解决这个两个问题：一般性可以相互转换，把不定方程寻找特殊解转为一般性整数方程 ，或者说把分数化为一般的代数式子。
- 如 要解4x+5y=7 这个方程
之所以叫特殊解，是因为范围确定性有影响，需要根据你你需要的范围进行求解
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
int gcd(int a,int b){
return !b?a:gcd(b,a%b);
}
int main(int argc, const char * argv[]) {
for(int x=1;x<1000;x++){
for(int y=1;y<1000;y++){
if(4*x-5*y==7){
cout<<"4*"<<x<<"-"<<"5*"<<y<<"=7"<<endl;
}
}
}
return 0;
}
- 转换为模板 ax+by=c 其中a4，b-5，c==7；
int main(int argc, const char * argv[]) {
for(int y=0;y<1000;y++){
if(7-(-5*y)%4==0){
cout<<"y="<<y<<endl;
cout<<"x="<<(7-(-5*y))/4<<endl;
}
}
return 0;
}
题目
标题：埃及分数
古埃及曾经创造出灿烂的人类文明，他们的分数表示却很令人不解。古埃及喜欢把一个分数分解为类似： 1/a + 1/b 的格式。
这里，a 和 b 必须是不同的两个整数，分子必须为 1
比如，2/15 一共有 4 种不同的分解法（姑且称为埃及分解法）：
1/8 + 1/120
1/9 + 1/45
1/10 + 1/30
1/12 + 1/20
那么， 2/45 一共有多少个不同的埃及分解呢（满足加法交换律的算同种分解）？ 请直接提交该整数（千万不要提交详细的分解式！）。
请严格按照要求，通过浏览器提交答案。
注意：只提交分解的种类数，不要写其它附加内容，比如：说明性的文字
answer：解决办法就是转换化整数求解，但是这里要注意范围，10000才能保证答案为7个：开始我没有注意到浮点数的问题，
按照模拟办法求解，也就是1/a+1/b==2/45 我让他们之间的相减的绝对值 小于1E-40 ，我认为可以得出结论，可是呵呵，一个是这个问题不是逼近
问题，另一个是没有注意到a<b 的问题，还有一个就是要注意的如果使用浮点数，必须要考虑精确度问题。如果这个直接模拟转化为分数问题也是可以直接
求解的，不过需要自己写一个分数类
- 核心code
int main()
{
init();
// 1/a + 1/b 2/45
double res=2/15;
for(int a=2;a<=10000;a++){
for(int b=2;b<a;b++){
if(45*a + 45*b == 2*a*b){
cout<<"1/"<< a << ", 1/ "<< b<<endl;
}
}
}
return 0;
}
- dfs解法
using namespace std;
const int INF= 1e9;
ll a,b,c,dep=1,ans[11],d[11],flag;
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
void print(int n)
{
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
cout<<endl;
}
void dfs(ll a,ll b,int t){
if(t>dep)return;
if(a==1 && b>d[t-1]){
d[t]=b;
if(!flag || d[t]<ans[t]) memcpy(ans,d,sizeof(d));
// print(t);
flag=1;
return;
}
ll l=b/a;
if(d[t-1]>=l) l=d[t-1]+1;
ll r=(dep-t+1)*b/a;
if(INF<r) r=INF-1;
if(flag && ans[dep]<=r) r=ans[dep]-1;//
for(ll i=l;i<=r;i++){
d[t]=i;
ll gc=gcd(i*a-b,b*i);
dfs((i*a-b)/gc,b*i/gc,t+1);
}
}
int main(){
cin>>a>>b;c=gcd(a,b);
a/=c;b/=c;d[0]=1;//d用来记录？
if(a==1){cout<<b<<endl;return 0;}//
while(dep<=10){
dfs(a,b,1);
if(flag){
for(int i=1;i<=dep;i++)
printf("%lld ",ans[i]);
return 0;
}
dep++;
}
return 0;
}
可能会用到的分数模板
#include <stdio.h>
struct fraction {
int numerator;
int denominator;
};
// 求解最大公约数
int find_gcd(int n1, int n2);
// 将分数化为最简形式
struct fraction reduce_fraction(struct fraction f);
// 分数的四则运算
struct fraction add_fractions(struct fraction f1, struct fraction f2);
struct fraction subtract_fractions(struct fraction f1, struct fraction f2);
struct fraction multiply_fractions(struct fraction f1, struct fraction f2);
struct fraction divide_fractions(struct fraction f1, struct fraction f2);
int main(void)
{
struct fraction f = { 21, 3 };
struct fraction f1 = { 8, 64 };
struct fraction f2 = { 9, 711 };
struct fraction reducedf = reduce_fraction(f);
printf("%d/%d reduced to simplest terms: %d/%d
", f.numerator,
f.denominator, reducedf.numerator, reducedf.denominator);
struct fraction addedf = add_fractions(f1, f2);
printf("%d/%d + %d/%d = %d/%d
", f1.numerator, f1.denominator,
f2.numerator, f2.denominator, addedf.numerator, addedf.denominator);
struct fraction subtractedf = subtract_fractions(f1, f2);
printf("%d/%d - %d/%d = %d/%d
", f1.numerator, f1.denominator,
f2.numerator, f2.denominator, subtractedf.numerator,
subtractedf.denominator);
struct fraction multipliedf = multiply_fractions(f1, f2);
printf("%d/%d * %d/%d = %d/%d
", f1.numerator, f1.denominator,
f2.numerator, f2.denominator, multipliedf.numerator,
multipliedf.denominator);
struct fraction dividedf = divide_fractions(f1, f2);
printf("%d/%d / %d/%d = %d/%d
", f1.numerator, f1.denominator,
f2.numerator, f2.denominator, dividedf.numerator,
dividedf.denominator);
return 0;
}
int find_gcd(int n1, int n2)
{
int temp;
while (n1 != 0) {
temp = n2 % n1;
n2 = n1;
n1 = temp;
}
return n2;
}
struct fraction reduce_fraction(struct fraction f)
{
int gcd = find_gcd(f.numerator, f.denominator);
f.numerator /= gcd;
f.denominator /= gcd;
return f;
}
struct fraction add_fractions(struct fraction f1, struct fraction f2)
{
f1.numerator *= f2.denominator;
f2.numerator *= f1.denominator;
struct fraction result = {
f1.numerator + f2.numerator,
f1.denominator * f2.denominator
};
result = reduce_fraction(result);
return result;
}
struct fraction subtract_fractions(struct fraction f1, struct fraction f2)
{
f1.numerator *= f2.denominator;
f2.numerator *= f1.denominator;
struct fraction result = {
f1.numerator - f2.numerator,
f1.denominator * f2.denominator
};
result = reduce_fraction(result);
return result;
}
struct fraction multiply_fractions(struct fraction f1, struct fraction f2)
{
struct fraction result = {
f1.numerator * f2.numerator,
f1.denominator * f2.denominator
};
result = reduce_fraction(result);
return result;
}
struct fraction divide_fractions(struct fraction f1, struct fraction f2)
{
struct fraction result = {
f1.numerator * f2.denominator,
f1.denominator * f2.numerator
};
result = reduce_fraction(result);
return result;
}