1053: [HAOI2007]反素?cái)?shù)ant

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?4118??Solved:?2453
[Submit][Status][Discuss]

Description

?

　　對(duì)于任何正整數(shù)x，其約數(shù)的個(gè)數(shù)記作g(x)。例如g(1)=1、g(6)=4。如果某個(gè)正整數(shù)x滿足：g(x)>g(i) 0<i<x ，則稱x為反質(zhì)數(shù)。例如，整數(shù)1，2，4，6等都是反質(zhì)數(shù)。現(xiàn)在給定一個(gè)數(shù)N，你能求出不超過(guò)N的最大的反質(zhì)數(shù)么 ？

Input

　　一個(gè)數(shù)N（1<=N<=2,000,000,000）。

Output

　　不超過(guò)N的最大的反質(zhì)數(shù)。

Sample Input

1000

Sample Output

840

HINT

?

Source

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int s[20]; long long n,ans,maxn; int pl[13]={0,2,3,5,7,11,13,17,19,23,29,31,37}; void dfs(long long x,int y,int z){if(z==11) return ;if(y>maxn||y==maxn&&x<ans)maxn=y,ans=x;s[z]=0;while(x*pl[z]<=n&&s[z]<s[z-1]){s[z]++;x*=pl[z];dfs(x,y*(s[z]+1),z+1);} } int main(){cin>>n;s[0]=1000000;dfs(1,1,1);cout<<ans; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/cangT-Tlan/p/9190599.html

與50位技術(shù)專家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的BZOJ(8) 1053: [HAOI2007]反素数ant的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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