Віночок для лисички#12239

Віночок для лисички (Розбір)

Автор задачі:	Андрій Холод (Connect)
Підготовлено:	Анна Ярош (Anna_Yarosh)
Розбір:	Андрій Холод (Connect)

Рішення

Помітимо що числа всі числа $x$ повинні ділити націло $n$ $-$ $n$ $m o d$ $10$ . Це можна довести припустивши протилежне. Якщо найбільше число яке менше за $n$ більше за $n$ $-$ $n$ $m o d$ $10$ , то тоді $n$ $m o d$ $x$ завжди буде меншим за $n$ $m o d$ $10$ . Якщо ж це число менше за $n$ $m o d$ $10$ то тоді $n$ $m o d$ $x$ завжди буде більшим за $n$ $m o d$ $10$ . Також всі числа $x$ повинні бути більшими за $n$ $m o d$ $10$ . Оскільки тоді завжди знайдеться число $m$ яке більше за $n$ $-$ $n$ $m o d$ $10$ та ділиться націло на $x$ .

Тоді задача зводиться до того що нам просто потрібно вивести у відсортованому порядку такі дільники числа $n$ $-$ $n$ $m o d$ $10$ що вони будуть більшими за $n$ $m o d$ $10$ .

Асимптотика рішення O( $n$ \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++