九度oj 題目1380：lucky number

題目描述：

每個人有自己的lucky number，小A也一樣。不過他的lucky number定義不一樣。他認為一個序列中某些數出現的次數為n的話，都是他的lucky number。但是，現在這個序列很大，他無法快速找到所有lucky number。既然這樣，他就想找到那些不是lucky number。

輸入：

輸入有兩行.

第一行有n和m。n表示出現次數為n的是lucky number，m表示序列的長度。2<=n<=10,m<=10^6，m%n!=0。

第二行為序列元素，每個元素都是正整數。

輸出：

輸出那個不是lucky number的數。題目保證非lucky number只有一個。

樣例輸入：

2 5
1 1 2 2 3

樣例輸出：

3

發現許多重復幾次的問題用位運算都是很好的辦法，本題把每一個數轉化為32位的二進制數
代碼如下

#include <cstdio>
#include <cstring>

int n, m;
int num;
int wnum[33];

int main(int argc, char const *argv[])
{
    while(scanf("%d %d",&n,&m) != EOF) {

        memset(wnum, 0, sizeof(wnum));
        int t = m % n;
        while(m--){
            scanf("%d",&num);
            for(int j = 0; j < 32; j++) {
                int p = num&1;
                wnum[j] = wnum[j] + p;
                num = num >> 1;
            }
        }
        for(int j = 0; j < 32; j++) {
            wnum[j] = wnum[j] % n;
        }
        
        int ans = 0;
        
        for(int j = 31; j >= 0; j--) {
            ans = ans * 2 + wnum[j]/t;
        }
        printf("%d\n",ans);
    }
    return 0;
}

比如

2 5

1 1 2 2 3

結果是3

編碼得到

　　　　00000001

　　　　00000001

　　　　00000010

　　　　00000010

　　　　00000011（因為數字比較小，省略了前面3位即24個0）

? ? ?求和 00000033

取余 ? ? ?00000011?

出現了m%n = 1次

結果為3

?

另外，設那個不為lucky_number的數為x,有

x % n = sum%n = y
m%n *x +sum(others) = sum

不知道由這兩點能不能啟發出更好的辦法