2010-1167

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

/*补题解工程..表示有点忘了算法了*/
题目大意：
求perfect square number set.
定义perfect square number set：
*必须是一个square number set
*元素的乘积是一个square number
定义square number set:
组成的元素是square number
定义square number:
不能被平方数整除

分析：
关键点是元素乘积也必须是square number
也就是说，对最后的乘积进行质因数分解，一个质因数的次数<=1

如果没有元素范围限制，则可以借用第二类斯特林数。由于这个限制，所以采用搜索办法。

贴一下看到的AC代码，由于里面用了STL的一些数据结构，理解不能。
#include<vector>
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<sstream>
#include<set>
#include<map>
#define sqr(x) ((x)*(x))

using namespace std;

const int rest = 1000000007;
map<pair<int, pair<int, vector<int> > >, int> d;
vector<int> prim;
int n, k;

int dfs(int cur, int num, vector<int> a)
{
    if (cur == prim.size()) return (num > 0);
    while (a.size() > 0 && a[a.size() - 1] * prim[cur] > n) a.pop_back();
    pair<int, pair<int, vector<int> > > tp = make_pair(cur, make_pair(num, a));
    if (d.find(tp) != d.end()) return d[tp];
    int val;
    val = dfs(cur + 1, num, a);
    vector<int> b;
    if (num < k)
    {
        b = a; b.push_back(prim[cur]);
        sort(b.begin(), b.end());
        val = (val + dfs(cur + 1, num + 1, b)) % rest;
    }
    for (int i = 0; i < a.size(); i++)
    {
        b = a; b[i] = b[i] * prim[cur];
        sort(b.begin(), b.end());
        val = (val + dfs(cur + 1, num, b)) % rest;
    }
    d[tp] = val; return val;
}


class SquareFreeSets
{
    public:
    int countPerfect(int N, int K)
    {
        n = N; k = K;
        for (int i = 2; i <= N; i++)
        {
            bool flag = true;
            for (int j = 2; j * j <= i; j++)
                if (i % j == 0)
                {
                    flag = false; break;
                }
            if (flag) prim.push_back(i);
        }
        vector<int> st;
        return dfs(0, 0, st);
    }
};

int main()
{
//  freopen("square.in", "r", stdin);
//  freopen("square.out", "w", stdout);
    int N, K;
    while (cin >> N >> K) {
          prim.clear();
          vector<int>().swap(prim);
          d.clear();
          cout << SquareFreeSets().countPerfect(N, K) << endl;
    }
    return 0;
}

/*补题解工程..表示有点忘了算法了*/

题目大意：

求perfect square number set.

定义perfect square number set：

*必须是一个square number set

*元素的乘积是一个square number

定义square number set:

组成的元素是square number

定义square number:

不能被平方数整除

分析：

关键点是元素乘积也必须是square number

也就是说，对最后的乘积进行质因数分解，一个质因数的次数<=1

如果没有元素范围限制，则可以借用第二类斯特林数。由于这个限制，所以采用搜索办法。

贴一下看到的AC代码，由于里面用了STL的一些数据结构，理解不能。

#include

#define sqr(x) ((x)*(x))

using namespace std;

const int rest = 1000000007;

map > >, int> d;

vector prim;

int n, k;

int dfs(int cur, int num, vector a)

{

if (cur == prim.size()) return (num > 0);

while (a.size() > 0 && a[a.size() - 1] * prim[cur] > n) a.pop_back();

pair > > tp = make_pair(cur, make_pair(num, a));

if (d.find(tp) != d.end()) return d[tp];

int val;

val = dfs(cur + 1, num, a);

vector b;

if (num < k)

{

b = a; b.push_back(prim[cur]);

sort(b.begin(), b.end());

val = (val + dfs(cur + 1, num + 1, b)) % rest;

}

for (int i = 0; i < a.size(); i++)

{

b = a; b[i] = b[i] * prim[cur];

sort(b.begin(), b.end());

val = (val + dfs(cur + 1, num, b)) % rest;

}

d[tp] = val; return val;

}

class SquareFreeSets

{

public:

int countPerfect(int N, int K)

{

n = N; k = K;

for (int i = 2; i <= N; i++)

{

bool flag = true;

for (int j = 2; j * j <= i; j++)

if (i % j == 0)

{

flag = false; break;

}

if (flag) prim.push_back(i);

}

vector st;

return dfs(0, 0, st);

}

};

int main()

{

// freopen("square.in", "r", stdin);

// freopen("square.out", "w", stdout);

int N, K;

while (cin >> N >> K) {

prim.clear();

vector().swap(prim);

d.clear();

cout << SquareFreeSets().countPerfect(N, K) << endl;

}

return 0;

}