2012年国家集训队: 和与积

Delta_Cosh · 2018-04-23 23:37:14 · 题解

As\ we\ know\ that:

(a+b)|ab;

So\ it\ is\ easy\ to\ think\ of\ it:

d=gcd(a,b);

Assume:

a=xd,b=yd;

Then\ there\ goes:

\frac{xyd}{x+y}\ is\ a\ integer;

Obviously\ there\ is

gcd(x,y)=1;

∴gcd(x,x+y)=1,gcd(y,x+y)=1,gcd(xy,x+y)=1;

∴(x+y)|d;

From\ the\ condition.1\ we\ know

\left\{\begin{aligned}xd\leqslant{N}\\ yd\leqslant{N} \\ x+y\leqslant{d}\end{aligned}\right.;

And\ there\ is

d\leqslant{\lfloor{\frac{N}{y}}\rfloor};

So\ the\ answer\ equals

ans=\sum_{x=1}^{\sqrt{N}}\sum_{y=x+1}^{\sqrt{N}}\lfloor{\frac{\lfloor{\frac{N}{y}}\rfloor}{x+y}}\rfloor\ [gcd(x,y)=1];

Use\ Möbius\ inversion\ formula\ and\ make:

xd=x,yd=y;

∴ans=\sum_{d=1}^{\sqrt{N}}\mu(d)\sum_{x=1}^{\frac{\sqrt{N}}{d}}\sum_{y=x+1}^{\frac{\sqrt{N}}{d}}\lfloor{\frac{\lfloor{\frac{N}{yd^2}}\rfloor}{x+y}}\rfloor ;

s=x+y;

∴ans=\sum_{d=1}^{\sqrt{N}}\mu(d)\sum_{y=2}^{\frac{\sqrt{N}}{d}}\sum_{s=y+1}^{2y-1}\lfloor{\frac{\lfloor{\frac{N}{yd^2}}\rfloor}{s}}\rfloor ;

By\ the\ identity\ we\ know\ the\ answer.

代码就不给了已经讲的很清楚了。