[GYM 101755]Restoring Numbers

题面描述

已知两个正整数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