傳送門
文章目錄
題意：
給你一個序列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 随机化 + 质因子的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
