Mishka and Divisors[CodeForces Round #365 Div.2]

http://codeforces.com/contest/703/problem/E

题意：给定一个最多个数的序列，从中选出最少个数的数字，使得他们的乘积是k的倍数，若有多种选择方式，输出选出数字和最小的一种，若有多种，输出任意一种。

动态规划，dp[i][j]表示从前i个数里选，所得乘积是j的倍数。显然dp[i][j]=max(dp[i-1][j],dp[i-1][j/gcd(j,a[i])])。由于k可能很大，所以只需令j分别等于k的每个约数即可。

确定k的约数的时候令i从1到sqrt(k)循环判断，注意由于k很大，这里的i要使用longlong。

#include<bits/stdc++.h>

using namespace std;

#define ft first

#define sd second

#define mp make_pair

long long a[], k, f[], b[];

int fc, n;

pair<int, long long> dp[][];

map<long long , int> e;

int main()

{

    //freopen("input.txt", "r", stdin);

    scanf("%d%I64d", &n, &k);

    long long t = k;

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

    {

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

        b[i] = __gcd(k, a[i]);

        t /= __gcd(t, a[i]);

    }

    if (t != )

    {

        printf("-1\n");

        return ;

    }

    if (k == )

    {

        printf("1\n%d\n", (int)(min_element(a + , a + n + ) - a));

        return ;

    }

    e.clear();

    fc = ;

    for (long long i = ; i * i <= k; i++)

    {

        if (k % i != ) continue;

        f[fc++] = i;

        if (i * i != k) f[fc++] = k / i;

    }

    sort(f, f + fc);

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

        e[f[i]] = i;

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

        dp[][i] = mp(n + , );

    dp[][] = mp(, );

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

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

        {

            dp[i][j] = dp[i - ][j];

            long long v = e[f[j] / __gcd(f[j], b[i])];

            if (dp[i][j] > mp(dp[i - ][v].ft + , dp[i - ][v].sd + a[i]))

                dp[i][j] = mp(dp[i - ][v].ft + , dp[i - ][v].sd + a[i]);

        }

    printf("%d\n", dp[n][fc - ].ft);

    t = k;

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

    {

        if (dp[i][e[t]] == dp[i - ][e[t]]) continue;

        printf("%d ", i);

        t /= __gcd(t, b[i]);

    }

    printf("\n");

    //fclose(stdin);

    return ;

}

巴特西

Mishka and Divisors[CodeForces Round #365 Div.2]

最新文章

热门文章