关键词：
51nod 1616 最小集合
题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1616
题目大意：若$a$和$b$均在集合$S$中，则$gcd(a,b)$也在$S$中。现给出$S$中$n$个元素，问$|S|$的最小值.
数论
定义$f(k)$为这$n$个数中能被$k$整除的数的个数.
对任意一个数$x$，设其倍数构成的集合为$D$，令$d=gcd(D)$，则显然有$f(x)=f(d)=|D|$
代码如下：
1 #include <iostream> 2 using namespace std; 3 int n,ans,t,vis[1000005],f[1000005],tmp[1000005]; 4 int main(void){ 5 std::ios::sync_with_stdio(false); 6 cin>>n; 7 for(int i=0;i<n;++i){cin>>t;vis[t]=1;} 8 for(int i=1;i<=1000000;++i) 9 for(int j=1;i*j<=1000000;++j) 10 if(vis[i*j])f[i]++; 11 for(int i=1,j;i<=1000000;++i)if(f[i]){ 12 for(j=1;i*j<=1000000;++j) 13 if(f[i]==f[i*j])t=i*j; 14 tmp[t]=1; 15 } 16 for(int i=1;i<=1000000;++i) 17 if(tmp[i])ans++; 18 cout<<ans; 19 }
51nod1616最小集合(代码片段)
传送门分析不难发现集合中的数一定是集合内其它一堆数的$gcd$于是我们枚举$i$，统计原来集合中有几个数是$i$的倍数，设这个值为$f(i)$之后对于每个$i$如果不存在$f(x*i)=f(i)$则这个$i$合法，答案累加一代码#include<iostream>#inclu... 查看详情
1616最小集合51nod（辗转相处求最大公约数+stl）
1616 最小集合基准时间限制：1 秒空间限制：131072 KB分值: 80 难度：5级算法题 收藏 关注A君有一个集合。这个集合有个神奇的性质。若X,Y属于该集合，那么X与Y的最大公因数也属于该集合。但是他忘了这... 查看详情
51nod1616最小集合(枚举倍数)
分析：也就是取任意多个数，它们的最大公约数都在这个集合里。考虑到ai比较小，可以枚举小于a中最大值的所有数，判断是否为其中若干个数的gcd。记c[k]为a中k的倍数的个数，然后枚举k的倍数i*k，c[i]<2直接跳过，如果c[i*k]==... 查看详情
51nod1499（最小割）
题意分析 将一些点分成两个集合，很明显的最小割问题 设一个S、T，和S相连的点表示在B集合中，和T相连的点表示在A集合中 因为原题是完美值最大，我们转换一下，变成损失的价值最小，那么就是最小割问题了 ... 查看详情
51nod1352集合计数(扩展欧几里得)
...这式子能够用扩展GCD求出gcd，x和y，然后我们求出大于0的最小x，A*x第一个满足条件的集合firstSet，剩下的N-firstSet个集合能够直接除LCM(A,B)(A和B的最小公倍数)统计出数量。代码例如以下：#include<stdio.h>#include<string. 查看详情
51nod1352集合计数（中国剩余定理+扩展欧几里得）
...题意我们可以构造出方程：Ax+By=N+1，用扩展欧几里得算出最小的非负整数解x（x确定，y也就确定了），然后再把剩余的数分配掉（以它们的最小公倍数去分）。1#include<cstdio>2#include<iostream>3#include<algorithm>4usingnamespaces... 查看详情
51nod1640天气晴朗的魔法(最小生成树)(代码片段)
...还有一个更好的解法。本题的核心就是如何找到那条可以最小的最大的边(S)，二分确实是一个办法，但是还有一种办法是求最小生成树，其最大边就是(S)。??因为最小生成树是将几条不重复的最小的边加入集合形成的树，那么如... 查看详情
51nod1227平均最小公倍数
传送门 查看详情
51nod-1212无向图最小生成树
51Nod:1212无向图最小生成树。 link： http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1212 1212 无向图最小生成树基准时间限制：1 秒空间限制：131072 KB分值: 0 难度：基础题N个点M条边的无向连通图 查看详情
求最小原根51nod1135
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1135代码//thesmallestprimitiverootofprimeP#include<bits/stdc++.h>constlonglongmod=1e9+7;constdoubleex=1e-10;#defineinf0x3f3f3f3fusingn 查看详情
51nod最小周长
1283 最小周长题目来源： Codility基准时间限制：1 秒空间限制：131072 KB分值: 5 难度：1级算法题 收藏 关注一个矩形的面积为S，已知该矩形的边长都是整数，求所有满足条件的矩形中，周长的最小值... 查看详情
51nod-1098最小方差
51Nod- 1098 最小方差若x1,x2,x3......xn的平均数为k。则方差s^2=1/n*[(x1-k)^2+(x2-k)^2+.......+(xn-k)^2]。方差即偏离平方的均值，称为标准差或均方差，方差描述波动程度。给出M个数，从中找出N个数，使这N个数方差最小。 Input第1... 查看详情
51nod-1097拼成最小的数
51Nod- 1097 拼成最小的数设有n个正整数，将它们联接成一排，组成一个最小的多位整数。 例如：n=2时，2个整数32，321连接成的最小整数为：32132，n=4时，4个整数55，31，312,33联接成的最小整数为：312313355Input第1行：... 查看详情
51nod1283最小周长
...矩形的边长都是整数，求所有满足条件的矩形中，周长的最小值。例如：S=24，那么有{124}{212}{38}{46}这4种矩形，其中{46}的周长最小，为20。Input输入1个数S(1 <= S <= 10^9)。Output输出最小周长。Input示例24Output示例20... 查看详情
51nod1283最小周长
...矩形的边长都是整数，求所有满足条件的矩形中，周长的最小值。例如：S=24，那么有{124}{212}{38}{46}这4种矩形，其中{46}的周长最小，为20。Input输入1个数S(1 <= S <= 10^9)。Output输出最小周长。Input示例24Output示例20... 查看详情
51nod1065最小正子段和
题目链接：51nod1065最小正子段和房教说用前缀和做,然后看了别人博客懂了后就感觉,这个真有意思...1#include<cstdio>2#include<cstring>3#include<algorithm>4usingnamespacestd;5constintN=50001;6constintinf=0x3f3f3f3f;7pair<longl 查看详情
51nod1135(求最小原根)
...原根。（其中φ(m)表示m的欧拉函数）给出1个质数P，找出P最小的原根。我们先了解一下阶的概念：满足a^rΞ(1modm)---1的最小r即为 查看详情
51nod1499图(最小割)
还是太菜了。。感觉是最小割然而不知道怎么建图。。以下是题解1#include<iostream>2#include<vector>3#include<queue>4#include<stack>5#include<cstdio>6#include<cstring>7usingnamespacestd;8constintma 查看详情