网站建设 青岛,seo关键词排名优化怎么样,江西建网站,免费工程项目信息网题目描述对于任何正整数x#xff0c;其约数的个数记作g(x)。例如g(1)1、g(6)4。如果某个正整数x满足#xff1a;g(x)g(i) 0ix#xff0c;则称x为反质数。例如#xff0c;整数1#xff0c;2#xff0c;4#xff0c;6等都是反质数。现在给定一个数N#xff0… 题目描述对于任何正整数x其约数的个数记作g(x)。例如g(1)1、g(6)4。如果某个正整数x满足g(x)g(i) 0ix则称x为反质数。例如整数1246等都是反质数。现在给定一个数N你能求出不超过N的最大的反质数么输入输出格式输入格式
一个数N1N2,000,000,000。输出格式
不超过N的最大的反质数。输入输出样例输入样例#1
1000
输出样例#1
840 题目 Step 1 这个是在openjudge上7591能A的代码原题输出l~r的所有反素数因为那时n2e7啊。 当然也要讲一下原理。对于数的因子个数不得不提唯一分解定理——na1^p1*a2^p2*…………其中a为该数的质因数p为它的个数比如497^2其中a17,p12。于是因子个数为p11*p21*……49有213个因子1,7,49。那么搜索的目的就很明显了枚举质因子凑数字凑出来的那一刻已经得到了它的因子个数 给质数打个表打多少呢前十几个质数虽然都很小但乘起来肥肠肥肠恐怖啊不信你自己试一试所以后面都不用了。 继续剪枝举个栗子2^3*3^272,2^2*3^3108,它们的因子个数都为21*(31)1272明显小于108也很明显如果把3的次方给2匀一个答案更优。同样的道理2*36 2*510如果质因数的组合不连续则一定存在更小的数比当前更优。 最后我们画一棵解答树第一层是2^1、2^2、2^3……它们的分支都有3^1、3^2、3^3……之后还有5、7、11等等接着找具体参考程序id为第几个质因数now是数的大小tot是因子数。 #includecstdio
#includealgorithm
using namespace std;
int maxn,L,R,f,ans[20000010],p[]{0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
void dfs(int id,int now,int tot)
{ans[now]tot;for(int i1;now*p[id]R;i) dfs(id1,now*p[id],tot*(i1));
}
int main()
{scanf(%d%d,L,R);dfs(1,1,1);for(int i1;iL;i) maxnmax(maxn,ans[i]);for(int iL;iR;i)if(ans[i]maxn){maxnans[i];f?printf(,):f1;printf(%d,i);}if(!f) puts(NO);return 0;
} Step 2 如果能做到第一步你就已经有一个不错的爆搜程序了但对于2e9的范围来说还是弱了不少。仔细读题发现这两道题还是有点区别的我们不必求出这个范围内的所有反素数只用找到那个最大的。既然这样那我们就直奔答案寻找新的优化。更新条件有两个注意不要漏估计只有像我这样头不好的人才会两次都写错……之后参考Step 1的剪枝我们尽量让小质数的次方数大这也就意味着对于2^p1*3^p2*5^p3,满足p3p2p1。开个use数组记录一下p就好了。 1 #includecstdio2 #includecstdlib3 #includeiostream4 #includealgorithm5 #includecmath6 #includecstring7 #define ll long long8 #define inf 1299 using namespace std;
10 int n,p[]{0,2,3,5,7,11,13,17,19,23,29,31},use[20];
11 ll maxt,ans;
12 void dfs(ll id,ll now,ll tot)
13 {
14 if(totmaxt||(totmaxtnowans)) ansnow,maxttot;
15 use[id]0;
16 while(now*p[id]nuse[id]1use[id-1]){
17 use[id];
18 now*p[id];
19 dfs(id1,now,tot*(use[id]1));
20 }
21 }
22 int main()
23 {
24 scanf(%d,n);
25 use[0]129;
26 dfs(1,1,1);
27 printf(%lld,ans);
28 return 0;
29 } Step 3 用我之前的程序可以打出比较小的表2e8以内观察一下发现反素数其实很少而且越往后它们的间隔越大147026880~183783600△3e7。这也就意味着我们不用一个一个数去枚举小于它的最大的反质数。于是先记录2e9的答案为1396755360再把它减一输入程序不断重复该操作与小的表接起来。我们终于打出最后的表了。不容易啊QAQ~~~~~ 1 #includecstdio2 #includealgorithm3 #define ll long long4 using namespace std;5 int n,biao[]{1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,554400,665280,720720,1081080,1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640,10810800,14414400,17297280,21621600,32432400,36756720,43243200,61261200,73513440,110270160,122522400,147026880,183783600,245044800,294053760,367567200,551350800,698377680,735134400,1102701600,1396755360};6 int main()7 {8 scanf(%d,n);9 for(int i0;i68;i)
10 if(biao[i]n){
11 printf(%d,biao[i-1]);
12 return 0;
13 }
14 printf(%d,biao[67]);
15 return 0;
16 } 转载于:https://www.cnblogs.com/12mango/p/7592925.html
