[GYM 101755]Restoring Numbers

╰+哭是因爲堅強的太久メ 2023-08-17 17:38 93阅读 0赞

#### 题面描述 ####

已知两个正整数a,b的和s与最大公约数g，求a,b

#### 输入格式 ####

一共一行，包含两个正整数\\(s,g\\)。

#### 输出格式 ####

一共一行，若有解输出\\(a,b\\),否则输出\\(-1\\)。

#### 样例数据 ####

##### 样例输入 #####

6 2

##### 样例输出 #####

4 2

#### 题解 ####

很容易想到暴力的做法

#include<bits/stdc++.h>
    #define mod 1000000007
    #define maxn 1000005
    #define local
    using namespace std;
    inline char get(){
        static char buf[30000],*p1=buf,*p2=buf;
        return p1==p2 && (p2=(p1=buf)+fread(buf,1,30000,stdin),p1==p2)?EOF:*p1++;
    }
    inline int read(){
        register char c=get();register int f=1,_=0;
        while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
        while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
        return _*f;
    }
    int s,g,a=1,b=0x3f3f3f3f;
    signed main(){
        //freopen("1.txt","r",stdin);
        s=read(),g=read();
        int flag=1;
        while(b%g!=0){
            a=g*flag,b=s-a;
            flag++;
            if(a>=s){
                cout<<-1;
                return 0;
            } 
        }
        cout<<a<<" "<<b<<endl;
    }

不过拜倒在了\\(10^9\\)的数据范围之下。  
理智分析，我们可以发现：\\\[ a=c⋅g,b=d⋅g,(c,d)=1,s=a+b=(c+d)⋅g \\\]

故若满足\\\[g|sg|s , s>gs>g\\\]

则满足\\\[a=g,b=s−g\\\]

显然符合条件，否则无解

#include<bits/stdc++.h>
    #define mod 1000000007
    #define maxn 1000005
    #define local
    using namespace std;
    inline char get(){
        static char buf[30000],*p1=buf,*p2=buf;
        return p1==p2 && (p2=(p1=buf)+fread(buf,1,30000,stdin),p1==p2)?EOF:*p1++;
    }
    inline int read(){
        register char c=get();register int f=1,_=0;
        while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
        while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
        return _*f;
    }
    int main(){
        freopen("1.txt","r",stdin);
        int s,g;
        s=read(),g=read();
        if(s%g!=0||s==g)printf("-1\n");
        else printf("%d %d\n",g,s-g); 
        return 0;
    }

转载于:https://www.cnblogs.com/Chen574118090/p/11612993.html