【Luogu】 P6274 [eJOI2017]六题解

首先，题目说了最多\(6\)个质因数。

如此小的数据范围，不是状压还是啥？

然后，我们可以发现一个性质：只要两个因数有相同的质因数（不管次数是多少），两者就不互质。

这启示我们用一个二进制数来表示一类\(N\)的因数，每个二进制位表示对应质因数的状态，\(1\)表示有，\(0\)表示没有。

举个例子：\(N=12156144=2^4 \times 3 \times 7 \times 11^2 \times 13 \times 23\)

那么，每个二进制数中，第\(0\)位表示是否有质因数\(2\)，第\(1\)位表示是否有质因数\(3\)，第\(2\)位表示是否有质因数\(7\)......以此类推。

比如说，\(N\)的因数\(132=2^2 \times 3 \times 11\)，应该对应的是\({(001011)}_2\)，即它属于第\(11\)类数。

状压以后，不难用乘法原理求出每类数的个数。接着，我们考虑如何求出答案。

我们用一个三进制数来表示当前状态。第\(i\)位表示当前第\(i\)类数的数量+与第\(i\)类不互质的数的个数。状态转移就很好写了。枚举当前增加哪一类数，直接转移即可。

最后有个要点：可以改成四进制数来写，并用一个\(int128\)来存，简化代码。

（Dev-C++是编译不通过的，因为这东西只有Linux下有）

Code:

#include <iostream>

#include <cstdio>

#include <map>

#define int long long

using namespace std;

typedef __uint128_t int128;

const int MOD=1e9+7;

int n,zys[105],cs[105],cnt,sum[1<<8],ans;

map<int128,int> m; //存状态

int dfs(int128 stat){

    if(m.count(stat)) return m[stat];//记忆化

    int res=1;

    for(int i=1;i<(1<<cnt);i++){ //枚举增加的数是哪一类

        int cur=(stat>>(i<<1))&3; //获取当前这一类数的情况

        int128 tmp=stat;

        if(cur>1) continue; //如果已经有数与它不互质了，显然不能再增加此类数

        for(int j=0;j<(1<<cnt);j++){

            if(!(i&j)) continue; //验证每一类数是否与所选的数互质

            //如果这两类数有相同的质因子，则按位与肯定不为0

            if((stat>>(j<<1)&3)<2) stat+=((int128)1<<(j<<1));

        }

        res=(res+dfs(stat)*sum[i])%MOD;

        stat=tmp;

    }

    return m[stat]=res;

}

signed main(){

    scanf("%lld",&n);

    int tmp=n;

    for(int i=2;i*i<=tmp;i++){

        if(tmp%i==0){

            zys[++cnt]=i;

            while(tmp%i==0) tmp/=i,cs[cnt]++; //分解质因数

            //zys:存储从小到大不同的质因子

            //cs:每一个质因子的次数

        }

    }

    if(tmp>1) zys[++cnt]=tmp,cs[cnt]++;

    for(int i=0;i<(1<<cnt);i++){

        sum[i]=1;

        for(int j=1;j<=cnt;j++){

            if(i&(1<<j-1)) sum[i]=(sum[i]*cs[j])%MOD; //乘法原理，计算每一类数的个数

        }

    }

    ans=dfs((int128)0);

    cout<<(ans-1+MOD)%MOD<<endl;//空集不能算，所以答案-1

    return 0;

}

巴特西

【Luogu】 P6274 [eJOI2017]六题解

最新文章

热门文章

巴特西

【Luogu】 P6274 [eJOI2017]六 题解

最新文章

热门文章

【Luogu】 P6274 [eJOI2017]六题解