Dfs

アンチプライム番号-アンチプライム



Anti Prime Number Antiprime



説明
1以上の正の整数nが、n未満で1以上のすべての正の整数のすべての近似数を満たし、nの近似数よりも小さい場合、nはアンチプライム数です。例：1、2、4、6、12、24、これらはすべてアンチプライム番号です。
n以下のアンチプライムの最大数を計算してください。
入力
行の正の整数n。
出力
含まれる整数は1つだけで、アンチプライムの最大数はn以下です。
サンプル入力
1000
サンプル出力
840
促す
データの10％の場合、1≤n≤10^ 3
データの40％について、1≤n≤10^ 6
データの100％の場合、1≤n≤2×10 ^ 9

まず、前向きな解決策についてお話ししましょう。



見つけるのはとても簡単

n以下の最大の素因数は、1〜nの中程度の素因数の最小でなければなりません。



また、n＆lt = 2 e 9 n＆lt = 2e9そして2 ∗ 3 ∗ 5 ∗ 7 ∗ 11 ∗ 13 ∗ 17 ∗ 19 ∗ 23 ∗ 29＆gt 2 e 9 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29＆gt2e9

したがって、1〜nの最大アンチプライムは10を超えません

そして、各素因数の指数は減少している必要があります



前のインデックスよりも大きい素因数インデックスがある場合、2つのインデックスを一緒に交換すると、同じ数の数が少なくなります。

したがって、インデックスをデクリメントする必要があります

次に、ディープサーチを直接検討できます

各素因数のインデックスを列挙します

#include using namespace std inline int read(){ char ch=getchar() int res=0 while(!isdigit(ch))ch=getchar() while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar() return res } #define ll long long const ll inc[12]={1,2,3,5,7,11,13,17,19,23,29,31} ll n ll minn=1e9,mnum=-100000 void dfs(ll now,int k,ll num,int mst){ if(mnum<num){ minn=now,mnum=num } if(mnum==num&&minn>now){ minn=now,mnum=num }// if(k>10)return ll p=now for(int i=1i<=msti++){ if(p*inc[k]>n)break p=p*inc[k] dfs(p,k+1,num*(i+1),i) } } int main(){ n=read() dfs(1,1,1,31) cout<<minn<<' ' }

もちろん、アンチプライム数の数は実際には非常に少ないこともわかります。

次に、テーブルをプレイすることも検討できます

2e9内のすべての反素数を列挙します

調べてみてください。

#include using namespace std #define ll long long ll antip[1000] = {1396755360,1102701600,735134400,698377680,551350800,367567200,294053760,245044800,183783600,147026880,122522400,110270160,73513440,61261200,43243200,36756720,32432400,21621600,17297280,14414400,10810800,8648640,7207200,6486480,4324320,3603600,2882880,2162160,1441440,1081080,720720,665280,554400,498960,332640,277200,221760,166320,110880,83160,55440,50400,45360,27720,25200,20160,15120,10080,7560,5040,2520,1680,1260,840,720,360,240,180,120,60,48,36,24,12,6,4,2,1}// Of course there aren't 1000 here, just open a large array. ll n int main(){ cin>>n for(int i=999i>=0i--){ if(antip[i]>n&&antip[i+1]<n){ cout<<antip[i+1] return 0 } } cout<<antip[0] }