hdu6237 分解质因子

时间：2022-06-27 03:19:03

题意：给一堆石子，每次移动一颗到另一堆，要求最小次数使得，所有石子数gcd>1

题解:枚举所有质因子，然后找次数最小的那一个，统计次数时，我们可以事先记录下每堆石子余质因子 的和，对所有石子取余，sort，从后往前扫（这样做的原因是取余后的数组只有可能有三种，排序之后最后的就是最大的，加上质因子减去石子数就是使这堆石子加上一些石子，然后又因为，可以有多堆石子放到同一堆里，那么这样处理就是可行的），每次加了之后总和减去质因子，如果总和小于0，那么就退出

ps：这题的难点不在于分解质因子，而在于找最小次数。

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pii pair<int,int>

#define C 0.5772156649

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f3f;

ll a[N],b[N];

int n;

ll solve(ll x)

{

    ll sum=,ans=;

    for(int j=;j<=n;j++)

    {

        b[j]=a[j]%x;

        sum+=b[j];

    }

    sort(b+,b++n);

    for(int i=n;i>=;i--)

    {

        if(!b[i])continue;

        ans+=x-b[i];

        sum-=x;

        if(sum<=)break;

    }

    return ans;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        ll sum=;

        for(int i=; i<=n; i++)

        {

            scanf("%lld",&a[i]);

            sum+=a[i];

        }

        ll res=1e18;

        for(ll i=; i*i<=sum; i++)

        {

            if(sum%i==)

            {

                res=min(res,solve(i));

                while(sum%i==)sum/=i;

            }

        }

        if(sum!=)

        {

            res=min(res,solve(sum));

        }

        printf("%lld\n",res);

    }

    return ;

}

/********************

********************/

相关文章