[COCI2022-2023 #1] Iksevi 题解
FFTotoro
·
·
题解
数学课想出来的奇怪做法。
以下为方便讨论，令 m=\dfrac{n}{2}。
由已知得，对于一个 m，其地砖边上的点必然满足以下条件：
等价于：
所以令 S=\{m|[m|\gcd(x,y)]\}，R=\{m|x+y\not\equiv 0\pmod {2m}\}，T=S\cap R，答案即为 |T|。
$[1,10^7]$ 以内所有数的因数个数可以对于每个数暴力枚举倍数预处理，令 $A=10^7$，时间复杂度 $O(A\log A)$。但因为常数小并且时限 $3\mathrm{s}$ 所以可以过。
放代码：
```cpp
#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;
}
```