Codeforces Round 697 A 题解

Odd Divisor

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$) that $n$ is divisible by $x$ and $x$ is odd).

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

Input

The first line contains one integer $t$ ($1≤t≤10^4$) — the number of test cases. Then $t$ test cases follow.

Each test case contains one integer $n$ ($2≤n≤10^{14}$).

Please note, that the input for some test cases won’t fit into $32$-bit integer type, so you should use at least $64$-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

6
2
3
4
5
998244353
1099511627776

output

NO
YES
NO
YES
YES
NO

题目大意

对于给定的数 $n$ ，判断该数是否存在包含大于 $1$ 的奇因子，有则输出 YES ，无则输出 NO 。

分析

根据题目要求最大的 $n$ 最大可能到 $10^{14}$ ，因此需要使用 long long 来存储。那么思路就是每次去判断它是否为奇数，如果是就直接输出 YES ，如果不是就除以 $2$ 然后再判断直到除到 $1$ 就输出 NO 。

AC代码

#include <stdio.h>
typedef long long ll;
int main() {
  ll t, n;
  scanf("%lld", &t);
  for(int i=0; i<t; ++i) {
    scanf("%lld", &n);
    bool flag = false;
    while(n > 1) {
      if(n % 2 != 0) {
        printf("YES\n");
        flag = true;
        break;
      }
      n /= 2;
    }
    if(!flag) printf("NO\n");
  }
  return 0;
}