首页   注册   登录
 liyunlong41 最近的时间轴更新
liyunlong41

liyunlong41

V2EX 第 375477 号会员,加入于 2019-01-05 21:27:49 +08:00
liyunlong41 最近回复了
270 天前
回复了 hakono 创建的主题 问与答 请教一道某公司的(简单?)算法题?
@liyunlong41 代码格式乱了,不太会搞,贴在网页上吧: https://github.com/hackssssss/test_git/blob/master/rc.go
270 天前
回复了 hakono 创建的主题 问与答 请教一道某公司的(简单?)算法题?
花时间用 golang 写了下程序,1e18 的样例已经能正确跑出结果,999656834379155073,用的是容斥原理,枚举数组所有子集,看子集个数,奇数个就减,偶数个就加。秒出结果,被乘法溢出搞了好久…… 代码凑活着看。
`
func gcd(x, y int64) int64 { //辗转相除法
tmp := x % y
if tmp > 0 {
return gcd(y, tmp)
}
return y
}
func lcm(x, y int64) int64 {
return x / gcd(x, y) * y //计算 lcm 的小技巧,先除 gcd,再乘另一个数,有效防止溢出
}
func main() {
var (
n = int64(1000000000000000000)
i = uint(1)
j = uint(0)
nums = []int{29516, 34882, 63315, 28983, 7176, 96533, 33422, 84834, 43803, 61310}
len = uint(len(nums))
)
sum := int64(0)
for i = 0; i < (1 << len); i++ {
count := 0
curLcm := int64(1)
ok := true
for j = 0; j < len; j++ {
if (i & (1 << j)) > 0 {
count++
tmp := curLcm
curLcm = lcm(int64(nums[j]), curLcm)
//这里判断乘法溢出!!被卡了好久
if curLcm > n || curLcm < tmp || curLcm % tmp != 0 || curLcm % int64(nums[j]) != 0 {
ok = false
break
}
}
}
if !ok {
continue
}
if count%2 == 1 {
sum -= n / curLcm
} else {
sum += n / curLcm
}
}
fmt.Println(sum)
}

`
270 天前
回复了 hakono 创建的主题 问与答 请教一道某公司的(简单?)算法题?
这题感觉是典型的容斥啊。
假设给定四个数 和总数 n。
容斥原理计算四个数的倍数在 n 范围内的数量 m=sum(n/单个数)-sum(n/任意两数公倍数+sum(n/任意三数公倍数)-sum(n/四个数的公倍数)
最终结果就是 n-m
286 天前
回复了 xh520630 创建的主题 问与答 [遇事不决] 老东家喊回去上班怎么抉择
假如你在当前公司提离职,公司又给你涨薪了呢
关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2089 人在线   最高记录 5168   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.3 · 16ms · UTC 11:22 · PVG 19:22 · LAX 03:22 · JFK 06:22
♥ Do have faith in what you're doing.