Algorithm

A. Odd Divisor
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/problemset/problem/1475/A
input
standard input
output
standard output

You are given an integer n�. Check if n� has an odd divisor, greater than one (does there exist such a number x� (x>1�>1) that n� is divisible by x� and x� is odd).

For example, if n=6�=6, then there is x=3�=3. If n=4�=4, then such a number does not exist.

Input

The first line contains one integer t� (1≤t≤1041≤�≤104) — the number of test cases. Then t� test cases follow.

Each test case contains one integer n� (2≤n≤10142≤�≤1014).

Please note, that the input for some test cases won't fit into 3232-bit integer type, so you should use at least 6464-bit integer type in your programming language.

Output

For each test case, output on a separate line:

  • "YES" if n� has an odd divisor, greater than one;
  • "NO" otherwise.

You can output "YES" and "NO" in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

Example
input
Copy
6
2
3
4
5
998244353
1099511627776
output
Copy
NO
YES
NO
YES
YES
NO

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;


#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll t;
  cin>>t;
  while(t--){
    ll n;
    cin>>n;
    while(n != 1){
      if(n % 2 == 0){
        n /= 2;
      }
      else{
        cout<<"YES"<<endl;
        break;
      }
    }
    if(n == 1){
      cout<<"NO"<<endl;
    }

  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
6
2
3
4
5
998244353
1099511627776

Output

x
–
+
cmd
NO
YES
NO
YES
YES
NO
Advertisements

Demonstration

Codeforcess Solution  1475-A A. Odd Divisor ,C++, Java, Js and Python,1475-A,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+