CF1110C Meaningless Operations

思路：

令x为满足2^x<= a的最大的x。如果a的二进制表示中包含0，则将b构造为(2^x+1 - 1) ^ a即可；否则gcd(a ^ b, a & b) = gcd(2^x+1 - 1 - b, b) = gcd(2^x+1 - 1, b)，要令此式最大，b应为(2^x+1 - 1)的最大非平凡因子。

实现：

 #include <bits/stdc++.h>

 using namespace std;

 inline int max_fac(int x)

 {

     for (int i = ; i * i <= x; i++)

     {

         if (x % i == ) return x / i;

     }

     return ;

 }

 int main()

 {

     int q, x;

     set<int> st;

     for (int i = ; i <= ; i++) st.insert(( << i) - );

     while (cin >> q)

     {

         for (int i = ; i < q; i++)

         {

             cin >> x;

             if (st.count(x))

             {

                 cout << max_fac(x) << endl;

             }

             else

             {

                 int tmp = , y = x;

                 while (y) { y >>= ; tmp++; }

                 cout << ( << tmp) -  << endl;

             }

         }

     }

     return ;

 }

巴特西

CF1110C Meaningless Operations

最新文章

热门文章