平方子集
发布时间
阅读量：
阅读量
题解：
题目要求找出若干个数的乘积构成一个完全平方数，而完全平方数在质因数分解后，每个质因子的指数均为偶数。在70以内的范围内，素数的数量仅有十余个，因此采用状态压缩动态规划的方法进行求解。状态压缩所表示的内容是各个素数因子的指数是否为偶数。当选择一个数值时，相当于将其质因数分解后的指数累加至对应的状态中。若当前质因子的指数为偶数，则加上偶数值不会改变其奇偶性，可以直接从上一状态转移而来；而当指数为奇数时，则需要转移到异或结果为0的状态。根据二项式定理可知，在k个元素中选取奇数个（如1、3、5等）的组合方式数目与选取偶数个的方式数目相同，均为2^{k-1}。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int N=1e5+10;
int f[2][(1<<20)+1],num[75],pow2[N];
vector<int> prime;
void init()
{
for(int i=2;i<=70;i++){
int flag=0;
for(int j=2;j<=sqrt(i);j++){全部评论 (0)
还没有任何评论哟~