提交
大佬博客
分析：比較難的一道數(shù)學(xué)題.有兩個(gè)結(jié)論：1.如果x是密碼，那么gcd(x,n)也是密碼. 2.如果x,y是密碼，那么gcd(x,y)也是密碼.根據(jù)這兩個(gè)結(jié)論就能很輕松地解決本題了.

先來證明第一個(gè)結(jié)論：構(gòu)造二元一次不定方程xk - nc = gcd(x,n),(也就是把x * k % n 寫成了不是取模的形式，x * k 減掉其中n的倍數(shù) )這個(gè)方程是一定有解的，也就是說一定存在一個(gè) k使得xk%n = gcd(x,n).而x是密碼，(x+x)%n也是密碼，所以kx%n也是密碼，那么gcd(x,n)就是密碼.x就是題目中告訴的a[k].

再來證明第二個(gè)結(jié)論：gcd(x,y) = ax + by,a,b有可能小于0.根據(jù)結(jié)論一可以推出

(px + qy)%n是密碼(p,q ≥ 0). 由ax + by ≡ gcd(x,y)(mod n),變形一下可以得到:

ax + by ≡ ax + by + pnx + qny(mod n) --> (a + pn) * x + (b + qn) * y ≡ gcd(x,y)(mod n).根據(jù)假設(shè)，((a + pn) * x + (b + qn) * y) % n是密碼(x,y系數(shù)大于0)，那么gcd(x,y)也是密碼.

把所有密碼寫出來以后，可以發(fā)現(xiàn)是一個(gè)x,2x,3x…的形式，所以任務(wù)就是找到一個(gè)最小的x使得x整除gcd(a[k],n).同時(shí)這個(gè)x不能整除a[j](1 ≤ j ＜ k).那么x就是gcd(a[k],n)的因子，根號(hào)的時(shí)間處理出來然后進(jìn)行判斷.判斷的話也有一個(gè)優(yōu)化，如果y是密碼，gcd(x,y)不是密碼，那么x也不是密碼，所以在判斷的時(shí)候看一下所有的gcd(a[j],n)是否被當(dāng)前的因子整除就行了.

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll ;
const int N = 250010 ;
ll n , k , a[N] , ans , cnt ;
bool check(int x)
{
	for(int i = 1 ;i <= cnt ;i ++)
	 if(a[i] % x == 0)
	  return false ;
	return true ; 
}
ll gcd(ll a , ll b)
{
	return b == 0 ? a : gcd(b , a % b) ;
}
int main()
{
	scanf("%lld%lld" , &n , &k) ;
	for(int i = 1 ;i <= k ;i ++)
	 {
	 	scanf("%lld" , &a[i]) ;
	 	a[i] = gcd(a[i] , n) ;
	 }
	 sort(a + 1 , a + k) ;
	 for(int i = 1 ;i < k ; i ++)
	 	if(a[i] != a[i - 1]) 
	 	 a[++ cnt] = a[i] ;
      for(ll i = 1 ;i <= sqrt(a[k]) ;i ++)
       	if(a[k] % i == 0 )
       	 {
       	 	if(check(i))
				{
					ans = n / i ;
       	 	        break ;
				} 
       	 	else if(check(a[k] / i))
       	 	 ans = n / a[k] * i ;
		 }
		printf("%lld\n" , ans) ;
       	 
	return 0 ;
}