ZZULIOJ 2502: 建国与两个数组 (思维题 详细题解)

这个题目是一道非常有意思的题目, 有很多种解法, 在这儿我只讨论一种最容易直观理解的解法
考虑一下, 因为求两数和为k的倍数, 我们就可以把每个数都先%k, 分为了k类, 用a,b保存起来, a[i]即为n中%k后为i的数量, b[i]同理
这样我们不难发现, 凑k的倍数就简化成了凑k, 那固然只能取i和k-i, 例如k= 7, a[2]=2, 那么只能取b[5], 一共则有a[2]*b[5]种凑法
所以答案即为sum(a[i]*b[k-i]), 注意对a[0]和b[0]的特殊处理

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const LL maxn = 1010;

int main()
{
    int n, m, k, T;
    int a[maxn], b[maxn];
    cin >> T;
    while(T--){
        cin >> n >> m >> k;
        //通过%7把a,b分为余数为0..k, k类
        ms(a, 0); ms(b, 0);
        for(int i = 1; i <= n; i++)
            a[i%k]++;
        for(int i = 1; i <= m; i++)
            b[i%k]++;

        LL sum = LL(a[0]*b[0]); //一定要加强转
        for(int i = 1; i <= k; i++)
            sum += a[i]*b[k-i]; //直接相乘

        cout << sum << endl;
    }

	return 0;
}