一道数论题 - 科创网

论坛>计算机科学>软件综合

文号t33864

8203

一道数论题

ltc2011/05/26软件综合 IP:浙江

输入n个正整数，每个数均不超过1000000
求最小的数m使这n个数模m的余数均不相等

来自：计算机科学 / 软件综合

~~空空如也

ltl

14年1个月前 IP:未同步

296783

1楼

n有多大？？？

引用

加载评论中，请稍候...

200字以内，仅用于支线交流，主线讨论请采用回复功能。

折叠评论

ltc

作者

14年1个月前 IP:未同步

296787

2楼

补充n≤4000

引用

加载评论中，请稍候...

200字以内，仅用于支线交流，主线讨论请采用回复功能。

折叠评论

ltc

作者

14年1个月前 IP:未同步

296799

3楼

说一下我的想法（不一定对）
两两求差

引用

加载评论中，请稍候...

200字以内，仅用于支线交流，主线讨论请采用回复功能。

折叠评论

rjsp

14年1个月前 IP:未同步

297044

4楼

引用第3楼ltc于2011-05-26 21:22发表的 :
说一下我的想法（不一定对）
两两求差

两两求差是有道理的，
a 和 b 是两个不相等的数，要求 a%m != b%m
设 b = a + T，则 a%m != b%m 变为
a%m != (a+T)%m
再变为
a%m != ( a%m + T%m )%m
即 T%m 不能为零
即 m 不能是 a和b差值的约数

// 算法，用筛选法
a. 在[1,最大元素]的区间上，置初值为0
b. 两两求差，将差所在的位置值置1
c. from 2 to 元素中的最大值 step 1，跳着走，如果中途碰到了1，则将其踩过的点（包括之后要踩的点）都置1
d. 在区间上从左到右搜索一个值为0的点

引用

加载评论中，请稍候...

200字以内，仅用于支线交流，主线讨论请采用回复功能。

折叠评论

rjsp

14年1个月前 IP:未同步

297046

5楼

上面描述得有错误，因为当时急着去撒尿
我做个事例，比如 5 10 12 13 四个数
第一步，求出两两差值，分别是 1 2 3 5 7 8

第二步，作一个数组，下标从4开始，到8结束。因为m不可能小于n，所以从n开始；如果m大于等于最大的哪个数，必然是可以的，所以到最大值结束。
将差所在位置置1。即
位置： 4 5 6 7 8
数值： 0 1 0 1 1

第三步，
从4开始，检测 buf[4]，buf[8]，buf[12]，…… 上是否有1，如果有，则失败 // 我这里数组比较小，只到buf[8]就行了
从5开始，检测 buf[5]，buf[10]，buf[15]，…… 上是否有1，如果有，则失败
从6开始，检测 buf[6]，buf[12]，buf[18]，…… 上是否有1，如果没有，则good，就是它了

引用

加载评论中，请稍候...

200字以内，仅用于支线交流，主线讨论请采用回复功能。

折叠评论

rjsp

14年1个月前 IP:未同步

297051

6楼

引用

加载评论中，请稍候...

200字以内，仅用于支线交流，主线讨论请采用回复功能。

折叠评论

想参与大家的讨论？现在就登录或者注册。

所属专业

软件综合

上级专业

计算机科学

同级专业

计算机电子学

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

200字以内，仅用于支线交流，主线讨论请采用回复功能。

请选择违规类型：

空空如也