[Codeforces Round 1000(Div.2)] - A. Minimal Coprime

https://codeforces.com/contest/2063/problem/A

Codeforces Round 1000(Div.2) - A. Minimal Coprime

문제 유형: 수학, 그리디

시간 제한: 1초

메모리 제한: 256MB

 

문제

A segment of positive integers [l,r] is called coprime if l and r are coprime.

A coprime segment [l,r] is called minimal coprime if it does not contain any coprime segment not equal to itself. To better understand this statement, you can refer to the notes.

Given [l,r], a segment of positive integers, find the number of minimal coprime segments contained in [l,r].

∗Two integers a and b are coprime if they share only one positive common divisor. For example, the numbers 2 and 4 are not coprime because they are both divided by 2 and 1, but the numbers 7 and 9 are coprime because their only positive common divisor is 1.

† A segment [l′,r′] is contained in the segment [l,r] if and only if l≤l′≤r′≤r.

 

두 앙의 정수 세그먼트 [l, r]은 l과 r이 서로소인경우 서로소 세그먼트라 한다.

만약 [l, r]사이에 다른 서로소 세그먼트가 없으면 최소 서로소 세그먼트라 한다.

[l, r]범위에서의 최초 서로소 세그먼트의 개수를 구하시오.

 

입력

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). The description of the test cases follows.

The only line of each test case consists of two integers l and r (1≤l≤r≤10^9).

 

첫째 줄에 테스트케이스의 수 t가 주어집니다.

각 테스트 케이스의 첫째 줄에 두 개의 정수 l, r이 주어집니다. (1 <= l <= r <= 10^9)

 

출력

For each test case, output the number of minimal coprime segments contained in [l,r], on a separate line.

각 테스트 케이스별로 [l, r]구간 사이의 최소 서로소 세그먼트의 개수를 구하시오.

 

풀이

최소 서로소 세그먼트를 만드는 건 간단하다. 차가 1인 두 자연수는 항상 서로소이다.

즉, r-l이 답이다.

예외 케이스로는 [1, 1]구간이 있다. 1과 1의 gcd는 1이기 때문에, 이 경우에만 따로 처리해주면 된다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int l, r;
  cin >> l >> r;

  int ans = 0;
  if (l == 1 && r == 1) {
    cout << "1\n";
  } else {
    cout << r - l << "\n";
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}