Codeforces 448E - Divisors
2024-09-24 03:27:29
思路：
dfs。注意如果是1，直接返回，因为1的因子还是1。
因为x因子的因子还是x的因子，所以可以事先处理好x因子的因子在x因子中的位置。
不用这个方法也可以，用map映射vector保存因子的因子。
代码1：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem memset(a,b,sizeof(a)) const int N=1e6+;
vector<int>son[N];
vector<ll>t;
ll x;
int cnt=;
void dfs(ll k,ll n){
if(cnt==1e5)return ;
if(n==){
cout<<<<' ';
cnt++;
return ;
}
if(k==){
cout<<t[n]<<' ';
cnt++;
return ;
}else{
for(int i=;i<son[n].size();i++){
dfs(k-,son[n][i]);
if(cnt==1e5)return;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie();
ll k;
cin>>x>>k;
for(ll i=;i*i<=x;i++){
if(x%i==){
if(i*i==x)t.pb(i);
else t.pb(i),t.pb(x/i);
}
}
sort(t.begin(),t.end());
for(int i=;i<t.size();i++){
for(int j=;j<=i;j++)
if(t[i]%t[j]==)son[i].pb(j);
}
dfs(k,t.size()-);
return ;
}
代码2：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem memset(a,b,sizeof(a)) vector<ll>t;
unordered_map<ll,vector<ll>>vc;
ll x;
int cnt=;
void dfs(ll k,ll n){
if(cnt==1e5)return ;
if(n==){
cout<<<<' ';
cnt++;
return ;
}
if(k==){
cout<<n<<' ';
cnt++;
return ;
}
else{
if(n==x){
for(int i=;i<t.size();i++){
dfs(k-,t[i]);
}
}else{
if(vc.find(n)!=vc.end()){
for(auto x:vc[n]){
dfs(k-,x);
if(cnt==1e5)return ;
}
}else{
for(ll i=;i*i<=n;i++){
if(n%i==){
if(i*i==n)vc[n].pb(i);
else vc[n].pb(i),vc[n].pb(n/i);
}
}
sort(vc[n].begin(),vc[n].end());
for(auto x:vc[n]){
dfs(k-,x);
if(cnt==1e5)return ;
}
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie();
ll k;
cin>>x>>k;
for(ll i=;i*i<=x;i++){
if(x%i==){
if(i*i==x)t.pb(i);
else t.pb(i),t.pb(x/i);
}
}
sort(t.begin(),t.end());
if(k==)cout<<x<<endl;
else if(k>=1e5){
if(x==)cout<<<<endl;
else{
for(int i=;i<=1e5;i++)cout<<<<' ';
cout<<endl;
}
}
else dfs(k,x);
return ;
}
最新文章
- 编译原理（简单自动词法分析器LEX）
- HT for Web基于HTML5的图像操作（三）
- java.lang.UnsatisfiedLinkError: Couldn't load hyphenate_av from loader dalvik.system.PathClassLoader
- Maven-010-maven 编译报错：Failure to ... in ... was cached in the local repository, resolution will not be reattempted until the update interval of nexus has elapsed or updates are forced.
- 字典树trie的学习与练习题
- Gridview中将某列的背景设置为绿色
- Windows2008RT搭建VPN服务器
- atitit.无线上网卡 无法搜索WiFi 解决无线路由器信号不能被连接
- PHP程序员的技术成长规划（转）
- MongoDB基础教程系列--第二篇 MongoDB基本操作（一）
- hibernate学习笔记之中的一个（JDBC回想-ORM规范）
- linux内核cfs浅析
- 机器学习之MCMC算法
- C#default关键字(泛型代码中的默认关键字)
- 通过flask的request对象获取url
- Arch Linux中禁用UTC解决双系统时间问题
- Apache Kafka学习 (二) - 多代理(broker)集群
- 25_re模块
- Android百度地图2.0运行定位到当前位置时“服务没有启动”
- 第八章 计时器（DIGCLOCK）