暴力出奇迹。。
#include #include #include #include #include #include #include #include using namespace std; #define ll __int64 #define N 42 ll n,m,ans; ll Gcd(ll x,ll y){ if(x>y)swap(x,y); while(x){ y%=x; swap(x,y); } return y; } ll Lcp(ll x,ll y){return x*y/Gcd(x,y);} map mp[N]; map ::iterator p; pair tmp; void work(ll x, ll cur){ p = mp[cur].end(); if(p==mp[cur].begin())return; p--; for(;;p--){ tmp = *p; ll dou = Lcp(tmp.first,x); if(dou>=m){ ans += tmp.second; } mp[cur][dou]+=tmp.second; if(p==mp[cur].begin())return; } } struct node{ ll num, ans; bool operator<(const node&a)const{ return a.num>num; } }; set myset[N]; int main(){ ll i, j, Cas = 1, T;scanf("%I64d",&T); mp[0].clear(); for(i=1;i<=40;i++) { mp[i] = mp[i-1]; work(i,i); mp[i][i]++; node now = {0,0}; myset[i].clear(); for(p=mp[i].end(),p--;;p--){ tmp = *p; now.num = tmp.first; now.ans += tmp.second; myset[i].insert(now); if(p==mp[i].begin())break; } } while(T--){ scanf("%I64d %I64d",&n,&m); printf("Case #%I64d: ",Cas++); node dou = {m,-1}; if(myset[n].lower_bound(dou)==myset[n].end())puts("0"); else printf("%I64d\n",myset[n].lower_bound(dou)->ans); } return 0; }