題目描述對于任何正整數(shù)x，其約數(shù)的個數(shù)記作g(x)。例如g(1)=1、g(6)=4。如果某個正整數(shù)x滿足：g(x)>g(i) 0<i<x，則稱x為反質(zhì)數(shù)。例如，整數(shù)1，2，4，6等都是反質(zhì)數(shù)。現(xiàn)在給定一個數(shù)N，你能求出不超過N的最大的反質(zhì)數(shù)么？輸入輸出格式輸入格式： 一個數(shù)N（1<=N<=2,000,000,000）。輸出格式： 不超過N的最大的反質(zhì)數(shù)。輸入輸出樣例輸入樣例#1： 1000 輸出樣例#1： 840 題目

Step 1

這個是在openjudge上（7591）能A的代碼（原題：輸出l~r的所有反素數(shù)），因為那時n<=2e7啊。

當(dāng)然也要講一下原理。對于數(shù)的因子個數(shù)，不得不提唯一分解定理——n=a1^p1*a2^p2*…………其中a為該數(shù)的質(zhì)因數(shù)，p為它的個數(shù)，比如49=7^2，其中a1=7,p1=2。于是因子個數(shù)為（p1+1）*（p2+1）*……（49有2+1=3個因子，1,7,49）。那么搜索的目的就很明顯了，枚舉質(zhì)因子湊數(shù)字，湊出來的那一刻已經(jīng)得到了它的因子個數(shù)！

給質(zhì)數(shù)打個表，打多少呢？前十幾個質(zhì)數(shù)雖然都很小，但乘起來肥腸肥腸恐怖啊（不信你自己試一試），所以后面都不用了。

繼續(xù)剪枝，舉個栗子，2^3*3^2=72,2^2*3^3=108,它們的因子個數(shù)都為（2+1）*(3+1)=12，72明顯小于108，也很明顯如果把3的次方給2勻一個答案更優(yōu)。同樣的道理，2*3=6 < 2*5=10，如果質(zhì)因數(shù)的組合不連續(xù)則一定存在更小的數(shù)比當(dāng)前更優(yōu)。

最后我們畫一棵解答樹，第一層是2^1、2^2、2^3……它們的分支都有3^1、3^2、3^3……之后還有5、7、11等等接著找（具體參考程序，id為第幾個質(zhì)因數(shù)，now是數(shù)的大小，tot是因子數(shù)）。

?

#include<cstdio> #include<algorithm> 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 i=1;now*p[id]<=R;++i) dfs(id+1,now*=p[id],tot*(i+1)); } int main() {scanf("%d%d",&L,&R);dfs(1,1,1);for(int i=1;i<L;++i) maxn=max(maxn,ans[i]);for(int i=L;i<=R;++i)if(ans[i]>maxn){maxn=ans[i];f?printf(","):f=1;printf("%d",i);}if(!f) puts("NO");return 0; }

?

Step 2

如果能做到第一步，你就已經(jīng)有一個不錯的爆搜程序了，但對于2e9的范圍來說還是弱了不少。仔細(xì)讀題，發(fā)現(xiàn)這兩道題還是有點區(qū)別的，我們不必求出這個范圍內(nèi)的所有反素數(shù)，只用找到那個最大的。既然這樣，那我們就直奔答案尋找新的優(yōu)化。更新條件有兩個注意不要漏（估計只有像我這樣頭不好的人才會兩次都寫錯……），之后參考Step 1的剪枝，我們盡量讓小質(zhì)數(shù)的次方數(shù)大，這也就意味著對于2^p1*3^p2*5^p3,滿足p3<=p2<=p1。開個use數(shù)組記錄一下p就好了。

?

1 #include<cstdio> 2 #include<cstdlib> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<cstring> 7 #define ll long long 8 #define inf 1<<29 9 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(tot>maxt||(tot==maxt&&now<ans)) ans=now,maxt=tot; 15 use[id]=0; 16 while(now*p[id]<=n&&use[id]+1<=use[id-1]){ 17 use[id]++; 18 now*=p[id]; 19 dfs(id+1,now,tot*(use[id]+1)); 20 } 21 } 22 int main() 23 { 24 scanf("%d",&n); 25 use[0]=1<<29; 26 dfs(1,1,1); 27 printf("%lld",ans); 28 return 0; 29 }

?

Step 3

用我之前的程序可以打出比較小的表（2e8以內(nèi)），觀察一下，發(fā)現(xiàn)反素數(shù)其實很少，而且越往后它們的間隔越大（147026880~183783600，△=3e7+）。這也就意味著我們不用一個一個數(shù)去枚舉小于它的最大的反質(zhì)數(shù)。于是，先記錄2e9的答案為1396755360，再把它減一輸入程序，不斷重復(fù)該操作與小的表接起來。我們終于打出最后的表了。（不容易啊QAQ~~~~~）

?

1 #include<cstdio> 2 #include<algorithm> 3 #define ll long long 4 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 i=0;i<68;++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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/12mango/p/7592925.html

總結(jié)

以上是生活随笔為你收集整理的luoguP1463:反素数ant（打表心得☆）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。