ZOJ2666 Irrelevant Elements [数论]

这是道有意思的题，在LRJ的杂题中有提到，题意是这样的：有n(n<=10^5)个数，每个数在[0,m), m <= 10^9中随机选一个数，对这n个数，做这样的操作，相邻的两个数求和后变成n-1个数，然后迭代到只剩下一个数，对这最后的数%m，问说哪个数是跟最后的数是没有影响的。

设这几个数是a,b,c,d->a+b,b+c,c+d->a+2b+c,b+2c+d->a+3b+3c+d，因此对于这n个数a1,a2,…,an，迭代到最后的ans=C(n-1,0)*a1+C(n-1,1)*a2+C(n-1,2)*a3+…+C(n-1,n-1)*an，因此当C(n-1,i)%m=0, i∈[0,n-1]的时候，ans对于该数是无关的。

因此，需要解决一个这样的问题，判断C(a, b)%m是否等于0，我们知道C(a, b)=a!/b!/(a-b)!，我们可以先筛出sqrt(m)以内的素数，复杂度O(sqrt(m))，然后把m进行质因数分解，复杂度O(logm)，然后把a!,b!,(a-b)!分别素因数(考虑m的素因数就可以了)分解，复杂度O(logm*logn)，然后判断，是否包含m的素因数就可以了，因此最后的复杂度为O(N*logm*logn)，代码如下：

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <map>
using namespace std;

const int MAXN = 100005;
const int MAXM = 1e9 + 5;

//map<int, int> map_n[MAXN];    //N!质因数分解


int n, m;
int s[MAXN];
vector<int> prime;

void make_prime()
{
    prime.clear();
    memset(s, 0, sizeof(s));
    //1...N之前的质数
    //复杂度约等于N*lg(N)
    for(int i = 2; i < MAXN; i++)
    {
        if(s[i] == 0)
        {
            prime.push_back(i);
            for(int j = i + i; j < MAXN; j += i)
                s[j] = 1;
        }
    }
}

void go()
{
    vector<map<int, int> > map_n;
    map<int, int> map_m;    //M的分解
    //分解M
    //复杂度lg(M)
    //初始化
    map_m.clear();
    int t_m = m;
    for(int i = 0; i < prime.size() && prime[i] <= sqrt(m * 1.0); i++)
    {
        int p = prime[i];
        if(t_m % p == 0)
        {
            while(t_m % p == 0)
            {
                map_m[p]++;
                t_m /= p;
            }
        }
    }
    if(t_m != 1)  map_m[t_m]++;

    //分解1...N的阶乘的质因数，这里其实只用分级M的质因数就可以了
    //否则复杂度就是N*O(N)*lg(N)了，O(N)表示N之前的质数
    //复杂度N*lg(M)*lg(N)


    map_n.clear();
    map_n.resize(n + 1);
    for(int i = 0; i <= n; i++)
    {
        //初始化
        //map_n[i].clear();

        int j = i;
        //for(int k = 0; k < prime.size() && prime[k] <= j; k++)
        for(map<int, int>::iterator it = map_m.begin(); it != map_m.end(); it++)
        {
            int N = j, p = it->first;
            if(p > N)  break;
            while(N)
            {
                map_n[i][p] += N / p;
                N /= p;
            }
        }
    }


    vector<int> ans;
    map<int, int>::iterator it;

    //复杂度为N*lg(M)
    //枚举解X

    //printf("count = %d\n", map_m.size());
    for(int i = 0; i <= n; i++)
    {
        //枚举M的质因数
        for(it = map_m.begin(); it != map_m.end(); it++)
        {
            int p = it->first;
            int cnt = it->second;

            if(map_n[n][p] - map_n[i][p] - map_n[n - i][p] < cnt)
                break;
        }
        if(it != map_m.end())  continue;
        ans.push_back(i + 1);
    }

    printf("%d\n", ans.size());

    for(int i = 0; i < ans.size(); i++)
    {
        if(i == 0)  printf("%d", ans[i]);
        else  printf(" %d", ans[i]);
        //printf("%d ", ans[i]);
    }
    printf("\n");

}

int main()
{
    make_prime();
    while(scanf("%d%d", &n, &m) != EOF)
    {
        --n;
        //求C(N, X)%M=0,X=[0, N],解X的个数
        //ready();
        //debug();
        go();
    }
}