【贪心】【TOJ4107】【A simple problem】

Given three integers n(1≤n≤1018), m(1≤m≤105), k(1≤k≤1018).
you should find a list of integer A1,A2,…,Am which
satisfies three conditions:

1. A1+A2+⋯+Am=n.

2. 1≤Ai≤k−1 for
each (1≤i≤m).

3. GCD(A1,A2,…,Am)=1.GCD
means the greatest common divisor

4. if i<j then Ai≥Aj.

As the author is too lazy to write a special judge, if there's no answer ouput "I love ACM", And if there's more than one answer, output the one has the minimum A1,
and if there still multiple answer make theA2 as
small as possible, then A3,A4…

m=1 直接 “I love ACM”

m=2

均摊第二个给第一个不断给1

m=3

均摊最后一个给第一个1个1

很多边界数据注意下

3 3 1

1 1 1

1 1 4

等等..

代码如下：

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <ctime>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <string>

#define oo 0x13131313

using namespace std;

long long n,m,k;

long long gcd(long long a,long long b)

{

    long long r;

    while(b>0)

    {

         r=a%b;

         a=b;

         b=r;

    }

    return a;

}

long long A[100000+5];

void do1()

{

    if(n%2==1)

    {

        long long p=n/2+1;

        if(p<=k-1) printf("%lld %lld\n",p,p-1);

        else printf("I love ACM\n");

    }

    else

    {

        int ok=1;

        long long a=n/2,b=n/2;

        while(a+1<=k-1&&b-1>=1)

        {

            a++;

            b--;

            if(gcd(a,b)==1)

            {

                ok=0;

                printf("%lld %lld\n",a,b);

                break;

            }

        }

        if(ok)

        printf("I love ACM\n");

    }

}

void do2()

{

    memset(A,0,sizeof(A));

    for(int i=1;i<=m;i++)

    {

        A[i]=n/m;

    }

    for(int i=1;i<=n%m;i++)

    {

        A[i]++;

    }

    if(n%m==0&&n!=m)

    {

        A[1]++;A[m]--;

    }

    if(A[1]<=k-1&&A[m]>=1)

    {

     for(int i=1;i<=m;i++)

    {

        printf("%lld",A[i]);

        if(i!=m) printf(" ");

    }

    printf("\n");

    }

    else printf("I love ACM\n");

}

int main()

{

    while(cin>>n>>m>>k)

    {

        if(m==1&&n!=1||k==1) printf("I love ACM\n");

        else if(m==1&&n==1) printf("1\n");

        else

        {

                if(m==2) do1();

                else if(m>=3) do2();

        }

    }

}

巴特西

【贪心】【TOJ4107】【A simple problem】

最新文章

热门文章