[HOJ 158][POI 18 Stage 2] Strongbox

這題我之前在HOJ上就AC過了( 作法在這裡 )，但一樣的 code 丟到 main 上 TLE 了，應該是 main 的主機跑太慢了，所以只好弄個另解=ㄦ=

作法：

參考了這篇的 code 。
由我之前打的那篇可知， d 整除 a_k 和 n ，並且不整除 a_1 ~ a_( k-1 ) 。也就是 d 整除 gcd ( a_k , n ) ，所以我們可以先把 a_k 改成 gcd( a_k , n ) ，不會影響答案。再來則是 d 不整除 a_1 ~ a_( k-1 ) 的條件，如果 a_i 有個質因數 p ，他不整除 a_k ，那麼 d 不整除 a_i 若且唯若 d 不整除 a_i / p ，也就是我們可以把每個 a_i 裡面和 a_k 不相干的部分都砍掉，也就是把 a_i 全部改成 gcd( a_i , a_k ) ，這樣也不會影響答案。

這時候問題就轉化為：現在有一個集合 S ，裡面包含了 a_k 的因數，但不包含 a_1 ~ a_( k-1 ) 的因數，求裡面最小的數 ( 也就是 d )是多少。這裡先介紹兩種找一個數的所有因數的方法，等等兩種都會用到。

假設現在要找 n 的所有因數，第一種就是直接從 1 枚舉到 sqrt( n ) ，如果 n 整除 i 那麼 i 和 n/i 都是 n 的因數，並且這樣不會遺漏。另外一種則是先求出 n 的標準分解式，假設為 p_1 ^ a_1 * p_2 ^ a_2 * ... * p_r ^ a_r ，那麼 n 的所有因數就型如 p_1 ^ b_1 * p_2 ^ b_2 * ... * p_r ^ b_r ，其中 0 <= b_i <= a_i ，所以我們可以對陣列 a_1 ~ a_r 作DFS，枚舉 p_i 要取幾個，就可以得到所有的因數。

回到原題，首先考慮這樣的一個算法：找出 a_1 ~ a_( k-1 ) 每個數的所有因數，把他們都丟進一個 set 裡，最後用第一種方法枚舉 a_k 的因數。但這樣在一開始就太慢了，因為在找出 a_1 ~ a_( k-1 ) 每個數的所有因數時會算到很多重複的數。不過我們知道 a_1 ~ a_( k-1 ) 全部都會是 a_k 的因數 ( 剛剛取過 gcd 了 )，也就是 a_1 ~ a_( k-1 ) 每個數字的樣子都是確定的( 質因數組成確定，但質因數的次方不確定 )，所以我們可以直接對 a_k 套用第二種找因數的方法，當找到了一個 a_k 的因數 u ，並且 u 出現在 a_1 ~ a_( k-1 ) 裡時，我們就知道 u 的每個質因數的次方是多少了，這時候就可以再用另外一個 dfs 找出所有 u 的因數並把它標記刪除了。但這樣還是有很多數被重複算到了，而這裡只需注意到，當 x 被刪除時，代表他的因數也全部都被刪除了，所以當第二次收到「刪除 x 」的指令時就可以不理他了，而這可以用一個 set 來維護，裡面存哪些數字已經被刪掉了。這樣就可以保證每個數頂多被刪除一次。最後再使用第一種找因數的方法，枚舉 a_k 的因數，如果遇到一個因數還沒被刪除，就把它拿去更新答案即可。


code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=250000+10 ;
 
LL getll()
{
    char c=getchar() ;
    while(c<'0'||c>'9') c=getchar() ;
    LL x=0 ;
    while(1)
    {
        x=x*10+c-'0' ;
        c=getchar() ;
        if(c<'0'||c>'9') return x ;
    }
}
 
LL a[maxn] ;
set<LL> st,del ;
 
int cnt=0,num[maxn],num2[maxn] ;
LL p[maxn] ;
 
void DEL(int x,LL now)
{
    if(x==cnt) { del.insert(now) ; return ; }
    if(del.find(now)!=del.end()) return ;
    DEL(x+1,now) ;
    for(int i=1;i<=num2[x];i++)
    {
        now/=p[x] ;
        DEL(x+1,now) ;
    }
}
 
void dfs(int x,LL now)
{
    if(x==cnt)
    {
        if(st.find(now)!=st.end()) DEL(0,now) ;
        return ;
    }
    if(del.find(now)!=del.end()) return ;
    dfs(x+1,now) ;
    for(int i=1;i<=num[x];i++)
    {
        now/=p[x] ; num2[x]-- ;
        dfs(x+1,now) ;
    }
    num2[x]=num[x] ;
}
 
main()
{
    LL n ; int m ;
    scanf("%lld%d",&n,&m) ;
    for(int i=1;i<=m;i++) a[i]=getll() ;
 
    a[m]=__gcd(a[m],n) ;
    for(int i=1;i<m;i++) st.insert(__gcd(a[i],a[m])) ;
 
    int sq=(int)sqrtl(a[m]+0.5) ;
    LL tmp=a[m] ;
    for(int i=2;i<=sq && i<tmp;i++) if(tmp%i==0)
    {
        p[cnt]=i ; num[cnt]=0 ;
        while(tmp%i==0) num[cnt]++ , tmp/=i ;
        num2[cnt]=num[cnt] ;
        cnt++ ;
    }
    if(tmp!=1) p[cnt]=tmp , num[cnt]=num2[cnt]=1 , cnt++ ;
 
    dfs(0,a[m]) ;
 
    LL ans=0LL ;
    for(int i=1;i<=sq;i++) if(a[m]%i==0)
    {
        if(del.find(i)==del.end()) ans=max(ans,n/i) ;
        if(del.find(a[m]/i)==del.end()) ans=max(ans,n/(a[m]/i)) ;
    }
    printf("%lld\n",ans) ;
}