Submission #490987

#	Time	Username	Problem	Language	Result	Execution time	Memory
490987		Mike4235	Toys (CEOI18_toy)	C++17	100 / 100	3652 ms	17160 KiB

toy

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
// #define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

vector<int> v, d;

void solve(int x, int pos, int sum) {
    if (x == 1) {
        v.push_back(sum);
        return;
    }
    if (pos == sz(d) || x < d[pos]) return;

    solve(x, pos + 1, sum);
    while (x % d[pos] == 0) {
        x /= d[pos]; sum += d[pos] - 1;
        solve(x, pos + 1, sum);
    }
}

signed main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    int n;
    cin >> n;
    for (int i = 2; i * i <= n; i++) if (n % i == 0) {
        d.push_back(i);
        if (n / i != i) d.push_back(n / i);
    }

    sort(d.begin(), d.end());
    solve(n, 0, 0);

    v.push_back(n - 1);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    cout << sz(v) << "\n";
    for (auto x : v) cout << x << " ";
    
}

Compilation message (stderr)

toy.cpp:21:17: warning: overflow in conversion from 'long int' to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
   21 | const int INF = 1000000000000000000;
      |                 ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 21 / 21