2017西安交大ACM小学期数论 [更新学号]

发布时间: 2017年6月24日 20:27   最后更新: 2017年7月3日 09:27   时间限制: 3000ms   内存限制: 128M

描述

某知名高校有n个学生，每个学生有一个唯一ID。但这些ID有7位数字，学生总是记不住，于是学校想了一个办法。它们将所有ID对m取模作为学生的新ID。显然，取模后要保证这些ID仍不相同。校长听说参加西安交通大学ACM培训的学生能帮忙解决这个问题，于是他想请你算一算m最小是多少。

输入

仅包含一组数据。
第一行一个正整数n(n<=5000)，表示该校学生个数。
第二行有n个整数，每个整数表示一个学生ID。

输出

一个正整数，表示m最小值。

样例输入1 3 2017703 2017704 2017706 样例输出1 4

我觉得这道题目挺难得，耗了我不少时间。

我们这样考虑，怎样才能算取模之后学号仍然重复呢，也就是说idx%m == idy%m

也就是说m为abs(idx-idy)的因数

所以说

我们用两层for循环，找出两两学号的差，并把它在数组的相应位置打上标记（由于所有的学号都是7位，因此，差一定小于1e7，所以数组最大开到1e7就可以了）

然后我们从n到1e7遍历模数，对于每个模数m，判断它的倍数中有没有被打过标记的，如果有，说明这个模数不可行。（我好菜，就这里想了好久。。。。，我一开始的错误想法是想把两两的差进行质因数分解，这显然是不行的，因为时间复杂度太高了！！！）

这种方案时间复杂度应该是O(1e7 log(1e7))

代码：

#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; int n; LL a[5005]; const int MAXN = 1e7 + 7; int st[MAXN]; int cnt = 0; int main(){cin>>n;for(int i = 0 ;i < n;i++){scanf("%lld",&a[i]);}for(int i = 0;i < n;i++){for(int j = 0;j < n;j++){if(i != j){int d = abs(a[i] - a[j]);st[d] = 1;}}}for(int i = n;i < MAXN;i++){int f = 1;for(int t = i;t < MAXN;t += i){if(st[t]){f = 0;break;}}if(f){cout<<i<<endl;break;}}return 0; }

总结

以上是生活随笔为你收集整理的2017西安交大ACM小学期数论 [更新学号]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。