关键词:
题目描述
农夫约翰有N(1<=N<=5000)头奶牛,每头奶牛都有一个唯一的不同于其它奶牛的编号Si,所有的奶牛都睡在一个有K个厩的谷仓中,厩的编号为0到K-1。每头奶牛都知道自己该睡在哪一个厩中,因为约翰教会了它们做除法,Si MOD K的值就是第i头奶年所睡的厩的编号。
给出一组奶牛的编号,确定最小的K使得没有二头或二头以上的奶牛睡在同一厩中。
输入输出格式
输入格式:
第一行一个正整数N,第2到N+1行每行一个整数表示一头奶牛的编号。
输出格式:
单独一行一个整数表示要求的最小的K,对所有的测试数据这样的K是一定存在的
输入输出样例
5 4 6 9 10 13
8
说明
Si(1<=Si<=1000000)
复习一波数论咯
——————————————————————————
a mod k=b mod k 等价于k|(a-b)
所以问题变成找出 ai-bj 的所有因数 然后就好辣
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int M=1e6; int read(){ int ans=0,f=1,c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘) f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){ans=ans*10+(c-‘0‘); c=getchar();} return ans*f; } int n,f[M+7],id[M]; int main() { n=read(); for(int i=1;i<=n;i++) id[i]=read(); sort(id+1,id+1+n); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) f[id[j]-id[i]]=1; for(int i=M;i>=1;i--) for(int j=i*2;j<=M;j+=i) if(f[j]){f[i]=1; break;} for(int i=1;i<=M;i++) if(!f[i]){printf("%d ",i); return 0;} return 0; }
洛谷p1154奶牛分厩
题目描述农夫约翰有N(1<=N<=5000)头奶牛,每头奶牛都有一个唯一的不同于其它奶牛的编号Si,所有的奶牛都睡在一个有K个厩的谷仓中,厩的编号为0到K-1。每头奶牛都知道自己该睡在哪一个厩中,因为约翰教会... 查看详情
洛谷[p1154]奶牛分厩
类似筛法的思想本题实际上就是反推hash的模数,首先想到枚举k,但显然会超时。$amodk==bmodk<==>k|(a-b)$由同余的定义可以知道所以我们的任务就变成的找到一个整数k使其不是任意一个$a-b$的因子,观察一下数据范围可以发现,... 查看详情
luogup1154奶牛分厩[数论]
题目描述农夫约翰有N(1<=N<=5000)头奶牛,每头奶牛都有一个唯一的不同于其它奶牛的编号Si,所有的奶牛都睡在一个有K个厩的谷仓中,厩的编号为0到K-1。每头奶牛都知道自己该睡在哪一个厩中,因为约翰教会... 查看详情
洛谷p1578奶牛浴场
P1578奶牛浴场题目描述由于John建造了牛场围栏,激起了奶牛的愤怒,奶牛的产奶量急剧减少。为了讨好奶牛,John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯,每头奶牛都必须在牛场中的一个固定的位置产... 查看详情
洛谷p2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为Xi,没有两头... 查看详情
洛谷p2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为Xi,没有两头... 查看详情
[wc2002][洛谷p1578]奶牛浴场
洛谷题解里那个人可真是话多呢。 题目描述由于John建造了牛场围栏,激起了奶牛的愤怒,奶牛的产奶量急剧减少。为了讨好奶牛,John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯,每头奶牛都必须在牛... 查看详情
洛谷p2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为Xi,没... 查看详情
洛谷p2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i头奶牛的坐标为Xi,没... 查看详情
洛谷p1472奶牛家谱cowpedigrees
P1472奶牛家谱CowPedigrees102通过193提交题目提供者该用户不存在标签USACO难度普及+/提高 提交 讨论 题解 最新讨论暂时没有讨论题目描述农民约翰准备购买一群新奶牛。在这个新的奶牛群中,每一个... 查看详情
洛谷p2340奶牛会展
洛谷P2340奶牛会展用下标表示智商,值表示情商 1#include<bits/stdc++.h>2#defineFor(i,j,k)for(inti=j;i<=k;i++)3usingnamespacestd;45constintN=411;6intn,m;7inta[N],b[N],f[800011];89inlineintread()10{11intx=0,f=1 查看详情
洛谷p1535游荡的奶牛(代码片段)
P1535游荡的奶牛题目描述Searchingfortheverybestgrass,thecowsaretravellingaboutthepasturewhichisrepresentedasagridwithNrowsandMcolumns(2<=N<=100;2<=M<=100).KeenobserverFarmerJohnhasrecordedBessie‘spo 查看详情
洛谷1578:[wc2002]奶牛浴场——题解(代码片段)
https://www.luogu.org/problemnew/show/P1578#sub由于John建造了牛场围栏,激起了奶牛的愤怒,奶牛的产奶量急剧减少。为了讨好奶牛,John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯,每头奶牛都必须在牛场中的一个... 查看详情
洛谷p2345奶牛集会
洛谷P2345奶牛集会树状数组按v从小到大排序消除max影响 1#include<bits/stdc++.h>2#defineFor(i,j,k)for(inti=j;i<=k;i++)3#defineDow(i,j,k)for(inti=j;i>=k;i--)4#defineLLlonglong5usingnamespacestd;6inlineintread( 查看详情
洛谷p1868饥饿的奶牛
P1868饥饿的奶牛题目描述有一条奶牛冲出了围栏,来到了一处圣地(对于奶牛来说),上面用牛语写着一段文字。现用汉语翻译为:有N个区间,每个区间x,y表示提供的x~y共y-x+1堆优质牧草。你可以选择任意区间但不能有重复的... 查看详情
动态规划洛谷p1868饥饿的奶牛
P1868饥饿的奶牛题目描述有一条奶牛冲出了围栏,来到了一处圣地(对于奶牛来说),上面用牛语写着一段文字。现用汉语翻译为:有N个区间,每个区间x,y表示提供的x~y共y-x+1堆优质牧草。你可以选择任意区间但不能有重复的... 查看详情
洛谷p1842奶牛玩杂技
洛谷P1842奶牛玩杂技贪心做法很经典比较相邻两个而且这个式子更简单Sx-wy>=Sy-Wx(x放下面更优)移项之后排序直接弄就好1#include<cstdio>2#include<algorithm>3#defineFor(i,j,k)for(inti=j;i<=k;i++)4#defineDow(i,j,k)for(inti=j;i>=k;i--)5 查看详情
洛谷p2868[usaco07dec]观光奶牛sightseeingcows
P2868[USACO07DEC]观光奶牛SightseeingCows题目描述FarmerJohnhasdecidedtorewardhiscowsfortheirhardworkbytakingthemonatourofthebigcity!Thecowsmustdecidehowbesttospendtheirfreetime.Fortunately,theyhaveadetailedcit 查看详情