BZOJ 2277 Poi2011 Strongbox 數論

BZOJ 2277 Poi2011 Strongbox 數論

題目大意：給定n和k個整數，求mod n加法下的群G的一個子群G'，滿足a[1]~a[k-1]都不在群中而a[k]在群中

首先易證G'一定是一個循環群

證明：顯然若a在群中則a的逆元在群中

那麼我們就有了減法運算

由群的封閉性可得若a和b都在群中則gcd(a,b)一定在群中

不妨設g為G'中所有元素的gcd 那麼群G''={0,g,2g,...}一定是G'的一個子群

由於G'-G''中的所有元素均不是g的倍數，故G'∩(G'-G'')為空 G'=G''

由此可得G'是以g為最小生成元的一個循環子群 大小為n/g

上面都是廢話

總之我們現在就要找到一個數g，使得g|n且g|a[k]，且對於任意1<=i<=k-1，g不是a[i]的約數

這個MS沒有什麼辦法直接做

我們發現10^14以內的數約數個數最多只有17280個

因此我們將a[1]~a[k-1]中所有的數對n取gcd，排序去重，這樣k的規模就減小到了17280

然後枚舉gcd(n,a[k])的所有約數，暴力驗證，取最小的g就是結果

時間復雜度O(√n+klogn+17280^2)

卡爆了

#include 
#include 
#include 
#include 
#define M 250250
using namespace std;
int k,tot;
long long n,ans,a[M];
void Check(long long x)
{
	int i;
	for(i=1;i<=tot;i++)
		if(a[i]%x==0)
			return ;
	ans=min(ans,x);
}
int main()
{
	int i;
	cin>>n>>k;ans=n;
	for(i=1;i<=k;i++)
	{
		#ifdef ONLINE_JUDGE
			scanf("%lld",&a[i]);
		#else
			scanf("%I64d",&a[i]);
		#endif
		a[i]=__gcd(n,a[i]);
	}
	sort(a+1,a+k);
	for(i=1;i