给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.
给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.
一个整数N
如题
对于样例(2,2),(2,4),(3,3),(4,2)
1<=N<=10^7
湖北省队互测
若gcd(a,b)=素数p，则a=px,b=py且gcd(x,y)=1，这样，我们枚举小于n的素数p，对于每个素数p，只需求小于等于n/p的数中互质的数的对数，就是以p为gcd的a,b的对数。要求小于某个数k的数种互质的对数，可考虑欧拉函数（设欧拉函数为f，不会打phi勿喷），则对数等于2(f(1)+f(2)+...+f(k))-1，乘2是因为顺序不同的算两个，减1是因为(1,1)不能算两次。这样我们只需预处理出欧拉函数表，再处理出它的前缀和就可以了。
1 program rrr(input,output); 2 var 3 f:array[0..10000000]of int64; 4 p:array[0..10000000]of boolean; 5 n,m,i,j:longint; 6 ans:int64; 7 begin 8 assign(input,‘r.in‘);assign(output,‘r.out‘);reset(input);rewrite(output); 9 readln(n);m:=n>>1; 10 fillchar(p,sizeof(p),true); 11 for i:=1 to n do f[i]:=i; 12 for i:=2 to n do 13 if p[i] then 14 begin 15 j:=i;while j<=m do begin f[j]:=f[j] div i*(i-1);j:=j+i; end; 16 j:=i<<1;while j<=n do begin p[j]:=false;j:=j+i; end; 17 end; 18 for i:=2 to m do f[i]:=f[i]+f[i-1]; 19 for i:=1 to m do f[i]:=f[i]<<1; 20 ans:=0; 21 for i:=2 to n do if p[i] then ans:=ans+f[n div i]-1; 22 write(ans); 23 close(input);close(output); 24 end.
原文：http://www.cnblogs.com/Currier/p/6480672.html