2818: Gcd
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 2170 Solved: 979
[Submit][Status][Discuss]
Description
给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.
Input
一个整数N
Output
如题
Sample Input
4
Sample Output
4
HINT
hint
对于样例(2,2),(2,4),(3,3),(4,2)
1<=N<=10^7
Source
题解：一个素数+欧拉函数题，其实就是先求出1-N的欧拉函数，然后枚举1-N之间的质数，然后简单加加就可以了
对了——每次加入的时候在乘2之后记得减1——因为有且仅有一种情况两个数字相同——那就是两个数字刚好等于那个质数，别的没了
/**************************************************************
Problem:
User: HansBug
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ var
i,j,k,l,m,n:longint;ans:int64;
a,b:array[..] of longint;
c:array[..] of int64;
procedure phi;
var i,j:longint;
begin
m:=;a[]:=;
for i:= to n do
begin
if a[i]= then
begin
inc(m);
b[m]:=i;
a[i]:=i-;
end;
for j:= to m do
begin
if (i*b[j])>n then break;
if (i mod b[j])= then
a[i*b[j]]:=a[i]*b[j]
else
a[i*b[j]]:=a[i]*(b[j]-);
end
end;
end;
begin
readln(n);m:=;phi;ans:=;
for i:= to n do c[i]:=c[i-]+int64(a[i]);
for i:= to m do inc(ans,c[n div b[i]]*-);
writeln(ans);
readln;
end.