4028 The time of a day
题目大意：有个奇怪的钟有n（1<=n<=40）个指针编号1~n 每根指针每过其对应编号秒后回到初始位置，定义一天的时间长为k（1<=k<=n）个指针都回到初始位置的间隔，现在给你一个m(<2^63-1)问从有多少种方案可以使一天的时间大于等于m
分析：一天的时间计算很简单就是k个数的最小公倍数，如果枚举每一种选取方案那么需要每次询问O(2^n)肯定是不现实的，分析发现虽然方案数很多但是方案对应的最小公倍数却很小，因为有很多的最小公倍数是相同的，大概有4万多种。这样就可以dp了
dp[i][j]表示前i个指针中选取方案状态（最小公倍数）为j有多少种那么方程为dp[i][j]=dp[i-1][j]（不选第i）+dp[i-1][k](选第i个 只有当lcm(k,i)==j才加)。
那么第二维很大怎么办STL map!!!!
1 #include <iostream> 2 #include<cstdio> 3 #include <cstring> 4 #include <map> 5 typedef long long ll; 6 using namespace std; 7 map<ll,ll>dp[50]; 8 int n; 9 ll m; 10 ll gcd(ll a,ll b) 11 { 12 return b==0?a:gcd(b,a%b); 13 } 14 ll lcm(ll a,ll b) 15 { 16 return a/gcd(a,b)*b; 17 } 18 void init() 19 { 20 dp[1][1]=1; 21 for(int i=2;i<=40;++i) 22 { 23 dp[i]=dp[i-1]; 24 dp[i][i]++; 25 for(map<ll,ll>::iterator it = dp[i-1].begin();it!=dp[i-1].end();++it) 26 { 27 long long t = lcm(i,it->first); 28 dp[i][t]+=it->second; 29 } 30 } 31 } 32 ll getans() 33 { 34 ll ans=0; 35 for(map<ll,ll>::iterator it = dp[n].begin();it!=dp[n].end();++it) 36 { 37 if(it->first>=m)ans+=it->second; 38 } 39 return ans; 40 } 41 int main () 42 { 43 init(); 44 int t; 45 scanf("%d",&t); 46 for(int Case=1;Case<=t;++Case) 47 { 48 scanf("%d%I64d",&n,&m); 49 printf("Case #%d: %I64d ",Case,getans()); 50 } 51 }