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.
如：
題目大意：給你1~n這n個(gè)數(shù)，從這n個(gè)數(shù)中選取x個(gè)數(shù)（1<=x<=n)，使得這些數(shù)的最小公倍數(shù)（lcm)大于等于m，問你有多少種選法喉脖。
這是一道離散化dp的題笤昨。以前沒有接觸過欠痴，看了題解后谈火，恍然大悟，又學(xué)到了新知識妻献，嘻嘻蛛株。不多說了，看代碼：
#include <iostream>
#include <vector>
#include <map>
#include <iterator>
using namespace std;
typedef long long ll;
typedef map<ll, ll> mp;//first表示最小公倍數(shù)育拨，second表示有多少種情況谨履。
const int MAX_N = 45;
vector<mp> dp(MAX_N);//dp[i][j] = x;表示n為i時(shí)，可以有it->second(即x)種情況組成it->first(即j)
ll gcd(ll a, ll b) {//求最大公約數(shù)
return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {//求最小公倍數(shù)
return a * b / gcd(a, b);
}
void init() {
dp[1][1] = 1;
for (int i = 2; i < MAX_N; ++i) {//表示有i個(gè)指針的時(shí)候
dp[i] = dp[i - 1];//不取第i個(gè)的所有情況
++dp[i][i];//只取第i個(gè)的情況
for (mp::iterator it = dp[i - 1].begin(); it != dp[i - 1].end(); ++it)
dp[i][lcm(i, it->first)] += it->second;//在前i - 1的基礎(chǔ)上加上第i個(gè)數(shù)
}
}
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) {//計(jì)算滿足條件的個(gè)數(shù)
if (it->first >= m) ans += it->second;
}
cout << "Case #" << ks << ": " << ans << endl;
}
return 0;
}
