首页 > 代码库 > 数论 - 整除问题 --- 整数集合中找出3的最大倍数
数论 - 整除问题 --- 整数集合中找出3的最大倍数
Mean:
题目描述：给一个包含非负整数的数组(长度为n)，找出由这些数字组成的最大的3的倍数，没有的话则输出impossible。
analyse:
首先想到的就是直接暴力，这是最蠢的方法，数据一大的话，必会TLE。
直接用蛮力的话，生成所有的组合，为 2^n个，对每个数字再进行比较判断，需要 O(n)的时间，因为n可能会比较大，需要每个位的比较。
总的时间复杂度为O(n * 2^n).
那么到底要怎么做呢？
首先我们来了解几个数学知识：
1)一个数n对m取余的余数为a1，b为n的每一位数字的和，那么有：n%m=b%m=a1。
例如，如果对于151和它的各位之和7，对于3的余数都为1。
2)一个数是3的倍数，则该数字各位总和为3的倍数。
例如，让我们考虑8760，它是3的倍数，因为数字总和为8 + 7 + 6 + 0 = 21，这是3的倍数。
推论：一个数是3的倍数，那么构成他的数字的排列为一个新的数字，这个数字仍然是3的倍数。
Time complexity：O(nlongn)
Source code：
暴力代码：
// Memory Time// 1347K 0MS// by : Snarl_jsb// 2014-09-10-09.28#include<algorithm>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<vector>#include<queue>#include<stack>#include<map>#include<string>#include<climits>#include<cmath>#define N 100#define MAXN 100#define LL long longusing namespace std;long long n,summ;long long a[N];bool cmp(LL a,LL b){ return a>b;}LL ans[N];LL idx;LL Max;void work(int* b,int n){ LL sum1=0; for(int i=0;i<n;i++) { sum1+=a[b[i]]; } if(sum1%3==0&&sum1>Max) { Max=sum1; idx=n; for(int i=0;i<n;i++) { ans[i]=a[b[i]]; } }}void _gen_comb(int* a,int s,int e,int m,int& cnt,int* temp){ int i; if (!m) work(temp,cnt); else for (i=s;i<=e-m+1;i++){ temp[cnt++]=a[i]; _gen_comb(a,i+1,e,m-1,cnt,temp); cnt--; }}void gen_comb(int n,int m){ int a[MAXN],temp[MAXN],cnt=0,i; for (i=0;i<n;i++) a[i]=i+1; _gen_comb(a,0,n-1,m,cnt,temp);}int main(){// freopen("C:\\Users\\ASUS\\Desktop\\cin.cpp","r",stdin);// freopen("C:\\Users\\ASUS\\Desktop\\cout.cpp","w",stdout); while(~scanf("%I64d",&n)) { LL sum=0; for(int i=1;i<=n;++i) { scanf("%I64d",a+i); sum+=a[i]; } summ=sum;// cout<<sum<<endl; sort(a+1,a+1+n,cmp); if(!(sum%3)) { for(int i=1;i<=n;i++) { printf("%I64d",a[i]); } puts(""); continue; } bool flag=0; for(int i=n;i>1;--i) { sum-=a[n]; if(!(sum%3)) { for(int j=1;j<i;j++) printf("%I64d",a[j]); puts(""); flag=1; break; } } if(flag) continue; Max=LONG_LONG_MIN; for(int i=n;i>=1;--i) { gen_comb(n,i); } if(sizeof(ans)==0) { puts("impossible\n"); continue; } sort(ans,ans+idx,cmp); for(int i=0;i<idx;++i) { printf("%I64d",ans[i]); } puts(""); } return 0;}
数学方法：
// Memory Time// 1347K 0MS// by : Snarl_jsb// 2014-09-10-11.37#include<algorithm>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<vector>#include<queue>#include<stack>#include<map>#include<string>#include<climits>#include<cmath>#define N 10000#define LL long longusing namespace std;LL n;LL a[N];LL ans[N];LL n1,n2,n3;LL q1[N],q2[N],q3[N];bool cmp(LL a,LL b){ return a>b;}int main(){// freopen("C:\\Users\\ASUS\\Desktop\\cin.cpp","r",stdin);// freopen("C:\\Users\\ASUS\\Desktop\\cout.cpp","w",stdout); while(scanf("%d",&n)!=EOF) { n1=n2=n3=0; LL sum=0; for(LL i=1;i<=n;i++) { scanf("%d",&a[i]); sum+=a[i]; if(a[i]%3==0) { q1[++n1]=a[i]; } else if(a[i]%3==1) q2[++n2]=a[i]; else q3[++n3]=a[i]; } if(sum%3==0) { sort(a+1,a+1+n); for(int i=n;i>=1;--i) { printf("%d",a[i]); } puts(""); continue; } sort(q1+1,q1+1+n1,cmp); sort(q2+1,q2+1+n2,cmp); sort(q3+1,q3+1+n3,cmp); if(sum%3==1) { if(n2>=1) { n2--; } else if(n3>=2) { n3-=2; } else { puts("impossible\n"); continue; } } else if(sum%3==2) { if(n1>=2) { n1-=2; } else if(n2>=1) { n2--; } else { puts("impossible\n"); continue; } } LL idx=0; for(int i=1;i<=n1;++i) { ans[++idx]=q1[i]; } for(int i=1;i<=n2;++i) { ans[++idx]=q2[i]; } for(int i=1;i<=n3;++i) { ans[++idx]=q3[i]; } sort(ans+1,ans+1+idx,cmp); for(int i=1;i<=idx;i++) { printf("%I64d",ans[i]); } puts(""); } return 0;}
数论 - 整除问题 --- 整数集合中找出3的最大倍数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。