Chlience

【题解】CF 1051B Relatively Prime Pairs
Problem传送门 >ω<题目大意:给定 $[l,r]$ ,问能否两两组合,每组之间互质Solution因为 $...
扫描右侧二维码阅读全文
24
2018/10

【题解】CF 1051B Relatively Prime Pairs

Problem

传送门 >ω<

题目大意:

给定 $[l,r]$ ,问能否两两组合,每组之间互质

Solution

因为 $l , r \leq 10^{18}$ 直接排除分解质因数之类的方法
显然序列可以写成 $a+1,a+2,a+3,\cdots,a+n$
gcd = 1
目前思路:
辗转相除,更相减损,欧拉函数...

想多了...

其实 $a$ 和 $a + 1$ 是互质的
按顺序输出即可
做完了qwq

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL read() {
    LL ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int main() {
    LL l = read() , r = read();
    puts("YES");
    for(LL i = l ; i <= r ; i += 2)
        printf("%lld %lld\n" , i , i + 1);
    return 0;
}
Last modification:October 30th, 2018 at 09:52 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment