C - Reduced ID Numbers 寒假训练

时间:2022-05-15 06:10:05
T. Chur teaches various groups of students at university U. Every U-student has a unique Student Identification Number (SIN). A SIN s is an integer in the range 0 ≤ s ≤ MaxSIN with MaxSIN = 10 6-1. T. Chur finds this range of SINs too large for identification within her groups. For each group, she wants to find the smallest positive integer m, such that within the group all SINs reduced modulo m are unique.

Input

On the first line of the input is a single positive integer N, telling the number of test cases (groups) to follow. Each case starts with one line containing the integer G (1 ≤ G ≤ 300): the number of students in the group. The following G lines each contain one SIN. The SINs within a group are distinct, though not necessarily sorted.

Output

For each test case, output one line containing the smallest modulus m, such that all SINs reduced modulo m are distinct.

Sample Input

2
1
124866
3
124866
111111
987651

Sample Output

1
8 该题,整体思路有,不过会觉得肯定会超时,结果也超时了,后来搜了题解,有一个小小的技巧
就是memset的时候,不整体memset,而是从0到i+1,因为下一层循环对i取得膜,所以vis里面改变的下标都<=i!!!!!十分重要,不这样就会超时!!!
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
const int maxn=1e6+10;
bool vis[maxn];
int a[500];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int g;
scanf("%d",&g);
for(int i=0;i<g;i++) scanf("%d",&a[i]); if(g==1) printf("1\n");
else
{
int i;
for(i=2;;i++)
{
memset(vis,0,sizeof(bool)*(i+1));//!!!!
bool flag=0;
for(int j=0;j<g;j++)
{
if(vis[a[j]%i]){flag=1;break;}
else vis[a[j]%i]=1;
}
if(flag==0) break;
}
printf("%d\n",i);
}
}
}

  

														
		

C - Reduced ID Numbers 寒假训练的更多相关文章

  1. G - Reduced ID Numbers(第二季水)

    Description T. Chur teaches various groups of students at university U. Every U-student has a unique ...

  2. poj 2769 Reduced ID Numbers(memset使用技巧)

    Description T. Chur teaches various groups of students at university U. Every U-student has a unique ...

  3. poj 2769 Reduced ID Numbers 同余定理

    链接:http://poj.org/problem?id=2769 题意:寻找数m,是的对于n个数的余数不同 思路:暴力,优化:同余部分不用测试 代码: #include <iostream&g ...

  4. scau 2015寒假训练

    并不是很正规的.每个人自愿参与自愿退出,马哥找题(马哥超nice么么哒). 放假第一周与放假结束前一周 2015-01-26 http://acm.hust.edu.cn/vjudge/contest ...

  5. 寒假训练——搜索——C - Robot

    The Robot Moving Institute is using a robot in their local store to transport different items. Of co ...

  6. 寒假训练——搜索 G - Xor-Paths

    There is a rectangular grid of size n×mn×m . Each cell has a number written on it; the number on the ...

  7. 寒假训练——搜索 E - Bloxorz I

    Little Tom loves playing games. One day he downloads a little computer game called 'Bloxorz' which m ...

  8. 寒假训练 A - A Knight&&num;39&semi;s Journey 搜索

    Background The knight is getting bored of seeing the same black and white squares again and again an ...

  9. FZU ICPC 2020 寒假训练 4 —— 模拟&lpar;一)

    P1042 乒乓球 题目背景 国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革,以推动乒乓球运动在全球的普及.其中11分制改革引起了很大的争议,有一部分球员因为无法适应新规则只能选择退役.华华 ...

随机推荐

  1. CGLIB学习笔记

    0 概述 CGLIB基于ASM实现.提供比反射更为强大的动态特性.使用CGLIB可以非常方便的实现的动态代理. 0.1 CGLIB包结构 net.sf.cglib.core    底层字节码处理类. ...

  2. poj3469 最小割构图

    题目链接:http://poj.org/problem?id=3469 #include <cstdio> #include <cmath> #include <algo ...

  3. Mac 使用ab命令进行压测

    Mac 使用ab命令进行压测 1.在Mac中配置Apache Mac中应该有自带了Apache,详细配置见http://www.cnblogs.com/snandy/archive/2012/11/1 ...

  4. shullfe机制详解

    一.shuffle机制概述 shuffle机制就是发生在MR程序中,Mapper之后,Reducer之前的一系列分区排序的操作.shuffle的作用是为了保证Reducer收到的数据都是按键排序的. ...

  5. Java 基础 多线程进阶(锁,线程安全)

    一,前言 前面我们已经对线程和线程池有一定的了解,但是只要说到多线程,肯定需要考虑线程安全等问题.接下来我们就来好好聊聊这些问题. 二,线程安全 如果有多个线程在同时运行,而这些线程可能会同时运行这段 ...

  6. c&num;处理json数据最好的方式,没有之一。

    c#处理json数据最好的方式,没有之一. 引用Json.Net(需要.NET 4.5及以上版本) using Newtonsoft.Json.Linq; 使用非常简单 JObject result ...

  7. Maven工程打成一个jar包

    1:maven-shade-plugin 插件 <plugin> <groupId>org.apache.maven.plugins</groupId> <a ...

  8. 基于AngularJs &plus; Bootstrap &plus; AngularStrap 省市区联动实践

    什么是 AngularJs?网上一大堆资料,没能真正说明白. AngularJs 就是一个函数库,算不上一个框架,源码2万2千多行,提供了前端MVC的开发方式, 有双向绑定,指令等特性,这是具有革命性 ...

  9. 在Oracle中查看客户端连接的IP信息 &period;

    大家都知道在v$session 中记录着客户端的机器名称,但是没有IP , 如果记录clinet ip 呢? con sys/sys as dba 1. 利用triger 这里不介绍. 2. 利用 D ...

  10. selenium googleDrive

    http://chromedriver.storage.googleapis.com/index.html?path=2.1/下载地址 把googledriver.exe 放到google浏览器下目录 ...