CF 543 div3 B Preparation for International Women's Day

  • 题目链接

  • 题意:
  • 输入n个正整数和一个k,询问最多有多少个整数相加可以整除k
  • 思路:

    同余定理
    对于每一个数字,取%k的余数为下标,统计余数的个数 cnt[i]
    例如:\[a = n_1k + c_1 \]
    \[ b = n_2k + c_2 \]
    要使得 \[ a + b \mod k = 0\]
    \[(n_1+n_2) k + c_1+c_2 \mod k = 0\]

    \[ if\quad c_1 + c_2 =0 \quad or \quad c_1 + c_2=k\]

    code

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,k,t,ans=0;
    scanf("%d%d",&n,&k);
    vector<int> cnt(k); // 预先申请k个空间
    for(int i=0;i<n;++i){
        scanf("%d",&t);
        cnt[t%k]++;
    }
    ans += cnt[0]/2;// 余数为0 ,肯定整除k,/2是因为要统计全部之后,再*2
    for(int i=1;i<(k+1)/2;++i){
        ans += min(cnt[i],cnt[k-i]);// i + (k-i) % k == 0 ,取公共的部分min 
    }
    if(k%2==0) ans+=cnt[k/2]/2; // 如果k是偶数
    //由于i<(k+1)/2 ,取不到中间的偶数,即取不到(k/2)这个数字,再判断该数字有多少对,因为 k/2 + k/2 == k;
    printf("%d",ans*2);//ans 是对数, * 2 才是个数
    return 0;
}
上一篇:数论函数相关


下一篇:allegro 演示器件对齐_上下左右居中对齐67