Codeforces Round #628 (Div. 2) 一道比较简单的构造题。

题目链接：Codeforces 1325A。

[toc]

系列题解：
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;
}