15天大厂真题带刷 - ZT2小美的因子查询 | Go
小美的因子查询
https://www.nowcoder.com/practice/1870e68256794c6aa727c8bb71fd9737
题意
1e5次询问，每次循环都需要判断输入的数x是否至少存在一个偶数因子
其中x<=1e9
思路
最朴素的思想，对于每一个输入的数x，都从2开始，每次累加2，判断当前遍历到的偶数是否为x的因子。
但是1e5*sqrt(1e9)的时间复杂度有点逆天
考虑一个性质就是，偶数肯定能被2整除，所以如果一个数有偶数因子，这个数一定可以被2整除，问题转化为x能否被2整除
Go代码
%2 也可以用&1来判断 但是位运算也没有更快
package main
import (
"fmt"
)
func main() {
var T,x int
fmt.Scan(&T)
for i := 0; i < T; i ++{
fmt.Scan(&x)
if x % 2 == 0 {
fmt.Println("YES")
}else{
fmt.Println("NO")
}
}
}
#牛客创作赏金赛#15天大厂真题带刷Go题解 文章被收录于专栏
15天大厂真题带刷Golang题解
投递快手等公司8个岗位 >
查看9道真题和解析
汤臣倍健开奖53人在聊