记录编号	357719	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]艾米利亚的魔法融合	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C	运行时间	1.413 s
提交时间	2016-12-12 00:29:00	内存使用	51.79 MiB

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//aimiliyademagicmix
#define MXN 10000001
char vis[MXN];
int miu[MXN];
int primes[1000000];
int tot;
void pre(int n)
{
	int i, j;
	miu[1] = 1;
	for(i = 2; i <= n; i++)
	{
		if(!vis[i])
		{
			primes[tot++] = i;
			miu[i] = -1;
		}
		for(j = 0; j < tot; j++)
		{
			int k = primes[j]*i;
			if(k > n)break;
			vis[k] = 1;
			if(i%primes[j])miu[k] = -miu[i];
			else break;
		}
	}
	for(i = 1; i <= n; i++)miu[i] += miu[i-1];
}
typedef long long LL;
LL square(int x, ...)
{
	return (LL)x*(LL)x;
}
typedef LL (*meta)(int, void*);
LL calc(int n, meta f)
{
	LL r = 0;
	int i, j;
	for(i = 1; i <= n; i = j+1)
	{
		j = n/(n/i);
		r += (miu[j]-miu[i-1])*f(n/i, square);
	}
	return r;
}
int main()
{
	freopen("aimiliyademagicmix.in", "r", stdin);
	freopen("aimiliyademagicmix.out", "w", stdout);
	int n;
	scanf("%d", &n);
	pre(n);
    printf("%lld\n", calc(n, calc));
	return 0;
}