XDU1201(西电17年校赛F题)题解

2019-04-14 13:04发布生成海报

站内文章 / 模拟电子

12098 0

题意

给定一个面积s，求面积s的矩形共有多少种，只要长或宽不同或者矩形网格划分方式不同则视为不同方案

笺释

一开始是用暴力枚举1-sqrt(s)中的所有因子，对于已枚举得到的因子c和对应因子s/c，将其枚举c和d的所有划分情况ans1和ans2，答案就是ans1*ans2。超时了。
然后想到如果c或者s/c是素数就不用枚举了，将其划分一定是1*c或者c*1两种情况，所以加入了miller-rabin判断大素数想优化一下

long long solve(long long a,long long b)
{
        long long ans1=0;long long ans2=0;
        if(Miller_Rabin(a))
        {
            ans1=2;
        }
        else
        {
        for(int i=1;i<=sqrt(a);i++)
        {
            if(a%i==0)
            {
                if(i!=sqrt(a))
                {
                    ans1+=1*2;
                }
                else
                {
                    ans1+=1;
                }
            }
        }
        }
        if(Miller_Rabin(b))
        {
            ans2=2;
        }
        else
        {
        for(int i=1;i<=sqrt(b);i++)
        {
            if(b%i==0)
            {
                if(i!=sqrt(b))
                {
                    ans2+=1*2;
                }
                else
                {
                    ans2+=1;
                }
            }
        }
        }
        return ans1*ans2;
}

然后还是超时。
又想到因子数和质因子数的关系，可以利用Pollard-rho算法预先求出所有质因子数，然后根据(a1+1)(a2+1)…的公式快速得到c因子数，但是还是超时。
有种逃脱不了命运之手的感觉呢。
于是问了tsy大佬，得到了这样的思路
s本身可以分解为若干质因数的乘积，设质因数为p1，p2，p3，分别有a1，a2，a3个。先考虑将s分解为c*d，也就意味着，我们要将p1分成2部分，一部分组成长，一部分组成宽，
//(一部分组成头部，雾`)
p1分成2部分，p2分成2部分，p3分成2部分，将所有方案数相乘就是将s分解为c*d的所有方案。还要注意挑的时候可以不选择，转化成挡板法的思想就是要设置两个板位于边缘，在最左侧放一个板的时候表示第一部分不选p1，第二部分选全部的p1这种情况，最右类推。
但是这道题不只是分解成c*d，长和宽本身内部也是要分开的，但是这个分的过程实际上类似于上述将s分解为c*d，也就是说，我们本来是将所有质因数集合分成2部分，现在考虑将其分成4部分即可。

完整代码

#include
#define MAXN 1000005
using namespace std;
typedef long long ll;
ll s;
ll box[45];
bool isprime[MAXN];
int prime[MAXN];
int len=0;
void sieve(int n)
{
    for(int i=0;i1;
    isprime[0]=isprime[1]=0;
    for(int i=2;iif(isprime[i])
        {
            prime[++len]=i;
            for(int j=2*i;j0;
        }
}
void makec()
{
    box[3]=1;
    for(int i=4;i<=45;i++)
    {
        box[i]=(box[i-1]*i)/(i-3);
    }
}
int main()
{
    sieve(MAXN);
    makec();
    while(~scanf("%lld",&s))
    {
        ll ans=1;
        for(int i=1;i<=len;i++)
        {
            int p=3;
            while(s%prime[i]==0)
            {
                s/=prime[i];
                p++;
            }
            ans*=box[p];
        }
        if(s>=2)
        {
            ans*=4;
        }
        printf("%lld
",ans);
    }
}