首页 > 代码库 > luoguP1154 奶牛分厩 [数论]

luoguP1154 奶牛分厩 [数论]

2024-11-14 14:03:39   202人阅读

题目描述

农夫约翰有Ｎ（1<=Ｎ<=5000）头奶牛，每头奶牛都有一个唯一的不同于其它奶牛的编号Ｓi，所有的奶牛都睡在一个有Ｋ个厩的谷仓中，厩的编号为０到Ｋ－１。每头奶牛都知道自己该睡在哪一个厩中，因为约翰教会了它们做除法，Ｓi MOD Ｋ的值就是第i头奶年所睡的厩的编号。

给出一组奶牛的编号，确定最小的Ｋ使得没有二头或二头以上的奶牛睡在同一厩中。

输入输出格式

输入格式：

第一行一个正整数Ｎ，第2到Ｎ＋１行每行一个整数表示一头奶牛的编号。

输出格式：

单独一行一个整数表示要求的最小的Ｋ，对所有的测试数据这样的Ｋ是一定存在的

输入输出样例

输入样例#1：
5 4 6 9 10 13
输出样例#1：
8

说明

Si(1<=Si<=1000000)

 

O(n2+mlogm)解法

很多错误解法也能过？

 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 #define dbg(x) cout<<#x<<" = "<<x<<endl 8  9 const int maxn=5005,maxsize=1000005;10 11 int n,ans=0;12 int s[maxn],a[maxsize],siz=0;13 14 int main(){15     scanf("%d",&n);16     for(int i=1;i<=n;i++)  scanf("%d",&s[i]);17     for(int i=1;i<n;i++)18         for(int j=i+1;j<=n;j++){19             a[abs(s[i]-s[j])]=1;20             siz=max(siz,abs(s[i]-s[j]));21         }22 //    dbg(siz);23     for(int i=1;i<siz;i++){24         if(a[i])  continue;25         bool flag=0;26         for(int p=(i<<1);p<=siz;p+=i)27             if(a[p]){  flag=1;  break;  }28         if(!flag){  ans=i;  break;  }29     }30     if(ans==0)  ans=siz+1;31     printf("%d\n",ans);32     return 0;33 }

 

luoguP1154 奶牛分厩 [数论]


联系
我们