数学+思维，CF1056B - Divide Candies
一、题目
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 | mx^2 + y^2 | mΣ(cnt_x * cnt_y)m(q - 1) + r <= nq = (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;
}