第一周算法设计与分析:C : 200和整数对之间的情缘

C : 200和整数对之间的情缘

Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 97 Solved: 25

Description

给你一个有N个整型数字的序列A，整数对(i, j)满足以下条件，请问能找到多少这样的整数对：1 ≤ i, j ≤ N
Ai−Aj 是200的整数倍

Input

第一行输入N，第二行输入N个整数分别A1 A2 … AN

• 2 ≤ N ≤ 2 × 105

• 1 ≤ Ai ≤ 109

• 所有输入均为整型(int)

Output

输出答案并换行

Sample Input

6
123 223 123 523 200 2000

Sample Output

4

Hint

一、分析与程序

第一步：可以通过mod200的同余类数组来统计mod200后的余数相同的数个数。
在这样的一类里面，Ai-Aj，必然能被200整除
补充：mod200同余类例子：123,323,523,这三个数就是一个mod200的同余类，余数都为123。该类数字随机抽两个数相减必然能被200整除。
第二步：对每一个同余类随机抽两个,即求Cn2组合数，并求和即可

#include<iostream>
using namespace std;
int arr[200];//200个同余类构建数组。我们也可以称为桶
int main()
{
    int n,num;
    while(cin>>n)
    {
        for(int i=0;i<n;i++)
        {
            cin>>num;
            arr[num%200]++;//累计mod200后余数为num%200的同余类内数字个数
        }
        long long ans=0;
        for(int i=0;i<200;i++) ans+=arr[i]*(arr[i]-1);//求组合数,后对组合数求和，除2我放在下一行
        cout<<ans/2<<endl;
    }
    return 0;
}