CF27E (2000) (反素数)
admin
2024-03-03 18:40:22
0次

https://codeforces.com/contest/27/problem/E

反素数:

若N <= 2 ^ 31

引理1: 1 ~ N 中的反素数,就是 1 ~ N中约数个数最多的数中 最小 的一个。

引理2: 1 ~ N 中任何数的不同质因子都不会超过 10 个且所有质因子的质数都不会超过                      30。

引理3: \forallx \epsilon [ 1, N ],x 为反素数的必要条件是:x 分解质因数后可以写成

              2^c1 + 3^c2 + 5^c3 + 7^c4 + 11^c5 + 13^c6 + 17^c7 + 19^c8 + 23^c9 + 29^c10,                  且  c1 >= c2 >= c3 >= c4 >= c5 >= c6 >= c7 >= c8 >= c9 >= c10,

              换句话说, x的质因子是连续的若干个最小的质数,并指数单调递减。

 求法:

根据上面的三个引理,我们可以直接DFS,一次确认前 个质数的指数,并满足指数单调递减,总成绩不超过 ,同时记录约数的个 数即可。最后利用 引理1 找到约数个数最多的数里最小的那个数即可。

我们可以把当前走到每一个素数前面的时候列举成一棵树的根节点,然后一层层的去找。找到什么时候停止呢?

1. 当前走到的数字已经大于我们想要的数字了

2. 当前枚举的因子已经用不到了

3. 当前因子大于我们想要的因子了

4. 当前因子正好是我们想要的因子(此时判断是否需要更新最小 ans )

然后 dfs 里面不断一层一层枚举次数继续往下迭代

题目大意:

给你 一个正整数 n,  让你求一个拥有 n 个因子的最小正整数

思路: 

即求因子数一定的最小反素数

代码实现:

#include using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
#define LL long long
#define ULL unsigned long long
#define INF ~0ULLULL p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
ULL n,ans;// 枚举到的素数,当前因子的数量,当前因子总数,上一个素数的幂
void dfs(ULL depth, ULL temp, ULL num, ULL up)  
{if(num > n || depth >= 16) return;if(num == n && ans > temp){ans = temp; return;}for (ULL i = 1; i <= up; i ++ ){if(temp / p[depth] > ans) break;dfs(depth + 1, temp *= p[depth], num * (i + 1), i);}
}void solve()
{cin >> n;ans = INF;dfs(0, 1, 1, 64);cout << ans << endl;
}int main()
{IOSint T = 1;//cin >> T;while(T --){solve();}return 0;
}

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...