【dfs分解质因数】CF27E

水深无声 2024-03-23 00:38 14阅读 0赞

[Problem - 27E - Codeforces][]

题意：

![f3dff0b801414e46be12e008fff1f34f.png][]

思路：

爆搜分解质因子的模板题，记录一下板子

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int mxv=1e6+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    int N,len=0;
    int ans=1e18;
    int vis[mxn];
    int prime[mxn];
    
    void P_init(int n){
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i;
            for(int j=1;i<=n/prime[j];j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
    }
    void dfs(int now,int k,int last,int cnt){
        if(cnt>N) return;
        if(now<=0ll) return;
        if(now>ans) return;
        if(k>16) return;
        if(cnt==N){
            ans=now;
            return;
        }
        for(int i=1;i<=last;i++){
            dfs(now*=prime[k],k+1,i,cnt*(i+1));
        }
    }
    void solve(){
        cin>>N;
        dfs(1ll,1,64,1);
        cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
        P_init(1e6);
    	while(__--)solve();return 0;
    }

[Problem - 27E - Codeforces]: https://codeforces.com/problemset/problem/27/E
[f3dff0b801414e46be12e008fff1f34f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/924cf253b6414b62a5fa47a3558a42ee.png

发表评论取消回复

表情：

评论列表（有 0 条评论，14人围观）

还没有评论，来说两句吧...

相关阅读

相关【dfs分解质因数】CF27E

[Problem - 27E - Codeforces][] 题意： ![f3dff0b801414e46be12e008fff1f34f.png][] 思路：爆搜分

水深无声/ 2024年03月23日 00:38/ 0 赞/ 15 阅读

相关质因数分解

一道清华的复试题，我先后看了两份代码，收获匪浅，分别摘自下面两个博客： [https://blog.csdn.net/Little\_Kid\_Kang/article/de

深藏阁楼爱情的钟/ 2023年03月14日 05:54/ 0 赞/ 167 阅读

相关分解质因数

上一篇博客：[质数的筛法][Link 1] > 写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果

Love The Way You Lie/ 2022年10月22日 04:12/ 0 赞/ 240 阅读

相关分解质因数

public class DecomposePrimeFactor \{ public final static int NUM = 154; public static vo

Dear 丶/ 2022年09月30日 06:22/ 0 赞/ 235 阅读

相关分解质因数

问题描述　　求出区间\[a,b\]中所有整数的质因数分解。输入格式　　输入两个整数a，b。输出格式　　每行输出一个数的分解，形如k=a1\a2\a3...(

超、凢脫俗/ 2022年08月05日 02:54/ 0 赞/ 279 阅读

相关分解质因数

题目内容：每个非素数（合数）都可以写成几个素数（也可称为质数）相乘的形式，这几个素数就都叫做这个合数的质因数。比如，6可以被分解为2x3，而24可以被分解为2x2x2x3。

灰太狼/ 2022年07月03日 18:20/ 0 赞/ 270 阅读

相关分解质因数

分解质因数当无法分解是输出“no answer” <table style="font-size:12px; color:rgb(51,51,51); line-heig

淩亂°似流年/ 2022年06月06日 11:42/ 0 赞/ 300 阅读

相关分解质因数

问题描述　　求出区间\[a,b\]中所有整数的质因数分解。输入格式　　输入两个整数a，b。输出格式　　每行输出一个数的分解，形如k=a1\a2\a3...(

电玩女神/ 2022年06月01日 13:52/ 0 赞/ 307 阅读

相关质因数分解

讲一个数分解为几个质数相乘的结果 ![70][] include<cstdio> include<cmath>

末蓝、/ 2022年05月28日 07:58/ 0 赞/ 331 阅读

相关分解质因数

void solution(int num) { int i = 2; while (num != 1) { i

╰半夏微凉°/ 2022年05月09日 01:46/ 0 赞/ 337 阅读