-
1604-D, *1600코드포스 2021. 10. 31. 21:30
문제
- 두 양의 짝수 $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 인 경우
잘 모르겠어서 작은 입력에 대한 결과를 출력해봤다12345678910111213141516171819202122232425262728#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;}csx 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 22n = 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 인 경우
잘 모르겠어서 작은 입력에 대한 결과를 출력해봤다
12345678910111213141516171819202122232425262728#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;}cs2 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++
123456789101112131415161718192021222324252627282930#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;}cspython 3
1234567import sysfor _ in range(int(input())):x, y = map(int, sys.stdin.readline().split())if x == y: print(x)elif x > y: print(x+y)x < y 일 때 n = y - (y%x)/2 이면 된다(c++ 에서는 경우를 나눴는데 굳이 그럴 필요없다. 증명은 생략)
'코드포스' 카테고리의 다른 글
1604-B, *1100 (0) 2021.11.01 1604-C, *1300 (0) 2021.11.01 1283-C, *1500 (0) 2021.09.17 1283-D, *1800 (0) 2021.09.16 1560-A, *800 (0) 2021.08.30