分數與不定方程

概述

解決這個兩個問題：一般性可以互相轉換，把不定方程尋找特殊解轉為一般性整數方程 ，或者說把分數化為一般的代數式子。

• 如 要解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 一共有多少個不同的埃及分解呢（滿足加法交換律的算同種分解）？ 請直接送出該整數（千萬不要送出詳細的分解式！）。

請嚴格按照要求，通過浏覽器送出答案。
注意：隻送出分解的種類數，不要寫其它附加内容，比如：說明性的文字      

• 核心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\n", f.numerator,
        f.denominator, reducedf.numerator, reducedf.denominator);

    struct fraction addedf = add_fractions(f1, f2);
    printf("%d/%d + %d/%d = %d/%d\n", 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\n", 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\n", 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\n", 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;
}