WOJ 1543 Array

还是聪哥给我讲的思路才知道的，起初我利用两两互质去求发现有问题，互质只是必要条件而非充分条件，后来还是用的标准思路

即其实最终只要保留最大的素数的幂即可，其他包含该素数幂但指数低的都不用了，这样就能保证序列最小公倍数不变，同时，为了字典序最小，只需一点小小的处理。

在处理的时候遇到些小问题，主要是没考虑到每个值得因子没有求尽。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
ll num[550],ans[550],prime[550];
int n;
ll gcd(ll a,ll b)
{
    if (a<b) swap(a,b);
    return b==0? a:gcd(b,a%b);
}

int main()
{
    int cnt=0;
    while (scanf("%d",&n))
    {
        if (n==0) break;
        cnt=0;
        for (int i=0; i<n; i++)
        {
            scanf("%lld",&num[i]);
            ans[i]=num[i];
        }
        for (int i=0; i<n; i++)
        {
            while (ans[i]!=1)//求出每个ans[i]对应的因子
            {
                ll g=ans[i];
                for (int j=0; j<n; j++)
                {
                    if (ans[i]==1) break;
                    ll h=gcd(g,ans[j]);
                    if (h!=1)
                    {
                        g=h;
                    }
                }
                if (g!=1){
                  prime[cnt++]=g;//把因子存起来
                  for (int k=0; k<n; k++)
                    while (ans[k]%g==0) ans[k]/=g;//这里要除干净，为了这个搞了好久没弄出来
                }
            }
        }
        sort(prime,prime+cnt);//给因子排完序，把质数因子放在了前面，后面的非质数因子其实没有用了
        for (int i=0; i<n; i++)
            ans[i]=1;
        for (int i=0; i<cnt; i++)
        {
            ll tmp=prime[i];
            //cout<<tmp<<endl;
            int maxn=0;
            int loc=0;
            for (int j=0; j<n; j++)
            {
                int  tm=0;
                while (num[j]%tmp==0)
                {
                    // cout<<num[j]<<" "<<tmp<<endl;
                    num[j]/=tmp;
                    tm++;
                    // cout<<tm<<endl;
                }
                if (tm>=maxn) //这里即可保证字典序最小
                {
                    maxn=tm;
                    loc=j;
                    //cout<<j<<" loc "<<tmp<<endl;
                }
            }
            for (int k=0; k<maxn; k++)
                ans[loc]*=tmp;
        }
        printf("%lld",ans[0]);
        for (int i=1; i<n; i++)
            printf(" %lld",ans[i]);
        printf("
");
    }
    return 0;
}