一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 1056B - Codeforces

---

二、解题报告

1、思路分析

考虑i^2 + j^2 | m

而m的余数有限，且m很小

我们枚举两重循环，都枚举m的余数，分别记为x，y

如果x ^ 2 + y ^ 2 | m

我们就计算1~n中余数为x和y的数字个数cnt_x和cnt_y, 余数对(x, y)贡献就是cnt_x和cnt_y

2、复杂度

时间复杂度：O(M^2) 空间复杂度：O(1)

3、代码详解

 ​

#include <bits/stdc++.h>
using PII = std::pair<int, int>;
using i64 = long long;
using i128 = __int128;
std::ostream& operator<< (std::ostream& out, i128 x) {
    std::string s;
    while (x) s += ((x % 10) ^ 48), x /= 10;
    std::reverse(s.begin(), s.end());
    return out << s;
}

void solve() {
    i64 res = 0, N, M;
    std::cin >> N >> M;
    for (int i = 1; i <= M; i ++ )
        for (int j = 1; j <= M; j ++ ) 
            if ((i * i + j * j) % M == 0) {
                i64 cnt_i = (N - i + M) / M, cnt_j = (N - j + M) / M;
                res += cnt_i * cnt_j;
            }
    std::cout << res;
    /*
        a^2 + b^2 | m
        (a mod m)^2 + (b mod m)^2 | m

        x^2 + y^2 | m
        Σ(cnt_x * cnt_y)

        m(q - 1) + r <= n
        q = (n - r + m) / m

    */
}


int main () {
    std::ios::sync_with_stdio(false);   std::cin.tie(0);  std::cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_ --)
        solve();
    return 0;
}