记录编号	364835	评测结果	AAATTTTTTT
题目名称	2593.[河南省队2016]幂	最终得分	30
用户昵称	小一米	是否通过	未通过
代码语言	C++	运行时间	7.006 s
提交时间	2017-01-18 11:36:17	内存使用	0.48 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
#define LL long long
using namespace std;
int n,m;
int prime[32000],gcd[65][65],gao[65];
bool vis[32000],ok[65];
LL ans;
int G(int x,int y){return y?G(y,x%y):x;}
void init()
{
	int lim=31625;
	for (int i=2;i<=lim;++i)
	{
		if (!vis[i]) prime[++prime[0]]=i;
		for (int j=1;i*prime[j]<=lim&&j<=prime[0];++j)
		{
			vis[i*prime[j]]=1;
			if (i%prime[j]==0) break;
		}
	}
	for (int i=0;i<=60;++i)
		for (int j=0;j<=60;++j)
			gcd[i][j]=G(i,j);
}
void dfs(int x,LL sum,int g)
{
	if (x>prime[0]||sum*prime[x]>n)
	{
		if (!g) return;
		if (ok[g]) {ans+=gao[g];return;}
		ok[g]=1;
		for (int j=1;j<=m;++j)
		{
			LL t=g*j;
			if (t/(g-1)>m) break;
			if (t<=m) {--gao[g];continue;} 
			for (int k=g-1;k>=1&&t/k<=m;--k)
			if (t%k==0)
			{
				--gao[g];
				break;
			}
		}
		ans+=gao[g];
		return;
	}
	LL t=1;
	for (int i=1;sum*t<=n;++i)
	{
		if (gcd[i-1][g]!=1)	dfs(x+1,sum*t,gcd[i-1][g]);
		t=t*prime[x];
	}
}
main()
{
	freopen("powerz.in","r",stdin);
	freopen("powerz.out","w",stdout);
	init();
	scanf("%d%d",&n,&m);
	ans=1LL*n*m+1-m;
	dfs(1,1,0);
	printf("%lld\n",ans);
}