Bài C - Codeforces Global Round 1

Bài C:
Đề bài: Ước chung lớn nhất và các thao tác bitwise có điểm nào chung ? Đã đến lúc trả lời câu hỏi này.
Giả sử bạn được cho một số nguyên a. Bạn muốn chọn một số nguyên b nào đó từ 1 đến a-1 bằng một cách nào đó sao cho ước chung lớn nhất của a^b và a&b lớn nhất có thể. Hay nói cách khác, bạn muốn tính hàm sau: $f(a)=max_{0<b<a} gcd(a^b,a&b)$.
Ở đây ^ kí hiệu là thao tác XOR và & kí hiệu thao tác AND.
Bạn được cho q số nguyên a(1),a(2),...,a(q). Với mỗi số nguyên này, tính giá trị lớn nhất có thể của ước chung lớn nhất (khi b được chọn một cách tối ưu).
Đầu vào:
+ Dòng đầu tiên chứa 1 số nguyên q (1<=q<=10^3) - số các số nguyên bạn cần tính cho câu trả lời.
+ Sau đó là $q$ số nguyên được cho, mỗi số một dòng: a(1),a(2),...,a(q) (2<=a(i)<=2^(25)-1) - các số nguyên mà bạn cần tính.
Đầu ra:
Với mỗi số nguyên, in ra câu trả lời theo thứ tự với các số đã được cho trong input.
Ví dụ:
Đầu vào:
3
2
3
5
Đầu ra:
3
1
7
Chú thích:
Với số nguyên đầu tiên, ta chọn b=1, thì a^b=3,a&b=0, và ước chung lớn nhất của 3 và 0 là 3.
Với số nguyên thứ hai, ta chọn b=2, thì a^b=1, a&b=2 và ước chung lớn nhất của 1 và 2 là 1.
Với số nguyên thứ ba, ta chọn b=2, thì a^b=7, a&b=0, và ước chung lớn nhất của 7 và 0 là 7.
Lời giải:
Kí hiệu bit  cao nhất của a là x (có nghĩa là số nguyên x lớn nhất thỏa mãn 2^x<=a), ta xét b=(2^x-1) XOR a. Dễ dàng ta thấy rằng nếu a#2^x-1 thì 0<b<a xảy ra. Vì vậy, ước chung lớn nhất là có thể vì a&b=0 và gcd(2^x-1,0)=2^x-1.
 Bây giờ, ta đi xét trường hợp khi a=2^x-1. Điều này dẫn đến gcd(a^b,a&b)=gcd(2^x-1-b,b)=gcd(2^x-1,b), do gcd(x,x+y)=gcd(x,y) (với mọi x và y), vì vậy nó đủ để tìm ước lớn nhất không tầm thường của a - và ta sẽ có câu trả lời như mong muốn.
 Tìm ước chung lớn nhất có thể được thực hiện O(q.can(m)) hoặc có thể tính câu trả lời cho tất cả a=2^x-1 trước đó.
Lời giải:

#include <bits/stdc++.h>
using namespace std;
int q,n;
int main()
{
    cin>>q;
    while(q--)
 {
        cin>>n;
        int c=1;
        while(c<=n)
  {
   c<<=1;
  }
        if(n!=c-1)
  {
   cout<<c-1<<endl;
  }
        else
  {
            bool flag=false;
            for(int i=2;i*i<=n;i++)
            {
                if(n%i==0)
    {
     cout<<n/i<<endl;
     flag=true;
     break;
    }
   }
            if(!flag)
            {
             cout<<"1"<<endl;
            }
        } 
    }
}