poj2769之寻找最小完全剩余系

2019-04-14 12:00发布

站内文章 / 模拟电子
11493 0 1380
题目解析：该题所求即为寻找到最小的数 m 满足 m 模G个数两两不同余，即为找到最小的 m 使得这些数在 m 的最小完全剩余系中。 #include #include #include using namespace std; #define LENN 1000010 #define LENV 100001 int num[LENN], vis[LENV]; int main(int argc, char **argv) { int T, n, m, i, j, mark; cin >> T; while( T-- ) { cin >> n; for(i=1; i<=n; i++) cin >> num[i]; for(i=n; ; i++)//从 n 开始寻找这 n 个数的最小完全剩余系 { mark=1;//如果找到了就退出循环，用 mark 标记是否找到 memset(vis, 0, sizeof(vis)); for(j=1; j<=n; j++) { if( vis[ num[j]%i ] )//如果后面有与前面同余的则满足条件进入这个语句 { mark=0;//标记为 0 就是有两个数同余，则在后面不会跳出循环 break; } vis[ num[j]%i ]=1; } if( mark ) break;//如果没有两个是同余的数，则这是最小完全剩余系，这个数找到了 } cout << i << endl; } return 0; }

热门文章