1604-D, *1600

Problem - D - Codeforces

문제

• 두 양의 짝수 $x,\ y(2 \leq x,\ y \leq 10^{9})$가 주어진다
• $n \text{ mod } x = y \text{ mod } n$을 만족하는 $n(1\leq n \leq 2\cdot 10^{18})$을 출력하라

 

$O(1)$

제약이 더 많이 생기면 조건이 더 명확해지므로 x, y 의 크기로 경우를 나누어 풀었다
i) x = y 인 경우
n = x 이면 성립한다

ii) x > y 인 경우
잘 모르겠어서 작은 입력에 대한 결과를 출력해봤다

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    for(int y = 2; y <= 100; y += 2){
        for(int x = y; x <= 100; x += 2){
            loop(n, 100){
                if(n%x == y%n){
                    cout << x << ' ' << y << ' ' << n << endl;
                    break;
                }
            }
        }
    }
 
    return 0;
}cs

x y n
2 2 2
4 2 6
6 2 8
8 2 10
10 2 12
12 2 14
14 2 16
16 2 18
18 2 20
20 2 22

 

n = x + y 이라는 규칙성이 보인다

Claim
If x > y and n = x + y, then n (mod x) = y (mod n)

∵
(좌변) : x + y (mod x) = y (mod x) = y (∵ x > y)
(우변) : y (mod x+y) = y  (∵ x+y > y)  □

 

iii) x < y 인 경우

잘 모르겠어서 작은 입력에 대한 결과를 출력해봤다

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    for(int x = 2; x <= 100; x += 2){
        for(int y = x; y <= 100; y += 2){
            loop(n, 100){
                if(n%x == y%n){
                    cout << x << ' ' << y << ' ' << n << endl;
                    break;
                }
            }
        }
    }
 
    return 0;
}cs

2 2 2
2 4 2
2 6 2
2 8 2
2 10 2
2 12 2
(중략)
4 4 4
4 6 5
4 8 4
4 10 7
4 12 4
4 14 6
4 16 4
4 18 15

※ 실은 실제 시험에서는 몇 가지 테스트 케이스로 x < y 인 경우 n = (x+y)/2 라고 결론냈었다!!
그러나 이 해답은 아주 특이한 경우(x < y < 3x)에만 해당하는 해답이다. 귀납적으로 결론을 내지 말것.

 

몇 가지 규칙을 찾고 맞는지 확인하자

Claim 1
If $x\mid y$ and n = x, then n (mod x) = y (mod n)

∵
(좌변) : x (mod x) = 0
(우변) : y (mod x) = 0(∵ $x\mid y$) □

 

Claim 2
if x < y < 3x and n = (x+y)/2, then n (mod x) = y (mod n)

∵
Let 어떤 양의 짝수 k 가 존재하여 y = x + k 라고 하자

$\begin{aligned} n(\text{mod }x)&=\frac{x+y}{2} (\text{mod }x)\\ &=\frac{x+x+k}{2} (\text{mod }x)\\ &=x+\frac{k}{2} (\text{mod }x)\\ &=\frac{k}{2} (\because \frac{k}{2}=\frac{y-x}{2}<\frac{3x-x}{2}=x) \end{aligned}$

$\begin{aligned} y(\text{mod }n)&=\frac{y+y}{2}(\text{mod }\frac{x+y}{2})\\ &=\frac{y+(x+k)}{2}(\text{mod }\frac{x+y}{2})(\because y = x +k)\\ &=\frac{x+y}{2}+\frac{k}{2}(\text{mod }\frac{x+y}{2})\\ &=\frac{k}{2}(\because \frac{k}{2}=\frac{y-x}{2}<\frac{x+y}{2}) \end{aligned}$

따라서 (좌변) = (우변) =k/2  □

 

패턴은 더 이상 찾기 어렵다. 이제 남은부분은 추론을 통하여 구하도록 하자
일부분은 패턴을 찾아 해결하였으니 남은부분에 대해서는 제약조건을 더 걸 수 있다.

 

Claim 3
If 3x < y and $x \nmid y$ and $n = y - \frac{y \text{ mod }x}{2}$,
then n (mod x) = y (mod n)

 ∵

Division algorithm 에 의해
$y=xq+r,\ 0\leq r < x$
인 정수 q와 r 이 유일하게 존재한다

n 을 xq 와 y 의 평균값 즉,
$$\frac{y+xq}{2}=\frac{y+y-r}{2}=y-\frac{y(\text{mod } x)}{2}$$
으로 잡으면
$\begin{aligned} n(\text{mod } x)&=\frac{y+xq}{2}(\text{mod } x)\\ &=\frac{xq+r+xq}{2}(\text{mod } x)\\ &=xq+\frac{r}{2}(\text{mod } x)\\ &=\frac{r}{2}(\because \frac{r}{2}<\frac{x}{2}<x) \end{aligned}$

$\begin{aligned} y(\text{mod } n)&=y(\text{mod } \frac{y+xq}{2})\\ &=\frac{y+y}{2}(\text{mod } \frac{y+xq}{2})\\ &=\frac{y+xq+r}{2}(\text{mod } \frac{y+xq}{2})\\ &=(\frac{y+xq}{2}+\frac{r}{2})(\text{mod } \frac{y+xq}{2})\\ &=\frac{r}{2}(\because 3x<y \text{ i.e. } 0<3x< xq \text{ and }\frac{r}{2}=\frac{y-xq}{2}<\frac{y+xq}{2}) \end{aligned}$

따라서 (좌변)=(우변)=r/2 □

c++

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    ll x, y;
    while(t--){
        cin >> x >> y;
        if(y%x == 0) cout << x << endl;
        else if(x > y) cout << (x+y) << endl;
        else{
            if(y < 3*x) cout << (x+y)/2 << endl;
            else cout << y-(y%x)/2 << endl;
        }
    }
 
    return 0;
}cs

python 3

import sys
 
for _ in range(int(input())):
    x, y = map(int, sys.stdin.readline().split())
    if x == y: print(x)
    elif x > y: print(x+y)
    else: print(int(y-y%x/2))cs

x < y 일 때 n = y - (y%x)/2 이면 된다(c++ 에서는 경우를 나눴는데 굳이 그럴 필요없다. 증명은 생략)