| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 444707 | definitelynotmee | Toys (CEOI18_toy) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MOD = 1e9 + 7;
const int MAXN = 1e6+1;
int power(int in, int exp){
int cur = in;
int resp = 1;
for(int i = 0; i < 31; i++){
if((1<<i)&exp){
resp*=cur;
}
cur*=cur;
}
return resp;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
if(n==1){
cout << 1 << '\n' << 0 << '\n';
return 0;
}
vector<int>fat;
vector<int>num;
for(int i = 2; i <= sqrt(n); i++){
if(n%i == 0){
fat.push_back(i);
num.push_back(0);
while(n%i == 0){
num[num.size()-1]++;
n/=i;
}
}
}
if(n!=0)
fat.push_back(n),num.push_back(1);
map<vector<int>,vector<pii>> m;
vector<int> base(fat.size(),0);
m[base] = {{0,0}};
function<void(int,int,vector<int>&, vector<pii>&)> choice = [&](int id, int cur, vector<int>&v, vector<pii>& resp){
if(id == v.size()){
if(cur==1)
return;
bt(v);
for(pii i : m[v]){
resp.push_back({i.ff+1,i.ss+cur});
}
return;
}
int aux = v[id];
int add = 1;
while(v[id]>=0){
choice(id+1,cur*add,v,resp);
v[id]--;
add*=fat[id];
}
v[id] = aux;
};
function<void(vector<int>)> bt = [&](vector<int>v){
if(m.find(v)!=m.end())
return;
vector<pii> resp;
choice(0,1,v,resp);
sort(resp.begin(),resp.end());
vector<pii> trueresp;
if(resp.size()>0){
trueresp.push_back(resp[0]);
for(int i = 1; i < resp.size(); i++)
if(resp[i]!=resp[i-1])
trueresp.push_back(resp[i]);
}
m[v] = trueresp;
};
bt(num);
set<int> trueresp;
for(pii i : m[num]){
trueresp.insert(i.ss-i.ff);
}
cout << trueresp.size() << '\n';
for(int i : trueresp)
cout << i << ' ';
return 0;
}