郑轻周赛（7）复盘，C题
前言：
这道题在比赛过程中没有写出来，呸，是根本就没写。。思考了一下就跳过去了，这道题难度对我来说挺大的。看答案的时候，发现题目的分析是我以前遇到过但是不会的知识点，现在又遇见还是不会，血的教训。。。更加坚定我写题解的决心了，不再当懒狗。。
题目：
问题C: 分糖果
时间限制: 1 Sec 内存限制: 128 MB
题目描述
输入
输入一行包含两个整数 n(1 <= n <= 109),m(1 <= m <= 103) 。输出
输出一个整数，糖果可以恰好平均分给 m 个队员的区域数量。sjjj、jljj和ylgg成功夺得首块CCPC银牌，这是个值得纪念的时刻。sjjj很开心，决定给ACM的队员们分些糖果吃(据说吃了sjjj的糖可以拿牌子)。
已知sjjj手里有无数块糖果(有钱任性)，队里有 m 个人，sjjj不想简简单单的分糖果，于是想了个法子，他决定将一些糖果放到一个 n 行 n 列二维矩阵中，第 i 行，第 j 列的区域内就放 i^2 + j^2 个糖果。
sjjj想让你告诉他 n * n 个区域有多少个区域内的糖果可以恰好平均分给 m 个队员。(sjjj当然知道结果，他就是想单纯的为难你）
样例输入 Copy
6 5
样例输出 Copy
13
提示
如下区域内的糖果可以恰好平均分给队员
-
(1,2)和(2,1)，1^2 + 2^2=5，恰好可以平均分给5个队员;
-
(1,3)和(3,1);
-
(2,4)和(4,2);
-
(2,6)和(6,2);
-
(3,4)和(4,3);
-
(3,6)和(6,3);
-
(5,5);
分析：
比赛的时候，因为水平有限，只想到了二重循环遍历（最傻的方法），而且我知道这样写会超时，所以没写。
将题⽬转化⼀下，给两个整数n，m，问有多少种情况满⾜
将式⼦转化⼀下，变可以得到如下结果 (i^2 +j^2 ) % m = (i^2 % m +j^2 % m) %m = (( i% m * i% m) + ( j% m * j% m)) % m
如此我们就只需要统计余数0~m-1有多少个即可，⽤cnt数组存储个数
然后枚举余数i，j，计算答案
我的题解：
比赛没写。。
答案题解：
#include<iostream>
using namespace std;
int cnt[N];
int main()
{
IOS; cin.tie(0);//不知道啥意思
int n, m;
scanf("%d%d", &n, &m);
//统计余数的个数
for (int i = 0; i < m; i ++ )
cnt[i] = n / m;
//对余下的数单独统计
for (int i = n; i > n - n % m; i -- )
cnt[i % m] ++;
LL ans = 0;
//枚举余数
for (int i = 0; i < m; i ++ )
{
for (int j = 0; j < m; j ++ )
{
if ((i * i + j * j) % m == 0)
ans += 1ll * cnt[i] * cnt[j];
}
}
printf("%lld\n", ans);
return 0;
}
emmmmm，这答案我是真没看懂。。。写这篇主要是为了学一下分析。等后面水平上来再回头看吧。总结：
取模公式，印象来说，以前的比赛大概有有三道题涉及这个知识点，非常重要。
例如：
（a+b)%p=(a%p+b%p)%p
（a-b)%p=(a%p-b%p)%p
（a*b)%p=(a%p)*(b%p)%p
滴滴公司福利 894人发布
投递滴滴等公司9个岗位 >
查看6道真题和解析