A Wreath for the Fox#12239

A Wreath for the Fox (Editorial)

Problem Author:	Andrii Kholod (Connect)
Prepared by:	Anna Yarosh (Anna_Yarosh)
Editorial:	Andrii Kholod (Connect)

Solution

Let us note that all numbers $x$ must divide $n - n mod 10$ n - n \bmod 10 exactly. This can be proven by contradiction. If the largest number smaller than $n$ is greater than $n - n mod 10$ n - n \bmod 10, then $n mod x$ n \bmod x will always be smaller than $n mod 10$ n \bmod 10. If this number is smaller than $n mod 10$ n \bmod 10, then $n mod x$ n \bmod x will always be greater than $n mod 10$ n \bmod 10. Also, all numbers $x$ must be greater than $n mod 10$ n \bmod 10, since there will always exist a number $m$ greater than $n - n mod 10$ n - n \bmod 10 that is divisible by $x$ .

Thus, the problem reduces to simply outputting, in sorted order, all divisors of the number $n - n mod 10$ n - n \bmod 10 that are greater than $n mod 10$ n \bmod 10.

The time complexity of the solution is $O (n)$ O(\sqrt{n}).

#include <bits/stdc++.h>
#include <random>

using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")

#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double

#define pll pair <ll, ll>
#define pls pair <ll, string>
#define pb push_back
#define mp make_pair

const ll DIM = 2e6+7;
const ll bsize = 450;
const ll INF = 1e12;
const ll mln = 1e6+7;
const ll mod = 998244353;
const ld gold = ((1+sqrt(5))/2);

vector <ll> a;

void solve(){

    ll n;

    cin>>n;

    ll last = n%10;
    ll k = n-last;

    ll cnt = 0;
    for(ll i=1; i*i<=k; i++){

        if(k%i == 0 && i > last){
            cnt++;
            a.push_back(i);
        }
        if(k%(k/i) == 0 && k/i > last && i != k/i){
            cnt++;
            a.push_back(k/i);
        }
    }

    sort(a.begin(), a.end());

    cout<<cnt<<endl;
    for(auto to : a) cout<<to<<" ";
}

int main(){
    speed;

    int test = 1;
   //cin>>test;

    while(test--){
        solve();
        //cout << '\n';
    }

    return 0;
}

C++