Meaningless Operations
https://codeforces.com/contest/1110/problem/C
考え方
題意
\( f(b) = gcd(a \ \mathrm{XOR} \ b,\ a\ \mathrm{AND} \ b) \ (0 < b < a)\) の最大値を答えます。
方針
解説を読みました。
\( a \leq 2^x – 1\) を満たす最小の \( x \) とします。
\( a \neq 2^x – 1\) のとき
\( b = (2^x – 1) \ \mathrm{XOR} \ a \) は最上位のビットが \( 0 \) であるので、\( a \) より小さいことが言えます。
このとき、\( a \ \mathrm{XOR} \ b = 2^x – 1\)、\( a \ \mathrm{AND} \ b = 0\) なので、\( 2^x – 1\) が最大値となります。
\( a = 2^x – 1\) のとき
\( a \ \mathrm{XOR} \ b = a – b \) 、\( a \ \mathrm{AND} \ b = b \) となります。
\( gcd(x, x + y) = gcd(x, y)\) が成り立つので、\(gcd(a – b, b) = gcd(a, b) \) となります。なので、\( a \) の \(a \) 未満の約数の最大値が答えとなります。
コード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
import java.util.Arrays; import java.util.Scanner; public class ProblemC { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int q = sc.nextInt(); int[] a = new int[q]; for(int i = 0; i < q; i++) { a[i] = sc.nextInt(); } sc.close(); int[] b = new int[25]; b[0] = 2; for(int i = 1; i < 25; i++) { b[i] = 2 * b[i - 1]; } for(int i = 0; i < 25; i++) { b[i] -= 1; } int[] c = new int[25]; Arrays.fill(c, 1); for(int i = 0; i < 25; i++) { for(int j = 2; j * j <= b[i]; j++) { if(b[i] % j == 0) { c[i] = b[i] / j; break; } } } for(int i = 0; i < q; i++) { for(int j = 0; j < 25; j++) { if(a[i] == b[j]) { System.out.println(c[j]); break; }else if(a[i] < b[j]) { System.out.println(b[j]); break; } } } } } |
感想
最大値を取る証明ができていないので、良く分かりませんでした。