2010-1134

从 Trac 迁移的文章

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

原文章内容如下：

'''题意'''
      我们称一个数为square-free number当且仅当这个数是一个整数并且它不被除了1以外的其它正整数的平方整除。如果一个集合只包含square-free number，那么我们称这个集合为square-free set。定义一个集合的乘积表示该集合所包含元素的乘积。对于一个集合A，若A不仅是square-free set，并且A的乘积也是square-free number，那么我们称A是一个perfect set。
给你两个数n和k，请你求出包含不多于k个元素，且每个元素均属于[1, n]的非空perfect set的数目。(n, k <= 500)


'''题解'''
      搜索+记忆化。[[BR]]
      因为所以元素不超过500，而又必须是square-free number，所以对于一个元素的质因数分解没有重复的因子出现，并且不会超过4个，因为2*3*5*7=210，同时因子的只能是1到500间的质数，所以范围很小，可以直接搜。

'''代码'''

{{{
#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;
}

}}}

题意

我们称一个数为square-free number当且仅当这个数是一个整数并且它不被除了1以外的其它正整数的平方整除。如果一个集合只包含square-free number，那么我们称这个集合为square-free set。定义一个集合的乘积表示该集合所包含元素的乘积。对于一个集合A，若A不仅是square-free set，并且A的乘积也是square-free number，那么我们称A是一个perfect set。

给你两个数n和k，请你求出包含不多于k个元素，且每个元素均属于[1, n]的非空perfect set的数目。(n, k <= 500)

题解

搜索+记忆化。

因为所以元素不超过500，而又必须是square-free number，所以对于一个元素的质因数分解没有重复的因子出现，并且不会超过4个，因为2*3*5*7=210，同时因子的只能是1到500间的质数，所以范围很小，可以直接搜。

代码

#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;
}