Submission #1353011

#TimeUsernameProblemLanguageResultExecution timeMemory
1353011NewtonabcToys (CEOI18_toy)C++20
59 / 100
5104 ms319336 KiB
#include<bits/stdc++.h>
#define ll long long
const ll MOD=1e9+7;
const ll M2=676767677;
using namespace std;
struct pair_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(const pair<long long, long long>& p) const {
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();

        return splitmix64(p.first + FIXED_RANDOM) ^
               (splitmix64(p.second + FIXED_RANDOM) >> 1);
    }
};
unordered_map<pair<ll,ll>, int, pair_hash> mp;
ll n;
vector<ll> f,ans;
void dfs(ll now,ll sum){
    if(mp[{now,sum}]) return;
    mp[{now,sum}]=1;
    if(now==n){
        ans.push_back(sum);
        return;
    }
    for(auto x:f){
        if(now*x>n) break;
        dfs(now*x,sum+(x-1));
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=sqrt(n);i++){
        if(n%i) continue;
        f.push_back(i);
        if(n/i!=i) f.push_back(n/i);
    }
    sort(f.begin(),f.end());
    dfs(1,0);
    sort(ans.begin(),ans.end());
    ans.erase(unique(ans.begin(),ans.end()),ans.end());
    cout<<ans.size() <<"\n";
    for(auto x:ans) cout<<x <<" ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...