输入格式
第一行包含一个正整数N（1≤N≤10^ 5） 接下来N行，每行一个正整数Pi （ 1≤Pi≤10^ 7）
输出格式
有且只有一行，输出答案。
输入样例 3 4 9
15
输出样例
4
题解：最小生成树
如果两张卡片上的数相等，那么他们之间边权为0，可以将他们看做一个顶点。于是我们只需要考虑卡片上的互不相等的情况。 设卡片的最大值为maxz，注意到maxz不超过10^7，将卡片按值由小到大排序，对于某张卡片i，设它的值为pi。以pi为周期，将[pi,maxz]分为若干个区间，最后一个区间可能不足pi。在每个区间找到模pi的值最小的卡片，将该卡片和卡片i连边。特别的，第一个区间即[pi,2*pi-1]，要注意不能找第i张卡片本身。 我们只需要在刚才连的边中求一个最小生成树即可。 此时的边数最多为maxz*log(maxz)。 然后注意边权在10^7以内，所以，我们可以使用计数排序。这样，时间复杂度为O(N+maxz*log(maxz))
#include<cstdio> #include<vector> using namespace std; const int N=1e5+10; const int M=1e7; int n, p[N], rot[N], h[N], cnt[M+5]; int Root( int x ) { if( !rot[x] ) return x; return rot[x]=Root( rot[x] ); } int realv[M+5];//realv[i]:记录原值为i的位置被修改后的值 int pos[M+5];//pos[i]:记录i这个值最先出现的标号 struct node{ int s, e; node() {} node( int a, int b ) { s=a; e=b; } }; vector<node> edge[M+5]; long long sum; int main() { scanf( "%d", &n ); for( int i=1; i<=n; i++ ) { scanf( "%d", &p[i] ); realv[ p[i] ]=p[i]; if( !pos[ p[i] ] ) pos[ p[i] ]=i; } for( int i=M; i>=0; i-- ) if( !realv[i] ) realv[i]=realv[i+1]; for( int i=1; i<=n; i++ ) { if( cnt[ p[i] ]++ ) continue; if( realv[ p[i]+1 ] )//特殊处理第一个区间[ p[i], 2*p[i] ) if( realv[ p[i]*2 ]!=realv[p[i]+1] || p[i]*2>M ) edge[ realv[p[i]+1]-p[i] ].push_back( node( i, pos[ realv[p[i]+1] ] ) ); for( int j=p[i]*2; j<=M && realv[j]; j+=p[i] ) if( realv[ j+p[i] ]!=realv[j] || j+p[i]>M ) edge[ realv[j]-j ].push_back( node( i, pos[ realv[j] ] ) ); } for( int i=0; i<=M; i++ ) for( int j=0; j<(int)edge[i].size(); j++ ) { int s=Root( edge[i][j].s ), e=Root( edge[i][j].e ); if( s!=e ) { if( h[s]<h[e] ) rot[s]=e; else rot[e]=s; if( h[s]==h[e] ) h[s]++; sum+=i; } } printf( "%I64d\n", sum ); return 0; }
