题解 P6274 【[eJOI2017]六】

Zesty_Fox

2020-06-16 16:57:14

Solution

安利一波博客:[点这里](https://www.cnblogs.com/acceptedzhs/p/13141901.html) 首先,题目说了**最多$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$来存,简化代码。 Code: ```cpp #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; } ```