传送门
文章目录
题意：
给你一个序列aaa，找一个最大的集合，集合中所有元素模mmm相等。
思路：
之前做过一道连续的，直接尺取就好，这个不连续加大了难度。
考虑最简单的情况m=2m=2m=2时，答案至少为⌈n2⌉\left \lceil \frac{n}{2} \right \rceil⌈2n⌉，看到这个很容易想到随机算法。
我们随机选两个点a,ba,ba,b，那么这两个点都在答案中的概率至少为14\frac{1}{4}41，如果我们选404040次，那么不在答案中的概率(34)40(\frac{3}{4})^{40}(43)40是一个很大的数，几乎为000，所以现在假设我们选的两个点都在答案中，我们就可以通过枚举∣ai−aj∣|a_i-a_j|∣ai−aj∣的质因子作为mmm，让后取最大值即可。
一个数的质因子个数很少，所以还是比较快的。
O(kamax+11kn)O(k\sqrt {a_{max}}+11kn)O(kamax+11kn)
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); }
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=4000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
;
LL a
[N
];
int prime
[N
+10],cnt
;
bool st
[N
+10];
mt19937
rnd(time(0));void get_prime(int n
)
{for(int i
=2;i
<=n
;i
++){if(!st
[i
]) prime
[cnt
++]=i
;for(int j
=0;prime
[j
]<=n
/i
;j
++){st
[prime
[j
]*i
]=true;if(i
%prime
[j
]==0) break; } }
} int get(LL p
,LL x
) {int ans
=0;for(int i
=1;i
<=n
;i
++) if(a
[i
]%p
==x
) ans
++;return ans
;
}int main()
{
get_prime(N
-1);int _
; scanf("%d",&_
);while(_
--) {scanf("%d",&n
);for(int i
=1;i
<=n
;i
++) scanf("%lld",&a
[i
]);int ans
=1;for(int k
=1;k
<=40;k
++) {int pos1
,pos2
;pos1
=rnd()%n
+1,pos2
=rnd()%n
+1;if(pos1
==pos2
) {k
--;continue;}LL as
=abs(a
[pos1
]-a
[pos2
]);for(int i
=0;i
<cnt
&&1ll*prime
[i
]*prime
[i
]<=as
;i
++) if(as
%prime
[i
]==0) {while(as
%prime
[i
]==0) as
/=prime
[i
];ans
=max(ans
,get(prime
[i
],a
[pos1
]%prime
[i
]));}if(as
>1) ans
=max(ans
,get(as
,a
[pos1
]%as
));}printf("%d\n",ans
);}return 0;
}
总结
以上是生活随笔为你收集整理的HDU - 7073 Integers Have Friends 2.0 随机化 + 质因子的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
