Problem
Mr. Chef has been given a number N. He has a tendency to double whatever he get. So now he has got the number N with him and he has multiplied the number N by 2. Now Chef is superstitious. He believes in something known as Lucky Number. His lucky number is defined as any number, which when multiplied by 2 has no other factors other than 1,2, and N. If the number is lucky all you have to do is print “LUCKY NUMBER”. If the number is not a lucky number, print “Sorry”..
Input
The first line consists of T, which is the number of test cases. Every line of the next T lines consists of N.
Output
Print LUCKY NUMBER if the number is lucky and “Sorry” if the number is not lucky followed by a new line.
Constraints
1<=T<=1000
1<=N<=1000000
Input
3
26
12
11
Output:
Sorry
Sorry
LUCKY NUMBER
Solution
非常简单的题目, 所谓的Lucky Number就是判定n是不是素数, 同时是否是2的幂.
在判断素数部分, 使用了Sieve of Eratosthenes算法, 可以大幅度降低时间复杂度.
在判断是否为2的幂方面, 使用了bitwise操作.
Golang解法
package main
import (
"fmt"
"math"
)
var ns []int64
var UpperboundArray []bool
var upperbound, i, j, k int64
func is_pow_of_two(n int64) bool {
return (n&(n-1) != 0)
}
func generate_prime_number_table(n int64) {
upperbound = int64(math.Sqrt(float64(n)))
UpperboundArray = make([]bool, n+1)
for i = 2; i <= upperbound; i++ {
if !UpperboundArray[i] {
for k = i * i; k <= n; k += i {
UpperboundArray[k] = true
}
}
}
}
func is_prime_number(n int64) bool {
return !UpperboundArray[n]
}
func is_lucky_number(n int64) bool {
if n < 1 || n > 1000000 {
return false
}
return is_pow_of_two(n) || is_prime_number(n)
}
func main() {
var testcases, n int64
fmt.Scanln(&testcases)
ns = make([]int64, testcases)
n = 0
for i = 0; i < testcases; i++ {
fmt.Scanln(&ns[i])
if n < ns[i] {
n = ns[i]
}
}
generate_prime_number_table(n)
for i = 0; i < testcases; i++ {
if is_lucky_number(ns[i]) {
fmt.Println("LUCKY NUMBER")
} else {
fmt.Println("Sorry")
}
}
}