Codeforces 1056B (剩余系 / 找规律)

Codeforces 1056B
题意:求$m | (x^2+y^2), 1 \leq x, y \leq n$的$(x,y)$个数。($m \leq 2000, n \leq 10^9$)

其实观察题目样例解释可以发现,互质对只有$(1,2), (1,3), (3, 4)$。其他的都是在$\leq n$范围类的倍数。特殊的$(5,5)$我们也将其列入。观察这些数对都是小于$m$的,不妨将$(5,5)$记为$(0,0)$,这些数对都满足$m | (x^2+y^2), 0 \leq x, y < m$,所以我们可以尝试在$m$范围内枚举这样的数对,然后再统计在$n$范围内的数量即可。

数学方法:
$m | (x^2+y^2) \Leftrightarrow (x^2+y^2) \mod m = 0 $
那么在$m​$范围类枚举这样的数对,然后在$n​$范围内统计个数即可。

知识点:
1、题目中一个数据大一个数据小,肯定要枚举小的那个数据
2、找规律依题意,有可能不是 $ O(1) $ 方法。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
LL n, m;
LL hh[1005][1005];
LL calc(LL l) {return (n - l) / m + (l > 0);} // 不包含本身所以加上 (l > 0)
void clean() {
ms(hh, 0);
}
int solve() {
clean();
cin >> n >> m;
for (LL i = 0; i < m; ++i)
for (LL j = 0; j < m; ++j) if ((i * i + j * j) % m == 0) hh[i][j] = 1;
LL ans = 0;
for (LL i = 0; i <= min(n, m - 1); ++i)
for (LL j = 0; j <= min(n, m - 1); ++j) if (hh[i][j]) ans += calc(i) * calc(j);
cout << ans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------