我们发现，点(i,j)与(0,0)的连线所过整点的数目为\(\gcd(i,j)\)
发现要是想记录每个点的答案并不好算。那么怎么好算呢？
我们来找一找同一直线上的所有点答案的和的关系。先不考虑答案只考虑个数。发现，寻找一个点及其倍数的个数的和更加好算。而且，因为有n和m的限制，那么向下取整的答案一定就是其本身。考虑容斥，我们只需要从大往小更新答案并将答案乘2减1加起来即可。
那么对于一个点及其倍数的答案怎么计算呢？
假设n小于m，那么对于一个小于n的数i，显然它的倍数的个数就是\((n/i)*(m/i)\)，这样一来我们只需要考虑小于n的所有数的个数就能够统计n*m的所有数的答案了。至于为什么\((m-n) *
m\)这一块不用考虑，是因为这里不会再有数容斥它们了，直接统计就行。
所以，答案即为
\[\displaystyle
\sum_{i=1}^{n}num_i*(i*2-1)\]
其中\(\displaystyle
num_i=(n/i)*(m/i)-\sum_{i=2}^{n/i}num_i\)
在代码中一个倒序循环即可，时间复杂度线性。
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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#define int long long
using namespace std;
inline int read(){
int x=0,w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
const int maxn=1e5+10;
int ans[maxn];
signed main(){
int n=read(),m=read(),Ans=0;
if(n>m)swap(n,m);
for(int i=n;i;i--){
ans[i]=(n/i)*(m/i);
for(int j=2;j<=n/i;j++)ans[i]-=ans[i*j];
Ans+=(ans[i]*(i*2-1));
}
printf("%lld",Ans);
return 0;
}
|
