hdu4028(离散化dp)

Problem Description

There are no days and nights on byte island, so the residents here can hardly determine the length of a single day. Fortunately, they have invented a clock with several pointers. They have N pointers which can move round the clock. Every pointer ticks once per second, and the i-th pointer move to the starting position after i times of ticks. The wise of the byte island decide to define a day as the time interval between the initial time and the first time when all the pointers moves to the position exactly the same as the initial time.The wise of the island decide to choose some of the N pointers to make the length of the day greater or equal to M. They want to know how many different ways there are to make it possible.

Input

There are a lot of test cases. The first line of input contains exactly one integer, indicating the number of test cases. For each test cases, there are only one line contains two integers N and M, indicating the number of pointers and the lower bound for seconds of a day M. (1 <= N <= 40, 1 <= M <= 263
-1)

Output

For each test case, output a single integer denoting the number of ways.

如：

Paste_Image.png

题目大意：给你1~n这n个数，从这n个数中选取x个数（1<=x<=n)，使得这些数的最小公倍数（lcm)大于等于m，问你有多少种选法。

这是一道离散化dp的题。以前没有接触过，看了题解后，恍然大悟，又学到了新知识，嘻嘻。不多说了，看代码：

#include <iostream>
#include <vector>
#include <map>
#include <iterator>
using namespace std;

typedef long long ll;
typedef map<ll, ll> mp;//first表示最小公倍数，second表示有多少种情况。
const int MAX_N = 45;

vector<mp> dp(MAX_N);//dp[i][j] = x;表示n为i时，可以有it->second(即x)种情况组成it->first(即j)

ll gcd(ll a, ll b) {//求最大公约数
    return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b) {//求最小公倍数
    return a * b / gcd(a, b);
}

void init() {
    dp[1][1] = 1;
    for (int i = 2; i < MAX_N; ++i) {//表示有i个指针的时候
        dp[i] = dp[i - 1];//不取第i个的所有情况
        ++dp[i][i];//只取第i个的情况
        for (mp::iterator it = dp[i - 1].begin(); it != dp[i - 1].end(); ++it)
            dp[i][lcm(i, it->first)] += it->second;//在前i - 1的基础上加上第i个数
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    init();
    int t;
    cin >> t;
    for (int ks = 1; ks <= t; ++ks) {
        ll n, m;
        cin >> n >> m;
        ll ans = 0;
        for (mp::iterator it = dp[n].begin(); it != dp[n].end(); ++it) {//计算满足条件的个数
            if (it->first >= m) ans += it->second;
        }
        cout << "Case #" << ks << ": " << ans << endl;
    }
    return 0;
}