我们发现对于一个点(x,y),与(0,0)连线上的点数是gcd(x,y)-1
那么这个点的答案就是2*gcd(x,y)-1,那么最后的答案就是所有点
的gcd值*2-n*m,那么问题转化成了求每个点的gcd值的Σ
也即:Σi<=n Σj<=m gcd(i,j)
那么首先我们知道Σphi(d) d|n=n,所以我们可以将这个式子转化成
Σi<=n Σj<=m Σ d|gcd(i,j) phi(d)
那么对于矩阵n*m来说,我们将phi(d)累加了floor(n/d)*floor(m/d)次
所以对于所有的d,答案就是Σ d<=min(n,m) floor(n/d)*floor(m/d)*phi(d)
我们可以线性筛出欧拉函数表,然后线性的求解。
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
//By BLADEVIL
var
i, j :longint;
prime, mindiv, phi :array[..] of int64;
ans :int64;
n, m :int64;
procedure swap(var a,b:int64);
var
c :int64;
begin
c:=a; a:=b; b:=c;
end;
begin
read(n,m);
if n>m then swap(n,m);
phi[]:=;
for i:= to n do
begin
if mindiv[i]= then
begin
inc(prime[]);
prime[prime[]]:=i;
mindiv[i]:=i;
phi[i]:=i-;
end;
for j:= to prime[] do
begin
if i*prime[j]>m then break;
mindiv[i*prime[j]]:=prime[j];
if i mod prime[j]= then
begin
phi[i*prime[j]]:=phi[i]*prime[j];
break;
end else
phi[i*prime[j]]:=phi[i]*(prime[j]-);
end;
end;
for i:= to n do
ans:=ans+(n div i)*(m div i)*phi[i];
ans:=ans*-n*m;
writeln(ans);
end.