P1447

发表于 分类于
[NOI2010] 能量采集

[NOI2010] 能量采集

我们知道对于 $(i,j)$，它有 $d=\gcd(i,j)$，且 $(i/d,j/d)$ 是对应直线上第一个点，下一个点就是该点坐标两倍，再下一个就是三倍，以此类推。

因此 $(i,j)$ 前的点数为 $\gcd(i,j)-1$，答案就是：

$$
\begin{aligned}
& \sum_{i=1}^{n}\sum_{j=1}^{m}\left(2(\gcd(i,j)-1)+1\right)
\\
=& \sum_{i=1}^{n}\sum_{j=1}^{m}\left(2\gcd(i,j)-1\right)
\\
=& 2\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)-nm
\\
=& 2\sum_{k=1}\varphi(k)\left\lfloor\dfrac{n}{k}\right\rfloor\left\lfloor\dfrac{m}{k}\right\rfloor-nm
\end{aligned}
$$

直接 $O(n)$ 预处理出 $\varphi$ 前缀和，线性或数论分块就完事了。

闲着没事可以杜教筛 $O(n^{2/3})$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<cstdio>
#define ll __int128
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

const ll N=2e6;

ll n,m,cnt;
ll prime[N+5],phi[N+5],sphi[N+5];
bool f[N+5];

inline void Init() {
  f[1]=1;phi[1]=1;
  for(ll i=2;i<=n;i++) {
    if(!f[i]) {prime[++cnt]=i;phi[i]=i-1;}
    for(ll j=1;j<=cnt&&i*prime[j]<=n;j++) {
      f[i*prime[j]]=1;
      if(i%prime[j]==0) {
        phi[i*prime[j]]=phi[i]*prime[j];break;
      }
      phi[i*prime[j]]=phi[i]*phi[prime[j]];
    }
  }
  for(ll i=1;i<=n;i++) sphi[i]=sphi[i-1]+phi[i];
}

int main() {

  n=read();m=read();if(n<m) swap(n,m);Init();

  ll ans=-n*m;
  for(ll i=1,j;i<=n&&i<=m;i=j+1) {
    j=min(n/(n/i),m/(m/i));ans=ans+2*(sphi[j]-sphi[i-1])*(n/i)*(m/i);
  }

  write(ans);

  return 0;
}