判断整除
总时间限制: 1000ms 内存限制: 65536kB
描述
一个给定的正整数序列，在每个数之前都插入+号或-号后计算它们的和。比如序列：1、2、4共有8种可能的序列：
(+1) + (+2) + (+4) = 7
(+1) + (+2) + (-4) = -1
(+1) + (-2) + (+4) = 3
(+1) + (-2) + (-4) = -5
(-1) + (+2) + (+4) = 5
(-1) + (+2) + (-4) = -3
(-1) + (-2) + (+4) = 1
(-1) + (-2) + (-4) = -7
所有结果中至少有一个可被整数k整除，我们则称此正整数序列可被k整除。例如上述序列可以被3、5、7整除，而不能被2、4、6、8……整除。注意：0、-3、-6、-9……都可以认为是3的倍数。
输入
输入的第一行包含两个数：N（2 < N < 10000）和k(2 < k< 100)，其中N代表一共有N个数，k代表被除数。第二行给出序列中的N个整数，这些整数的取值范围都0到10000之间（可能重复）。
输出
如果此正整数序列可被k整除，则输出YES，否则输出NO。（注意：都是大写字母）
样例输入
3 2
1 2 4
样例输出
NO
一次计算十个数
然后二分，或者多路计算
求 K以内的所有素数
对结果尽行检测，虽然数量级改进不大，但是计算量应该可以大大减轻
100内的 素数，只有25个
我的思路来写的，不知道可否，主要是用集合来去重，消除很大一部分重复数据，从而来加速运算结果
#include "iostream"
#include "set"
using namespace std;
int a[10005];
int main() {
int N,K;
// 输入
while (cin>>N>>K) {
for (int i=0; i<N; i++) {
cin>>a[i];
}
// 两个集合，用于保存运算结果，集合自带去重特性
set<int> *result = new set<int>();
set<int> *old = new set<int>();
// 最开始的时候集合中只有一个
old->insert(0);
// 依次遍历每一个数，计算结果
for (int i=0; i<N; i++) {
// 遍历上一次计算的结果，并与当前取的数进行 ＋ － 操作，结果放入到新的集合中
set<int>::reverse_iterator it;
for(it=old->rbegin();it!=old->rend();it++) {
result->insert(*it + a[i]);
result->insert(*it - a[i]);
}
// 老的数据集合可以删掉了，如果对时间性能有要求的话这行可以注释掉
delete(old);
// 轮换
old = result;
result = new set<int>();
}
// 遍历最终的结果，判断是否可以整除
set<int>::reverse_iterator it;
bool isTrue = false;
for(it=old->rbegin();it!=old->rend();it++) {
// cout<<*it<< " ";
if (*it % K == 0) {
isTrue=true;
break;
}
}
//输出结果
if (isTrue) {
cout<<"YES"<<endl;
} else {
cout<<"NO"<<endl;
}
}
return 0;
}
#include
#include
#include
int mem[10000];
int a[10000];
int IsDiv(int sum,int k,int n,int i)
{
int ans;
if(mem[i]>0) return mem[i];
if(i==n)
{
if(sum%k==0) return 1;
else return 0;
}
if(abs(sum)>=k)
{
sum=sum%k;
}
ans+=IsDiv(sum+a[i+1],k,n,i+1);
ans+=IsDiv(sum-a[i+1],k,n,i+1);
mem[i]=ans;
return ans;
}
int main()
{
int n,k,i,j;
while(~scanf("%d%d",&n,&k))
{
memset(mem,-1,sizeof(mem));
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
if(!IsDiv(0,k,n,0)) printf("NO\n");
else printf("YES\n");
}
return 0;
}