暴力出奇迹。。

#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，如需转载请自行联系原作者