Codeforces Round #628 (Div. 2) 一道比较简单的构造题。
题目链接:Codeforces 1325A。
系列题解:
1. 「题解」Codeforces Round #628 (Div. 2) A EhAb AnD gCd;
2. 「题解」Codeforces Round #628 (Div. 2) B CopyCopyCopyCopyCopy;
3. 「题解」Codeforces Round #628 (Div. 2) C Ehab and Path-etic MEXs;
4. 「题解」Codeforces Round #628 (Div. 2) D Ehab the Xorcist;
5. 「题解」Codeforces Round #628 (Div. 2) E Ehab’s REAL Number Theory Problem;
6. 「题解」Codeforces Round #628 (Div. 2) F Ehab’s Last Theorem。
题目
原题
题意简述
对于已知的 $x$,存在 $a,b$ 满足 $\gcd(a,b)+\operatorname{lcm}(a,b)=x$,求 $a,b$。如有多解,输出任意一对。
输入有多组数据,数据组数用 $t$ 表示。
数据范围
$$1\leq t\leq 100$$
$$2\leq x\leq 10^9$$
时空限制
见原题 pdf
文件。
题解
思路
首先发现
- 如果 $x$ 是大于一的奇数,$\gcd(x-1,1)=1,\operatorname{lcm}(x-1,1)=x-1$。
- 如果 $x$ 是大于一的偶数,$\gcd(\frac{x}{2},\frac{x}{2})=\frac{x}{2},\operatorname{lcm}(\frac{x}{2},\frac{x}{2})=\frac{x}{2}$。
所以答案在 $x$ 是奇数时是 $1$ 和 $x-1$,在 $x$ 是偶数时是 $\frac{x}{2}$ 和 $\frac{x}{2}$。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){ //快读
reg bool f=false;
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return f?-res:res;
}
int x;
int main(void){
reg int T=read(); //多组数据
while(T--){
x=read(); //读入 x
if(x&1) //奇数
printf("%d %d\n",1,x-1); //奇数
else //偶数
printf("%d %d\n",x/2,x/2); //偶数
}
return 0;
}
近期评论