暴力出奇迹。。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<map>
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<ll,ll>mp[N];
map<ll,ll>::iterator p;
pair<ll,ll>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<node>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，如需转载请自行联系原作者
