记录编号	356663	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2016]循环之美	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.414 s
提交时间	2016-12-02 17:49:14	内存使用	52.94 MiB

#include<cstdio>
const int N=1e6+10,SIZE=1e6;
typedef long long ll;
int n,m,k,u[N],p[N],cnt,s[N],v[2],q[N],size;
bool hash[N],vis[2][N];
ll su[2][N];
ll get_s(int x,bool y){
	return x<=SIZE?s[x]:su[y][v[y]/x];
}
void solve(int x,bool y){
	if (x<=SIZE) return;
	int t=v[y]/x;
	if (vis[y][t]) return;
	vis[y][t]=1;su[y][t]=1;
	int l,r=1;
	while (r<x){
		l=r+1;r=x/(x/l);
		solve(x/l,y);
		su[y][t]-=get_s(x/l,y)*(r-l+1);
	}
}
bool used[2010][2010];
int ans_sum[2010][2010];
ll sum(int x,int k,bool y){//O(玄学) 
	if (!x) return 0;
	if (x<=2e3&&used[x][k]) return ans_sum[x][k];
	if (k==1) return get_s(x,y);
	if (x<=2e3) used[x][k]=1;
	ll ans=0;
	for (int i=1;i<=size&&q[i]<=k&&q[i]<=x;i++){
		int t=q[i];
		if (!(k%t)) ans+=sum(x/t,t,y);
	}
	if (x<=2e3) ans_sum[x][k]=ans;
	return ans;
}
ll f(int x){//O(16)
	ll ans=0;
	for (int i=1;i<=size;i++) ans+=u[q[i]]*(x/q[i]);
	return ans;
}
int main()
{
	freopen("cyclic.in","r",stdin);
	freopen("cyclic.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	//杜教筛 
	u[1]=1;v[0]=n;v[1]=m;
	for (int i=2;i<=SIZE;i++){
		if (!hash[i]) p[++cnt]=i,u[i]=-1;
		for (int j=1;j<=cnt&&i*p[j]<=SIZE;j++){
			hash[i*p[j]]=1;
			if (i%p[j]) u[i*p[j]]=-u[i];
				else{u[i*p[j]]=0;break;}
		}
	}
	for (int i=1;i<=SIZE;i++) s[i]=s[i-1]+u[i];
	solve(n,0);solve(m,1);
	//质因子分解 
	for (int i=1;i<=k;i++)
	if (u[i]&&!(k%i)) q[++size]=i;
	//分块 
	int l=0,r=0;
	ll last=0,ans=0;
	while (l<n&&l<m){
		r=n/(n/(l+1));
		bool tag=0;
		if (m/(m/(l+1))<r) r=m/(m/(l+1)),tag=1;
		int x=n/r,y=m/r;
		ll now=sum(r,k,tag);
		ans+=x*(now-last)*f(y);
		l=r;last=now;
	}
	printf("%lld\n",ans);
	return 0;
}