首相想到的就是搜索啦。。。。。
不过目测会超时啊。。。。那么该怎么办呢，，怎么办呢
为什么搜索这么慢呢？？
因为有N多重复的，比如说
四个数：1,1,1,1
想要得到余数为2有N多方式，
如果搜索的话每一种方式我们都会计算一次。。。
就存在了大量的重复计算。。那么就记忆化搜索呗。。
前i项能组成哪些余数，，把这些余数对应的点存起来。。
然后扫一遍目前的点，，计算前i+1项又能组成哪些余数。。
于是乎代码就轻而易举的写出来了（很不幸，这种方法和动归竟然扯上边了。。）
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define MAX 10001
int n,s,p[MAX];
bool opt[MAX][101];
void init()
{
cin>>n>>s;
for (int i = 1; i <= n; i++)
{
cin>>p[i];
p[i] = (p[i]%s + s) % s;
}
opt[1][ p[1] ] = true;
}
int main()
{
init();
for (int i = 2; i <= n; i++)
{//前i个数
for (int j = 0; j < s; j++)
{
opt[i][(j+p[i])%s] |= opt[i-1][j];
opt[i][(j+s-p[i])%s] |= opt[i-1][j];
}
}
if ( opt[n][0] == true )
{
cout<<"Divisible";
}
else
{
cout<<"Not divisible";
}
cout<<endl;
return 0;
}
我还想了想，，可不可以二分呢？
从理论上来说是完全可以的，，因为主要只要舍去了重复计算就成了。。
不过我实在想不出怎么用二分来做。。。。。
根据这一性质，我们还可以写出递推式，，
int suan(int i,int j)
{
if ( jisuan[i][j] == true )
{
return opt[i][j];
}
opt[i][j] = suan(i-1,j-p[i]);
jisuan[i][j] = true;
return opt[i][j];
}
再改造一下也成了，
不过看得出要更耗时（大量的调用），更耗内存（多开了个数组辨别是否已经计算）