记录编号	365723	评测结果	AAAAAAAAAA
题目名称	[河南省队2016]幂	最终得分	100
用户昵称	小一米	是否通过	通过
代码语言	C++	运行时间	3.014 s
提交时间	2017-01-21 15:21:06	内存使用	0.48 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
#define min(x,y) ((x)<(y)?(x):(y))
#define LL long long
using namespace std;
int n,m,lim,XX;
int prime[32000],gcd[65][65];
bool vis[32000];
LL ans,tot,sum[65],ok[33];
inline LL G(LL x,LL y){return y?G(y,x%y):x;}
void init()
{
	lim=sqrt(n);
	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);
}
inline void dfs1(int x,LL lcm,int mi,int val)
{
	if (1LL*x*m/lcm<1||x<=mi)
	{
		ans+=(1LL*mi*m)/lcm*val;
		sum[29]-=(1LL*mi*m)/lcm/29*val;
		return;
	}
	ok[x]=lcm;
	dfs1(x-1,lcm,mi,val);
	ok[x]=0;
	if (lcm%x)
	ok[x]=lcm,
	dfs1(x-1,lcm/G(x,lcm)*x,mi,-val),
	ok[x]=0;
	else
	{
		bool flag=0;
		for (int i=XX-1;i>x;--i)
			if (lcm%i==0)
			{
				if (lcm==ok[i]) flag=1;
				break;
			}
		if (!flag)
			ok[x]=lcm,
			dfs1(x-1,lcm,mi,-val);
			ok[x]=0;
	}
}
inline void dfs2(int x,LL cnt,int g)
{
	if (x>prime[0]||cnt*prime[x]>lim)
	{
		if (g!=1) return;
		int t=(log(n)+1e-6)/log(cnt);
		ans+=sum[t];
		tot-=1LL*t*m;
		return;
	}
	LL t=1;
	for (int i=1;t*cnt<=lim;++i)
	{
		dfs2(x+1,cnt*t,gcd[g][i-1]);
		t*=prime[x];
	}
}
main()
{
		freopen("powerz.in","r",stdin);
	freopen("powerz.out","w",stdout);
	scanf("%d%d",&n,&m);
	init();
	sum[1]=m;
	for (int i=2;1<<i<=n&&i<=28;++i)
	{
		ans=sum[i-1];
		XX=i;
		dfs1(i-1,i,i,1);
		for (int j=i-1;j>=1;--j)
		{
			bool flag=0;
			for (int k=j+1;k<i;++k)
				if (i/gcd[i][j]*j%k==0)
				{
					flag=1;
					break;
				}
			if (!flag) dfs1(i-1,i/gcd[i][j]*j,j,-1);
		}
		sum[i]=ans;
	}
	sum[29]+=sum[28]+m-m/29;
//	printf("%lld\n",sum[29]);
//	printf("%lld %lld\n",sum[28],sum[29]);
//	if (1<<28<=n)
//	{
//		for (int i=2;i<=28;++i)
//			sum[29]+=(sum[i])/29;
//		sum[29]+=m;
//	}
	tot=1LL*n*m-m+1;
	ans=0;
	dfs2(1,1,0);
	printf("%lld\n",ans+tot);
}