http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=51196
紫书P320;
题意：给定n个数a1,a2····an,依次求出相邻两个数值和，将得到一个新数列，重复上述操作，最后结果将变为一个数，问这个数除以m的余数与那些数无关？例如n=3,m=2时，第一次得到a1+a2,a2+a3，在求和得到a1+2*a2+a3，它除以2的余数和a2无关。1=<n<=10^5, 2=<m<=10^9
其实就是杨辉三角的某一行有几个能整除m，求C(0,n - 1)，C（1， n - 2)... C（n - 1， n - 1)中那几个能整除m
解题思路：
1、首先我们可以发现对于给定的n其实每项的系数就是C(n-1,i-1)，所以我们只需要找到每项的系数对m取余是否为0即可
2、由于m的取值范围为10^9,所以我们只需要筛选 √(10^9)的素数，然后对m进行分解；如果分解后m>1，说明当前m的是原m的一个素数，而且m> √(10^9)，因此我们只需记录它即可
3、由组合数的递推公式C（k, n) = (n - k + 1) / k * C(k - 1， n)，而这道题n = n - 1；首项是一，可以直接从第二项即k = 1: （n - 1 ) - k + 1 / k开始判断是否能整除m，分子能整除素数元素个数就减一，分母能整除就+1，如果对于任意一个素数对应的指数 >= 1，就说明不能整除
收获：
每个整数的唯一分解式项数不多（long long 类型的数值最多20项，前21个素数相乘long long就溢出了）
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int Max = ; int factor[],nfactor[],num_factor,flag_factor[ + ];
int count_prime,prime[Max + ],flag[Max + ];
void get_prime()
{
memset(flag, , sizeof(flag));
count_prime = ;
for(int i = ; i <= Max; i++)
{
if(flag[i] == )
{
flag[i] = ;
prime[++count_prime] = i;
for(int j = ; j <= Max / i; j++)
{
flag[i * j] = ;
}
}
}
} void get_factor(int m)
{
num_factor = ;
memset(nfactor, , sizeof(nfactor));
memset(factor, , sizeof(factor));
for(int i = ; i <= count_prime; i++)
{
if(m < prime[i])
break;
if(m % prime[i] == )
{
factor[num_factor] = prime[i];
while(m % prime[i] == && m)
{
nfactor[num_factor]++;
m = m / prime[i];
}
num_factor++;
if(m == || m == )
break;
}
}
if(m > )
{
factor[num_factor] = m;
nfactor[num_factor]++;
num_factor++;
}
}
bool check(int x, int y)
{
bool check_flag = true;
for(int i = ; i < num_factor; i++)
{
while(x % factor[i] == && x)
{
x = x / factor[i];
nfactor[i]--;
}
while(y % factor[i] == && y)
{
y = y / factor[i];
nfactor[i]++;
}
if(nfactor[i] >= )
{
check_flag = false;
//break; 要不得，即使不能整除，也要约分完，因为下一个受这一个的影响
}
}
return check_flag;
}
int main()
{
int n,m;
get_prime();
while(scanf("%d%d", &n, &m) != EOF)
{
get_factor(m); //对m分解
int cnt = , ends = ;
memset(flag_factor, , sizeof(flag_factor));
for(int i = ; i <= n; i++)
{
if( check(n - i, i) ) //原型就是 (n - 1 - i + 1) / i
{
flag_factor[i + ] = ;
ends = i + ;
cnt++;
}
}
printf("%d\n", cnt);
if(cnt > )
{
for(int i = ; i < ends; i++)
if(flag_factor[i])
printf("%d ", i);
printf("%d", ends);
}
printf("\n");
}
return ;
}