本文共 1303 字，大约阅读时间需要 4 分钟。
暴力出奇迹。。
#include #include #include #include #include #include #include #include using namespace std;#define ll __int64#define N 42ll 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;}
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5088444.html，如需转载请自行联系原作者