Little Difference Gym - 101612L 思维

题意：

给你一个数n，你需要输出它可以由那几个数相乘构成，我们设可以由x个数构成，这x个数中最小值为minn，最大值为maxx，那么要求maxx-minn<=1

问你满足上面要求的情况有多少种。如果一个数的构成方式由无数种就输出-1

样例解释：

输入：

输出：

1 12

3 2 3 2

2 4 3

12有三种满足题意的构成方式，分别是12、2*3*2、4*3

输入

输出

-1

因为1的构成可以是1、1*1、1*1*1、1*1*1*1无数种

题解：

你会发现输出-1的情况都是2的次幂，例如1、2、4、8、16.特判一下就可以了

其他情况首先n本身算一次。后面就是两个数相乘得到n，这种情况设定x=sqrt(n)

判断一下x*x==n、x*(x-1)==n、x*(x+1)==n

之后就是多个数相乘（大于两个），n最大是1e18，那么我们枚举1到n^1/3的所有数，判断就可以

代码：

#include <algorithm>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 1e4 + 5;

const int mod = 1000000007;

vector<ll>r[maxn],que;

int main()

{

    ll n;

    freopen("little.in","r",stdin);

    freopen("little.out","w",stdout);

    scanf("%lld",&n);

    if((n&(-n))==n)

    {

        printf("-1\n");

        return 0;

    }

    ll pos=0;

    //que.push_back(1);

    que.push_back(n);

    r[pos]=que;

    pos++;

    que.clear();

    for(ll i=2;i*i*i<=n;++i)

    {

        ll tmp=n;

        if(tmp%i==0)

        {

            while(tmp%i==0)

                que.push_back(i),tmp/=i;

            while(tmp%(i+1)==0)

                que.push_back(i+1),tmp/=(i+1);

            if(tmp==1)

            {

                r[pos]=que;

                pos++;

            }

            que.clear();

        }

    }

    ll tmp=sqrt(n);

    if(tmp*tmp==n)

    {

        que.push_back(tmp);

        que.push_back(tmp);

        r[pos]=que;

        pos++;

        que.clear();

    }

    if(tmp*(tmp+1)==n)

    {

        que.push_back(tmp);

        que.push_back(tmp+1);

        r[pos]=que;

        pos++;

        que.clear();

    }

    if(tmp*(tmp-1)==n)

    {

        que.push_back(tmp);

        que.push_back(tmp-1);

        r[pos]=que;

        pos++;

        que.clear();

    }

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

    for(ll i=0;i<pos;++i)

    {

        ll len=r[i].size();

        printf("%lld ",len);

        for(ll j=0;j<len-1;++j)

        {

            printf("%lld ",r[i][j]);

        }

        printf("%lld\n",r[i][len-1]);

    }

    return 0;

}

巴特西

Little Difference Gym - 101612L 思维

最新文章

热门文章