尧图网页设计 
题目P1734 最大约数和题目描述选取和不超过S SS的若干个不同的正整数使得所有数的约数不含它本身之和最大。输入格式输入一个正整数S SS。输出格式输出最大的约数之和。输入输出样例 #1输入 #111输出 #19说明/提示【样例说明】取数字4 44和6 66可以得到最大值( 1 2 ) ( 1 2 3 ) 9 (12)(123)9(12)(123)9。【数据规模】对于100 % 100 \%100%的数据1 ≤ S ≤ 1000 1 \le S \le 10001≤S≤1000。代码一维数组#includebits/stdc.husingnamespacestd;constintM100010;intV,n,cnt,w[M],v[M],f[M];intmain(){cinV;for(inti1;iV;i){cnt;v[cnt]i;for(intj1;ji;j){if(i%j0){w[cnt]j;}}}ncnt;for(inti1;in;i)for(intjV;jv[i];j--)f[j]max(f[j],f[j-v[i]]w[i]);coutf[V];return0;}结果 【题解-洛谷】P1734 最大约数和
题目P1734 最大约数和题目描述选取和不超过S SS的若干个不同的正整数使得所有数的约数不含它本身之和最大。输入格式输入一个正整数S SS。输出格式输出最大的约数之和。输入输出样例 #1输入 #111输出 #19说明/提示【样例说明】取数字4 44和6 66可以得到最大值( 1 2 ) ( 1 2 3 ) 9 (12)(123)9(12)(123)9。【数据规模】对于100 % 100 \%100%的数据1 ≤ S ≤ 1000 1 \le S \le 10001≤S≤1000。代码一维数组#includebits/stdc.husingnamespacestd;constintM100010;intV,n,cnt,w[M],v[M],f[M];intmain(){cinV;for(inti1;iV;i){cnt;v[cnt]i;for(intj1;ji;j){if(i%j0){w[cnt]j;}}}ncnt;for(inti1;in;i)for(intjV;jv[i];j--)f[j]max(f[j],f[j-v[i]]w[i]);coutf[V];return0;}结果