自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:44:45，当前版本为作者最后更新于2023-10-10 19:47:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

数学课想出来的奇怪做法。

以下为方便讨论，令 $m=\dfrac{n}{2}$。

由已知得，对于一个 $m$，其地砖边上的点必然满足以下条件：

• $m|x$ 且 $m|y$；

• $x+y\equiv m\pmod {2m}$；

等价于：

• $m|\gcd(x,y)$；

• $x+y\not\equiv 0\pmod {2m}$；

所以令 $S=\{m|[m|\gcd(x,y)]\}$，$R=\{m|x+y\not\equiv 0\pmod {2m}\}$，$T=S\cap R$，答案即为 $|T|$。

$|T|$ 不好计算，正难则反，令 $U=\complement_ST=\begin{cases}\{m|[m|\gcd(x,y,\frac{x+y}{2})]\}&x+y\equiv 0\pmod 2\\\emptyset&\mathrm{otherwise}\end{cases}$，计算 $|U|$ 即可。答案为 $|S-U|$。

$[1,10^7]$ 以内所有数的因数个数可以对于每个数暴力枚举倍数预处理，令 $A=10^7$，时间复杂度 $O(A\log A)$。但因为常数小并且时限 $3\mathrm{s}$ 所以可以过。

放代码：

#include<bits/stdc++.h>
using namespace std;
int a[10000001];
int main(){
  ios::sync_with_stdio(false);
  for(int i=1;i<=1e7;i++)
    for(int j=1;i*j<=1e7;j++)a[i*j]++; // 预处理
  int t; cin>>t;
  while(t--){
    int x,y,c=0; cin>>x>>y;
    int g=gcd(x,y),m=gcd(x+y>>1,g);
    cout<<a[g]-(x+y&1?0:a[m])<<'\n'; // 计算答案
  }
  return 0;
}