BZOJ2818

BZOJ网站貌似没做下去了。 简单说一下题目，思路。 给定整数N，求1<=x,y<=N且gcd(x,y)为素数的数对(x,y)有多少对。

思路：直接去枚举1-N中的素数，x和y题目没有说大小，假定我们先去求的y=$p\ast a$，x=$p\ast b$，gcd(a,b)=1，要求的话直接a=[1,n/p]每个数的欧拉函数，无大小关系乘以一个2即可，但是考虑到1的欧拉函数就是1，就是本身，乘2后结果减1。用一个数组存在欧拉函数的前缀和。