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.
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)
3 5 5 10 1 10 128
Case #1: 22 Case #2: 1023 Case #3: 586
//
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
long long gcd(long long a,long long b)
{
return b==0?a:gcd(b,a%b);
}
long long lcm(long long a,long long b)
{
return a/gcd(a,b)*b;
}
map<long long ,long long > dp[50];
//dp[i][j]表示前i个数，最小公倍数为j的个数
//离散DP
void DP()
{
dp[1][1]=1;
for(int i=2;i<=40;i++)
{
dp[i]=dp[i-1];
dp[i][i]++;
map<long long ,long long >::iterator j;
for(j=dp[i-1].begin();j!=dp[i-1].end();++j)
{
long long lc=lcm(i,j->first);
dp[i][lc]+=j->second;
}
}
}
int main()
{
DP();
int ci,pl=1;scanf("%d",&ci);
while(ci--)
{
int n;long long m;
scanf("%d%I64d",&n,&m);
long long ans=0;
map<long long ,long long >::iterator j;
for(j=dp[n].begin();j!=dp[n].end();++j)
{
if(j->first>=m) ans+=j->second;
}
printf("Case #%d: %I64d\n",pl++,ans);
}
return 0;
}