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

发表于 | 分类于 | | + s

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;
}
------ 本文结束 ------